1. 简介

散列表的插入、删除和搜索操作都具有 O(1)O(1)O(1) 的时间复杂度。

通常而言，散列表的底层就是一个大小固定的数组，且散列表的大小通常需要为素数。

为了插入 (key,value)(key,value)(key,value) 键值对，需要首先使用散列函数对键进行散列，从而得到该键值对应该插入的位置（桶），即，pos=hash(key)pos=\text{hash}(key)pos=hash(key)。如果位置 pospospos 已被其他键值对占据了，则出现了冲突。

2. 分离链接法

分离链接法是解决冲突的一种方法，它会将散列到同一个位置的所有元素保存到一个链表（其他数据结构亦可，如，红黑树、另一个散列表等）中。

搜索：

（1）使用散列函数对关键码进行散列，以确定要遍历哪个链表；

（2）遍历相应的链表，直至命中目标，或搜索不到目标。

插入：

（1）使用散列函数对关键码进行散列，以确定应该插入哪个链表；

（2）遍历相应的链表，以确定该元素是否已经存在；

（3）如果已经存在，且允许插入重复元素，则通常可以增加一个字段，以表明该元素出现的次数，然后递增该字段；

（4）如果不存在，则将元素插入到链表头部。

装填因子（load factor）：

设散列表的大小为 mmm（即有 mmm 个桶/链表），元素总数为 nnn，则散列表的装填因子为 λ=n/m\lambda = n/mλ=n/m。

对于分离链接法来说，装填因子就是每个链表的平均长度，表示了搜索操作的平均代价。

分离链接法的一般原则是让 λ≈1\lambda \approx 1λ≈1。

3. 探测散列表

探测散列表是另一种解决冲突的方法。当出现冲突时，它会不断地尝试其他的桶，直至找到空桶为止。

一般地，探测散列表会相继尝试 h0(x),h1(x),h2(x),...h_0(x),h_1(x),h_2(x), ...h0​(x),h1​(x),h2​(x),...。其中，hi=(hash(x)+f(i))%mh_i=(\text{hash}(x) + f(i)) \% mhi​=(hash(x)+f(i))%m，mmm 表示散列表的大小。

一般来说，探测散列表的装填因子应该低于 λ=0.5\lambda=0.5λ=0.5。

线性探测法

在线性探测法中，fff 是 iii 的线性函数，如，f(i)=if(i)=if(i)=i，即相继地探测下一个单元，且必要时可以回绕（回到表头）。

线性探测法通常会导致一次聚集（primary clustering），即，数据连续地聚集到散列表的一些区域中，从而导致散列到该区域中的任何关键码都需要进行多次尝试才能够解决冲突。

应确保散列表的装填因子低于 λ=0.5\lambda=0.5λ=0.5。

平方探测法

平方探测法可以消除线性探测法中的一次聚集问题。

此时，fff 是 iii 的二次函数，如，f(i)=i2f(i) = i^2f(i)=i2。

如果散列表有一半是空的，且表的大小是素数，则平方探测法可以保证总能够插入一个新的元素。

平方探测法可能会导致二次聚集（secondary clustering），即散列到同一位置上的那些元素将探测到相同的备选位置。

双散列

此时，fff 是另一个散列函数，如，f(i)=i×hash2(x)f(i)=i \times \text{hash}_2(x)f(i)=i×hash2​(x)。

可以令 hash2(x)=R−(x%R)\text{hash}_2(x)=R-(x \% R)hash2​(x)=R−(x%R)，RRR 为小于 mmm（散列表大小）的素数。

4. 再散列

如果散列表被填得太满，即 λ\lambdaλ 太大了，那么操作的运行时间将消耗过长，且插入操作可能会失败。

此时，一种解决办法是再散列，即创建一个更大的散列表（如，大小约为原表的两倍），然后扫描原表，计算每个元素新的散列值，并将其插入到新表中。

再散列操作的时间复杂度为 O(n)O(n)O(n)，但均摊到每个插入操作上而言，再散列操作的时间复杂度为 O(1)O(1)O(1)。