散列存储方法

开散列方法（就是把散列函数输出的相同值统一放在一起）：

1、拉链法

开散列方法的一种简单形式是把散列表中的每个槽定义为一个链表的表头。散列到一个特定槽的所有记录都放到这个槽的链表中。图9-5说明了一个开散列的散列表，这个表中每一个槽存储一个记录和一个指向链表其余部分的指针。这7个数存储在有11个槽的散列表中，使用的散列函数是h(K) = K mod 11。数的插入顺序是77、7、110、95、14、75和62。有2个值散列到第0个槽，1个值散列到第3个槽，3个值散列到第7个槽，1个值散列到第9个槽。

2、桶式散列

桶式散列方法的基本思想是把一个文件的记录分为若干存储桶，每个存储桶包含一个或多个页块，一个存储桶内的各页块用指针连接起来，每个页块包含若干记录。散列函数h把关键码值K转换为存储桶号，即h(K)表示具有关键码值K的记录所在的存储桶号。 图9-6表示了一个具有B个存储桶的散列文件组织。有一个存储桶目录表，存放B个指针，每个存储桶一个，每个指针就是所对应存储桶的第一个页块的地址。

有些存储桶仅仅由一个页块组成，如下图中的1号存储桶。有的存储桶由多个页块组成，每一个页块的块头上有一个指向下一个页块的指针，例如，如下图中的第B-1号存储桶由b4，b5，b6三个页块组成，每个存储桶中最后一个页块的头上为空指针。

闭散列方法：

（个人感觉该方法不大好，会引发本来由散列函数确定的位置被前面的占了，然后在查找的时候比较麻烦，还是喜欢“开散列方法”，但是这个方法可以节约空间）

闭散列方法把所有记录直接存储在散列表中。每个记录关键码key有一个由散列函数计算出来的基位置，即h(key)。如果要插入一个关键码，而另一个记录已经占据了R的基位置(发生碰撞)，那么就把R存储在表中的其它地址内，由冲突解决策略确定是哪个地址。

闭散列表解决冲突的基本思想是：当冲突发生时，使用某种方法为关键码K生成一个散列地址序列d0，d1，d2，... di ，...dm-1。其中d0=h（K）称为K的基地址地置( home position )；所有di(0< i< m)是后继散列地址。当插入K时，若基地址上的结点已被别的数据元素占用，则按上述地址序列依次探查，将找到的第一个开放的空闲位置di作为K的存储位置；若所有后继散列地址都不空闲，说明该闭散列表已满，报告溢出。相应地，检索K时，将按同值的后继地址序列依次查找，检索成功时返回该位置di ；如果沿着探查序列检索时，遇到了开放的空闲地址，则说明表中没有待查的关键码。删除K时，也按同值的后继地址序列依次查找，查找到某个位置di具有该K值，则删除该位置di上的数据元素（删除操作实际上只是对该结点加以删除标记）；如果遇到了开放的空闲地址，则说明表中没有待删除的关键码。因此，对于闭散列表来说，构造后继散列地址序列的方法，也就是处理冲突的方法。

形成探查的方法不同，所得到的解决冲突的方法也不同。下面是几种常见的构造方法。

1、线性探查法

将散列表看成是一个环形表，若在基地址d（即h(K)=d）发生冲突，则依次探查下述地址单元：d+1，d+2，......，M-1，0，1，......，d-1直到找到一个空闲地址或查找到关键码为key的结点为止。当然，若沿着该探查序列检索一遍之后，又回到了地址d，则无论是做插入操作还是做检索操作，都意味着失败。 用于简单线性探查的探查函数是： p(K，i) = i

例9.7 已知一组关键码为（26，36，41，38，44，15，68，12，06，51，25），散列表长度M= 15，用线性探查法解决冲突构造这组关键码的散列表。 因为n=11，利用除余法构造散列函数，选取小于Ｍ的最大质数P=13，则散列函数为：h(key) = key%13。按顺序插入各个结点： 26: h(26) = 0，36: h(36) = 10， 41: h(41) = 2，38: h(38) = 12， 44: h(44) = 5。 插入15时，其散列地址为2，由于2已被关键码为41的元素占用，故需进行探查。按顺序探查法，显然3为开放的空闲地址，故可将其放在3单元。类似地，68和12可分别放在4和13单元中.

2、二次探查法

二次探查法的基本思想是：生成的后继散列地址不是连续的，而是跳跃式的，以便为后续数据元素留下空间从而减少聚集。二次探查法的探查序列依次为：12，-12，22 ，-22，...等，也就是说，发生冲突时，将同义词来回散列在第一个地址的两端。求下一个开放地址的公式为：

3、随机探查法

理想的探查函数应当在探查序列中随机地从未访问过的槽中选择下一个位置，即探查序列应当是散列表位置的一个随机排列。但是，我们实际上不能随机地从探查序列中选择一个位置，因为在检索关键码的时候不能建立起同样的探查序列。然而，我们可以做一些类似于伪随机探查( pseudo-random probing )的事情。在伪随机探查中，探查序列中的第i个槽是(h(K) + ri) mod M，其中ri是1到M - 1之间数的“随机”数序列。所有插入和检索都使用相同的“随机”数。探查函数将是 p(K，i) = perm[i - 1]， 这里perm是一个长度为M - 1的数组，它包含值从1到M – 1的随机序列。

4、双散列探查法

伪随机探查和二次探查都能消除基本聚集——即基地址不同的关键码，在探查时重叠在一起——的问题。然而，如果两个关键码散列到同一个基地址，那么采用这两种方法还是得到同样的探查序列，仍然会产生聚集。这是因为伪随机探查和二次探查产生的探查序列只是基地址的函数，而不是原来关键码值的函数。这个问题称为二级聚集( secondary clustering )。

为了避免二级聚集，我们需要使得探查序列是原来关键码值的函数，而不是基位置的函数。双散列探查法利用第二个散列函数作为常数，每次跳过常数项，做线性探查。