Hash table 处理碰撞的技术

Open addressing(closed hashing):探测方式。通过选择不同的位置来存放数据。

线形探测:计算公式为next_pos = (cur_pos + m) mod N;其中m 为常数,N 为Hash table 数组长度;

平方探测:常用计算公式为next_pos = (cur_pos + cur_pos^2) mod N;

二次Hash:常用计算公式为next_pos = (cur_pos + Hash2(key)) mod N;Hash2 表示第二个Hash 函数。

Chaining:链表方式。即把冲突的key 串在一起。

以上两种碰撞处理技术很多数据结构书籍都详细描述过,本处不在赘述。下面看看其他的方法:

Coalesced hashing:结合了Open addressing 和Chaining 方法,把Chaining 的链表融合到Hash table 的数组里面,从而减少了空间使用。

下面用一个例子说明这种方式。输入key 序列为{“qur”,“qrj”,“ofu”,“gcl”,“clq”,“ecd”,“aty”,“rhv”,“qus”},左边图是基本Chaining 方式的结果,右边图是本方式的结果:

Coalesced hashing 方式的处理方法为:利用线形探测找到一个空位,填入key,然后把这个空位链接到相同映射值组成的链表上面。

需要注意的是,Coalesced hashing 对定长的key 才真正有用。

Cuckoo hashing:基本思想是使用2 个hash 函数来处理碰撞,从而每个 key 都可以对应到2 个位置。其具体的处理方式为:

如果key 对应的2 个位置中有一个为空,key 就可以插入到那个位置;

否则,任选一个位置,key 插入,把已经在那个位置的key 踢出来;

被踢出来的key 需要重新插入;

直到没有key 被踢出为止。

显然,这种方式是可能产生无限循环的,当出现无限循环的时候,就需要重新选择hash 函数。

Cuckoo hashing 有2 个主要的变形:1)增加hash 函数的个数;2)每个位置可以放2 个key。

这2 个的目的都是为了增加Hash table 数组的利用率,因为基本的Cuckoo hashing 只有49%的利用率,而3 个Hash table 可以利用91%的空间,每个位置保存2 个key 可以使利用率达到80%。

有人分析Cuckoo hashing 比Chaining 的方式更好。