开放地址法, Open Addressing
开放地址法, Open Addressing 本文我们来探讨一个数据结构的基础话题:hash 结构中的开放地址法(Open Addressing) HashMap 无 Java 人不知无 Java 人不晓,它使用开链法处理 hash 碰撞,将碰撞的元素用链表串起来挂在第一维数组上。但是并不是所有语言的字典都使用开链法搞定的,比如 Python,它使用的是另一种形式 —— 开放地址法。相比 HashMap 是二维的结构,它只是一维的,只有一个数组。 开放地址法与开链法的不同之处在于如何处理 hash 冲突。当新来一个元素哈希到数组中的位置已经被其它元素占据了该怎么办? 开放地址法会根据当前的位置计算出下一个位置,将这个冲突的元素挪进来。如果这下一个位置也被占用了,那么就再计算下一个位置,直到找到一个空的位置。可以想像,将会有一条虚拟的链条将这些相关的位置串起来。这个虚拟的链条就好比开链法里面的第二维链表。只不过链表有显示的指针字段,而虚拟链条没有,它的这个链条完全是通过数学函数计算出来的。 root = hash(key) % m // 第一个位置,m 为数组的长度 index_i = (root + p(key, i)) % m // 链条中的第 i 个位置 index_1 = (root + p(key, 1)) % m index_2 = (root + p(key, 2)) % m … 复制代码这个数学函数就是上面代码中的 p —— probe sequence (探测序列)。寻找空位置的过程就是一步一步的探测的过程。不同的 key 会生成不一样的探测序列。 在查找的时候,如果第一个位置上保存的 key 不是目标 key,那就沿着探测路径继续寻找,直到找到或者遇到一个空位置为止。 到这里你可能会担心又没有可能探测过程会出现死循环,探来探去又回到原点了,或者是回到路径的中间。这是很有可能的,所以这里的探测函数不能随意选择,它必须保证探测序列不会出现循环,经过 m-1 次探测生成的探测序列必须正好是 1..m-1的全排列。 这样的探测函数有很多,其中最常见的一种是线性探测函数。该探测序列和输入 key 无关。最终的探测路径只和初始位置相关。 // m = 2^n,c 必须是一个奇数 p(key, i) = c i index_i = root + c i 复制代码这里我不去仔细证明这个函数为什么满足要求,我们可以写个简单的代码来验证一下。 ...