跳转至

Hash

哈希表

哈希表（hash table）是实现字典操作的一种有效的数据结构。当关键字的全域 \(U\) 比较小时，基于数组的直接寻址简单而有效。但如果全域 \(U\) 很大时，哈希表需要的存储空间比直接寻址表小得多。

在直接寻址表中，具有关键字 \(k\) 的元素被放在槽 \(k\) 中。在哈希表中，该元素则放在槽 \(h(k)\) 中，即利用哈希函数(hash function) \(h\)，计算关键字 \(k\) 对应的槽的位置。函数 \(h\) 为全域 \(U\) 到哈希表 \(T[0..m-1]\) 的映射：

\[ h:U\rarr\{0,1,\cdots,m-1\} \]

随之而来的问题是，两个关键字可能映射到同一个槽中，即发生冲突。一种简单的冲突解决方法是拉链法，将哈希到同一个槽中的所有元素，采用尾插法放在一个链表中。

对于一个能存放 \(n\) 个元素、具有 \(m\) 个槽位的哈希表，其装载因子（load factor） \(\alpha\) 定义为 \(n/m\)，即一个链的平均存储元素数。

在实际应用中，计算得到的哈希值通常较大，需要再将哈希值对槽位的数量取模来确定存储位置。

随之而来的问题是，如果槽位数量发生变化，需要对原有数据重新进行 Hash 映射，一部分的数据可能需要迁移。最坏的情况下，所有的数据都需要迁移。

一致性哈希算法

一致性哈希算法（Consistent Hashing）是一种特殊的哈希算法。设 \(K\) 为关键字的数量，\(n\) 为槽位数量，使用一致性哈希算法后，槽位数量的变化平均只需要对 \(\frac{K}{n}\) 个关键字进行重新哈希映射。

TODO

哈希槽分区算法

TODO

布隆过滤器

TODO

参考