哈希Hash

什么是Hash

通过一些计算，把关键码值映射到数组中的位置来访问记录，这个过程称为散列（hash）。

重要组成：

• hash函数：把关键码值映射到位置的函数称为散列函数。用h表示。
• hash表：存放记录的数组称为散列表。用HT表示。
• 槽（slot）：散列表中的一个位置称为一个槽。

设计hash表的目标是：使得对于任何关键码值K和某个散列函数h，i=h(K)是表中满足0<=h(K)<M（M为HT中槽的数目）的一个槽，并且记录在HT[i]存储的关键码值与K相等。

冲突解决

在实际情况中，我们根据散列方法组织的数据库必须把存储的记录存放在不大的散列表中，以避免浪费过多的空间。这样的话，有可能有多个关键码值计算出来的h(K)是一样的，但又不能同时放在同一个槽中，此时就要使用冲突解决策略。

冲突解决策略

冲突解决策略一般分为两类：

• 开散列方法（open hashing；也称为单链方法）
• 闭散列方法（closed hashing；也称为开地址方法）

开散列方法

开散列方法的最简单形式把散列表中的每个槽定义为一个链表的表头，散列到一个槽的所有记录都放在这个槽的链表内。

闭散列方法

闭散列方法把所有记录直接存储到散列表中。每条关键码值标记为k_R，记录R有一个基槽，就是h(k_R)，即由散列函数计算出来的槽。如果要插入一条记录R，而另一条记录已经占据了R的基槽，那么就把R存储在表的其他槽内。

桶式散列

• 一种实现闭散列的方法是把散列表中的槽分成多个桶(bucket)。把散列表中的M个槽分成B个桶，每个桶中包含M/B个槽。
• 散列函数把每一条记录分配到某个桶的第一个槽中。
• 如果这个槽已经被占用，那么就顺序地沿着桶查找，直到找到一个空槽。
• 如果一个桶全部被占满了，那么就把这条记录存储在表后具有无限容量的溢出桶（overflow bucket）中。

线性探查

最常用的散列方法。当发生冲突时，从当前基槽开始往后查找，有空位则将记录放进去。例如，2037原本应放在7的槽中，但是7已经被占用，所以往后查找空位，8是空的，于是将2037放进去。

但是这种方法会导致基本聚集。例如在上例中，下一条记录放到第2个槽的概率就是6/10了，因为取模后值为7,8,9,0,1,2都会放到第2个槽中。在理想情况下，表中的每个空槽都应该有相同的机会接受到下一个要插入的记录。

改进的冲突解决方法

如何避免基本聚集呢？

一种可能的改进方式是仍然使用线性探查，但是跳过一些槽，而且每次跳过常数c个而不是1个槽。这会生成探查函数：P(K,i)=ci。

例如，如果常数c是2的话：如果基槽被占用的话，第一次会找基槽+2的位置，看是否被占用，如果被占用了，第二次会找基槽+4的位置，如果还是被占用，则找基槽+6的位置，以此类推。即从基槽开始的偏移量将会为2,4,6。

另一种方法是使用二次探查函数（对于某些常数c1,c2,c3）：p(K,i)=c1i<sup>2</sup>+c2i+c3。一个最简单的变体就是p(K,i)=i<sup>2</sup>。

例如，对于一个长度M=101的散列表，假定对于关键码k1和k2，h(k1)=30，h(k2)=29。k1的探查序列为30,31,34,39；k2的探查序列为29,30,33,38。这样，尽管k2会在第二步探查k1的基槽，这两个关键码的探查序列此后就立即分开了。

双散列方法

即由两个散列函数，一个散列函数用于计算基槽，另一个散列函数用于确定线性探查中的常数。即线性探查此时的形式为：p(K,i)=i*h2(K)。

例如，假定散列表的长度是M=101，有3个关键码k1，k2，k3，h(k1)=30，h(k2)=28，h(k3)=30，h2(k1)=2，h2(k2)=5，h2(k3)=5。那么k1的探查序列为：30,32,34,36等；k2的探查序列为：28,33,38,43等；k3的探查序列为：30,35,40,45等。这样关键码之间就不会共享同一段探查序列了。