STL源码剖析笔记 - 哈希表冲突解决和容量扩充

C++

---

冲突解决方法

线性探测

当前项目冲突，就线性向后搜索，直到找到一个可以存放的位置，该方法复杂度较高。该方法会导致主集团(primary clustering)的问题，即多数的冲突会导致数据在array中较为集中的排列。

二次探测

当冲突时，向后搜索$H + 1^2, H + 2 ^ 2, H + 3 ^ 2, \dots$等位置，为了消除每次计算时需要计算二次函数，进行如下变换

$$H_i = H_0 + i ^ 2(mod \ M) \\ H_{i - 1} = H_0 + (i - 1)^2(mod \ M) \\ 整理得\\ H_i - H_{i-1} = i^2 - (i - 1)^2(mod \ M) \\ H_i = H_{i-1} + (2i - 1)(mod \ M)$$
$2i$操作可以用位移完成。但是这会有次级集团(secondary clustering)的问题，也就是两个元素hash function结果相同，那么探测的序列也是相同的，形成浪费。

开链(seperate chaining)

每个array的位置上，维护一个list，每次通过hash function得到array的位置，在该位置上的list进行插入、搜寻和删除。list够短时，这些操作效率是可以接受的。
STL中就是用的这种方法。

hashtable的桶(buckets)和节点(nodes)

每个hash table表格内的元素为桶子，一就是说一个元素维护的是一桶节点。图示如下：

Hashtable扩充容量的方法

判断何时需要扩容

根据新加入元素之后的元素数量，与当前buckets数量比较，如果前者大于后者，就表示需要扩大容量，此时需要将组织buckets的vector容量扩大之后，重新计算所存元素节点在新buckets中的新位置，并删除掉旧的节点。

扩容大小的选择

buckets的容量大小必须为质数，因此预先计算28个质数（呈现大约两倍的关系），并提供一个函数，查询在这28个质数中，“最接近某数并大于该数”的质数

HashSet和HashMap

HashSet和HashMap都是以hashtable作为底层机制，提供与set和map完全相同的操作，但是Hash版本的容器不提供自动排序的功能，非Hash的版本是以RB-tree作为底层机制，也就提供排序的能力。