散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存储存位置的数据结构。而因为键是通过哈希函数得到的且键的空间是有限的,所以会产生不同的值经过计算后在哈希表的同一个位置,此时就发生了哈希冲突。

哈希表的装填因子 = 数据总数 / 哈希表长

解决办法

开放地址方法

通过某种探测方法,在冲突的哈希值附近寻找新的位置,直到找到一个没有冲突的位置。

根据探测算法可以分为一下几类:

  • 线性探测

按顺序决定下一个探测的哈希值,如果发现哈希冲突,则在原来哈希值的基础上增加一个单位,直到不发生哈希冲突
具体应用:Java的ThreadLocalMap

  • 再平方探测

在冲突的哈希值前后的空间内,以原先冲突的哈希值为基础,先后增加1的平方单位,减少1的平方单位;增加2的平方单位,减少2的平方单位;……直到找到不冲突的哈希值。

  • 伪随机探测

不断地在冲突的哈希值上增加一个随机数,直到找到不冲突的哈希值。

拉链法

在每个冲突的位置,构建一个链表,将哈希冲突的key放入链表中,每次查找的时候遍历这个链表。

具体应用:Java的HashMap、HashSet

优点

与开放定址法相比,拉链法有如下几个优点:

  • 拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;

  • 由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;

  • 开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;

  • 在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

缺点

指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。

再散列法

再散列法是拥有多个哈希函数(H1,H2,H3…),若H1(key)发生冲突则H2(key)、H3(key)。。。直到不发生冲突。

建立公共溢出区

建立公共溢出区存储所有哈希冲突的数据。