B+树vsB树

1.在前者n个关键字对应n个子树，在后者n个关键字对应n+1个子树

2.

3.在B树中，各个结点中包含的关键字是不重复的。在B+树中，叶结点包含全部关键字，非叶结点中出现过的关键字也会出现在叶结点中。

4.在B+数中，叶结点包含信息，所有的非叶结点仅仅起到索引作用，非叶节点中的每个索引项只含有对应子树的最大关键字和指向子树的指针，不含有该关键字对应记录的存储地址；而在B树中，B树的结点都包含了关键字对应的记录的存储结构

操作系统文件管理学完之后，看一下这一章节；能了解B活着B+树的本质区别；

7.4散列表

7.4.1 散列表的基本概念

散列表，又称为哈希表。是一种数据结构。

为什么用这种数据结构呢 ，他的作用是什么呢？

原因是数据元素，即数据元素的关键字往往要储存地址相联系。类似于一种映射关系

而用哈希表来储存形成两者对应

就比如咱们看一个例子：

从这个例子咱们看到数据元素的关键字，应该储存在哪儿呢，具体每一个储存地址应该在那儿呢？咱们用哈希函数就把这个关系找出来了，看上图右边，咱们看他的计算得到对应的存储地址；一一计算你会发现，下面两种现象：

1.若不同的关键字通过散列函数映射到同一个值，则称之为同义词

2.通过散列函数确定的位置已经存放了其他元素，则称之为这种请况为冲突

7.4.2 处理冲突的方法

拉链法

用拉链法/链接法/链地址法处理冲突：把所有同义词存储在一个链表中

如下图

开放定址法

所谓开放定址法，是指可存放新表项的空闲地址既向他的同义词开放，又向他的非同义词开放。其数学递推公式为：

其di 有以下三种方法：

如果第0次确实冲突了：则

具体存放过程看王道视频（查找09）

对应结构哈希表的查找：

同义词，非同义词都要被检查，也算作查找长度

空位置的判断也算作一次比较 ，即长度（拉链法没有这样做）

越早遇到空位置，就可以越早确定查找失败

看起来很满，实际很空

平方探测法：

注意：

找《数论》

伪随机序列法：

再散列法

王道书上不要看了这部分。

7.4.3 散列查找以及性能分析

拉链法的散列查找以及性能分析

怎么查找一个特定字，以及他的查找长度：

首先咱们利用哈希函数球的对应的地址空间，然后再对应地址空间中的链表里面进行一一对比，如果对出相等就称之为这个这个查找到了，对于查找长度而言，空指针不算做查找一次，所以说查找长度就是对比次数的总和咯

平均查找长度呢？

看：

最理想情况:

查找失败：

13代表表长度为13，每次查找失败的概率是相同的。

装填因子，公式如下，其等价查找失败的平均长度。装填因子回直接印象散列表的查找效率。比如：对于查找失败，他是公式相等的，就相当于是同比影响的，再者说对于查找成功来说，装填因子越大，说明装填越多，就会导致冲突越多，就意味着表长越长，就意味着访问的时候开销越大。

开放定址法的查找效率分析

7.4.4 散列函数的构造方法（14：20）

直接定址法

你仔细看这个，直接定地址 或者线性的平移 ；其中a,b是常数。这种方法简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布基本不均匀，空位较多，则会造成储存空间上的浪费。

看一个例子：

除留余数法

质数：又称之为素数。指除了1和此整数自身外，不能被其他自然数整除的数；反之称为合数；

比如如下取散列表：

为什么用这个取一个不大于m但最接近或等于m的质数呢

为了让不同关键字的冲突能够最少；咱们才这么做；但是呢实际情况并不是绝对的，只是综合来说咱们遇到的数更符合使用最接近或等于m的质数这一选择。

比如如下：

当关键字是连续自然数时候：

当关键字是偶数是时候:

那到底为什么：《数论》中说，用质数取模，分布更均匀，冲突更少；

建议：虽然咱们考试是如此取值，三十具体散列函数的设计要结合实际关键字的分布特点来考虑，不要教条化；

数字分析法

选取数码分布较为平均的若干位作为散列地址

设关键字是r进制数（如十进制数），而r个数码在各位上出现的频率也不一定相同，可能在某些位上分布更均匀一些，每种数码出现的机会均等；而在某些位置上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。这种方法适用于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。

平方取中法

平方取中法：取关键字的平方值的中间几位作为散列地址。

具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布较为均匀，适用于关键字的每位取值都不够均匀或小于散列地址所需要的位数；

例如：

但是这样任然是有冲突的，那么咱们有什么办法绝避免冲突。有是有，就是给存储空间么。存储空间够多就能够了。如下