数据结构_Hash 表

JI,XIAOYONG原创2018/12/23大约 2 分钟

前言

Hash 表是一种可以快速插入和查找的数据结构，将数据保存在通过 hash 函数计算得到的下标中。

插入和删除所需时间为 O(1)。在确定容量、无需遍历时效果最好。

当其大小接近容量时，效率会变得很差。

Hash 表有两种存储方式

开放地址法
开放地址法，直接将数据存储在数组中。
当 hash 算出的地址已经被占用时，则走过一定的步长找到另外一个空位（在填充质数很大时就会很耗时）并保存数据。
链地址法
链地址法，创建保存数据的数组，该数组中不直接保存数据，而是保存一个用来存储这些数据的链表，将数据项直接存储的链表中。
当 hash 算法计算出的地址时，遍历数组中对应的链表找到空位并保存。

其中，开放地址法又分为 3 种实现：

再哈希法

每次前进的步长是根据另外一个 hash 算法计算出来的值

这个算法要求如下：

1. 与第一次 hash 输出不同
2. 不能输出 0

已经有一个公认的比较好的二次 hash 算法：

stepSize = constant - (key % constant)
如：stepSize = 5 - (key % 5)
* constant 是小于数组容量的质数

再哈希法 VS 二次探测法

在小型哈希表中，再哈希法比二次探测好；

但如果容量充足，并且容量大小不再变化时，二次探测效果好，在装填因子小于 0.5 时几乎没有性能损失

开放地址法 VS 链地址法

hash 表容器大小未知时，用链地址法比较好

当装填因子变得很大时，开放地址法性能下降很快，但链地址法只是线性下降。