哈希表

哈希表是一种数据结构，基于数组实现，但存取方式和数组不同。
哈希表可以认为是一种特殊的数组，一个重要的特性是“数据项的关键字与数组下标有关联”。（数据项的关键字经过简单计算便可得到数组下标，从而实现快速存取）

---

优点与缺点

• 优点
  • 提供快速的插入操作和查找操作，时间复杂度接近O(1)。
  • 编程实现相对容易。
• 缺点
  • 基于数组，一是创建后难于扩展，二是基本填满时性能下降严重。
  • 难以进行数据有序遍历。

因此，当可以提前预测数据量的大小且不需要有序地遍历数据时，使用哈希表具有巨大的优势。

---

哈希化

• 什么是哈希化？

  • 哈希化概念：通过映射方法（即哈希函数）把一个巨大的整数范围转化为一个可接受的数组范围中。对哈希表来说是把较大的关键字值范围压缩成较小的数组下标范围。
  • 哈希化过程（哈希函数步骤）：
    • 具有唯一标识作用的原始数据—s1—>合适的整数关键字—s2—>数组下标
    • s1: 有些原始数据虽然具备唯一标识特征，但可能不是数字（如字符串），也有可能存在冗余数字位（如校验位），需要将其处理为合适的整数关键字。属于预处理过程。
    • s2: 一般对整数关键字取余得到数组下标。

• 为什么要哈希化？

  • 数据存储快速：
    • 整数关键字与数组下标存在映射关系，可以通过关键字获取数组下标直接存取数据，而不用像普通数组那样通过遍历来存取数据。
  • 节省空间：
    • 将大范围整数压缩成小范围，需要的数组长度变小了。

• 哈希函数的要求：

  • 能将整数关键字范围转化为数组下标值，即关键字要和数组下标要有关联。
  • 简单能快速计算，即各种运算尽量要少。
  • 大范围的数字经过哈希映射后应随机地分布在这个小的数字范围。
    • 要保证数组容量不能整数很多关键字，否则关键字经哈希函数映射后容易在某处聚集，影响存取效率。

• 哈希函数的形式：

  • 关键字范围足够小且组织比较连续：
    • 可以不用哈希函数映射，关键字直接作为数组的下标。
  • 关键字随机分布：
    • key % arraySize（其中arraySize是数组容量），这种取余操作效果比较好。
  • 关键字非随机分布：（一般需要对关键字进行预处理，再取余）
    • 不要使用关键字中无效的数据位。关键字一般是位数比较高的整数，有些位对唯一标识这个关键字不起作用，如校验位，应舍弃这些位。
    • 折叠关键字。如哈希表数组容量为1000，对于一个原始关键字123456789，可折叠为123+456+789=1368，再对容量1000取余得到数组下标368。每组包含几个数字应该根据数组容量来选择。

• 举例说明：

  • 有时候虽然整数范围很大，但实际的数据项个数却相对较少。比如说一组整数 0，100，1000，其整数范围为[0, 1000]，但是却只有3项。
  • 若创建一个下标从0到1000的整数数组来存放这组整数，数组下标为0的单元存0，数组下标为100的单元存100，数组下标为1000的单元存1000。存取性能很高，可以通过整数直接访问数组，但只用到了3个地址单元，存储效率极低。
  • 若创建一个下标从0到2的整数数组来存放这组整数，数组下标为0的单元存0，数组下标为1的单元存100，数组下标为2的单元存1000。存储效率很高，但这些整数与数组下标没有关联，只能遍历来访问数组，存取性能比较低，当数据项个数很多时更差。
  • 哈希化在保证这些整数关键字与数组下标直接有关联的前提下，大大减小了整数范围。兼顾了存储效率和存取性能。

• 字符串哈希化

  • 一般方法：hashVal += pow27 * (letterAscii-96); 循环字符串长度次
  • Horner法：hashVal = (hashVal*27 + letterAscii) % arraySize; 循环字符串长度次

---

冲突

• 冲突：把巨大的数字空间压缩成较小的数字空间，插入时不能保证每个关键字都能通过哈希函数映射到数组的空白单元，删除时不能保证每个关键字通过哈希函数映射到的单元数据项正好为要删除的数据项。

• 减少冲突——哈希表数组容量取质数

  • 若哈希表数组容量为非质数，如6，则数据项关键字为2的倍数、3的倍数容易发生冲突，关键字为6倍数一定发生冲突；
  • 若哈希表数组容量为质数，如7，则数据项关键字仅在是7的倍数时发生冲突。
  • 如2 4 6 8 10 12这6个数是2的倍数，如果对 6 取余 得到 2 4 0 2 4 0 只会得到3种哈希值，冲突会很多。如果对 7 取余 得到 2 4 6 1 3 5 得到6种哈希值，没有冲突。
    因此，哈希表数组容量取质数可减少冲突。

• 处理冲突——开放地址法

  • 要求：指定目标数组大小两倍于需要存储的数据量，从而保证有大量单元是空的；否则在数组快满时，存取效率会严重降低。
  • 思想：当冲突发生时，通过系统的方法找到数组的一个空位并插入。
  • 查找开放地址的方法：
    • 线性探测：线性地查找空白单元，即数组下标递增（即步长为1）直到找到空位。
    • 二次探测：数组下标按步数的平方增加，直到找到空位。
    • 再哈希法：数组下标按另一个哈希函数计算得到的步长增加，直到找到空位。

• 解决冲突——链地址法

  • 思想：不使用对象数组，而是创建一个链表数组，新数据项直接插入哈希函数得到的数组下标的链表中。

---

基于线性探测的开放地址法

插入

• 过程：
  • 根据哈希函数获取数组下标，
    • 若该下标位置是空单元，则插入；
    • 若该下标位置已有关键字，则线性查找空位插入（查找过程中的线性探测，数组下标递增n位找到空位，则称探测长度为n）。
• 说明：
  • 哈希表中，一串连续的已填充单元叫做填充序列。
  • 增加越来越多的数据项时，填充序列变得越来越长，叫做聚集。
  • 哈希表再几乎被填满的数组中（聚集严重），每填入一个数据项都要花费很长时间（探测长度大），效率变得非常低。
  • 若允许有重复关键字的数据项，查找所有具有相同关键字的数据项需要搜索的范围为[哈希函数获得的数据下标, 哈希表末尾]，非常耗时。因此，若无特别需求，应禁止重复的关键字。

查找

• 过程：
  • 根据哈希函数获取数组下标，
    • 若该下标位置为空，查找失败；
    • 若该下标位置非空且内部关键字与查找键相等，查找成功；
    • 若该下标位置非空且内部关键字与查找键不相等，则依次查找下一个单元，直至查找相等关键字（查找成功）或查找到空单元（查找失败）。
• 说明：
  • 如上所述，在查找操作中也可能出现线性探测，和插入一样是在做线性的查找，但查找的目标不同，“查找过程中的线性探测”是在查找相同关键字的数据项，而“插入过程中的线性探测”是在查找空白单元。
  • 之所以探测到空单元就认为查找失败，是因为若相等关键字的数据项存在的话，之前插入算法本该把这个空单元填充，而不会遇到了空单元还没探测到具有相同关键字的数据项。

删除

• 过程：
  • 查找删除键，
    • 查找成功，则将查找单元中的数据项的替换为一个关键字为-1的特殊数据项—nonItem；
    • 查找失败，则删除也失败。
• 说明：
  • 对插入操作来说，有nonItem的单元按照空单元来处理；对于查找操作来说有nonItem的单元按照非空单元来处理。

性能问题

• 容量要求：

  • 一方面哈希表数据容量要为质数，尽量减少冲突；
  • 另一方面哈希表数组容量至少为预测需要数据量的两倍。因为数组中有一半的数据项时，对哈希表存取性能影响不大；但当数组中有超过三分之二的数据项时，性能便下降十分严重。数据项个数/哈希表数组容量 = 装填因子，即要确保装填因子不超过1/2。

• 原始聚集：

  • 随着插入的数据越来越多，哈希表越来越满，聚集变得越来越严重，导致线性探测时产生非常长的探测长度，从而使存取数据项非常耗时。
  • 有时候，虽然哈希表还不太满，但也会出现在某个部分大量聚集，从而降低哈希表的性能。
  • 导致上述聚集现象的主要原因：
    • 插入时探测步长为1（可人为改变）
    • 大量数据项关键字的哈希值相同（无法控制）

• 扩展数组：

  • 当聚集现象很严重时，一个选择是扩展数组——即创建一个新的更大的数组，然后把旧数组中的所有内容插入到新数组中。
  • 由于哈希函数是根据数组大小计算给定数据项的位置，因此，不能简单地从一个数组向另一个数组中拷贝数据。需要遍历老数组中的数据，然后通过insert()方法向新数组中插入，称为重新哈希化。该过程很耗时，但又是必须的。
  • 新数组的容量通常是大于原来的两倍的最近的质数。

---

基于二次探测的开放地址法

• 与线性探测的区别：步长是步数的平方。
  • 在线性探测中，若哈希函数计算的原始下标是x，线性探测就是x+1,x+2,x+3,以此类推。
  • 在二次探测中是x+1²,x+2²,x+3²,以此类推。
• 相对线性探测的优势：消除了原始聚集。
• 仍存在缺陷：二次聚集。如一些数据项的关键字值都映射到下标x，它们便会在x+1²,x+2²,x+3²,等位置聚集起来。当然，二次聚集并没有原始聚集那么严重，不过二次探测也不常用。
• 二次聚集产生的原因：步长固定，总是1，4，9，16，以此类推。

---

基于再哈希法的开放地址法

• 与前两种探测算法的区别：步长由第二个哈希函数计算得到。
  • 第二个哈希函数要求：和第一个哈希函数不同；不能输出0（步长为0即在原地踏步，陷入死循环）。
  • 常用形式：stant - (key % constant)，其中constant是小于数组容量的质数。
  • 作用：使得不同的关键字，即使映射地址相同，但步长很可能不相同。
• 相对于前两种探测算法的优势：消除了原始聚集和二次聚集。
• 再哈希法要求哈希表的容量是一个质数：
  • 假设哈希表容量不是质数，如15，由一个特定关键字映射到0且步长为5，则探测序列为0，5，10，0，5，10，以此类推一直循环。算法只能尝试三个单元，而不能访问到其他位置，最终会崩溃。（即表容量被步长整数，而陷入无限的循环中）
  • 假设哈希表容量是质数，如13，映射到0且步长为5的关键字的探测序列为0，5，10，2，7，12，4，9，1，6，11，3。除1之外不存在能整除该质数容量的步长，因此探测序列可以访问所有单元，所以只要表中由一个空位，就可以探测到它。

---

链地址法

• 概念：链地址法是创建一个链表数组，新数据项直接插入哈希函数得到的数组下标的链表中。

• 装填因子分析

  • 平均表长：已知，装填因子 = 数据项个数/哈希表的数组长度；因此，对链地址法的哈希表来说，装填因子就是各个单元中的平均链表长度。
  • 装填因子的作用：
    • 从定义上可以看出装填因子表征的是存储效率，装填因子越大，存储效率越高。
    • 但是随着装填因子增大，无论是开放地址法还是链地址法的存取性能（速度）会随之降低。
      • 开放地址法中在装填因子大于1/2后，存取性能快速下降；
      • 链地址法中存取性能随装填因子的增大缓慢的降低（若用有序链表实现，平均探测长度随装填因子的增大以1/2的斜率缓慢变大）。
    • 因此装填因子的取值要平衡“存储效率”和“存取性能”。
  • 装填因子的取值：
    • 已知，开放地址法中装填因子最大是1，即数组中所有单元都有一个数据项；出于对存取性能的考虑，开放地址法中装填因子一般不超过2/3甚至1/2。
    • 在链地址法中，由于链表能存储的数据量受内存容量决定，所以链地址法中装填因子可以非常大；同样出于对存取性能的考虑，链地址法中装填因子一般取1。

• 相对于开放地址法的优势：

  • 概念上简单：对表容量是否为质数没有要求
    • 一是因为不需要寻找空位来解决冲突问题（线性探测、二次探测和再哈希法）。
    • 二是因为不用担心表容量能被步长整除而陷入无限的循环（再哈希法）。
  • 具有更健壮的机制：
    • 一是在事先难以确定哈希表要存储多少数据时有优势。
    • 二是存储效率高，在不影响存取性能的前提下，开放地址法装填因子只能取到1/2左右，而链地址法装填因子可以取到1。
    • 三是存取速度受装填因子的影响小。
  • 哈希表数据项比较多时，装填因子链表会比较长，存取性能会降低

• 相对于开放地址法的缺陷：

  • 涉及到链表机制，代码实现相对复杂。

哈希表实现方法的选择

• 使用开放地址法时，对于小型哈希表，一般再哈希法效果最好。
• 使用开放地址法时，若内存充足可以保证装填因子低于1/2，三种方法存取性能都比较好，但线性探测法最简单，建议选择线性探测法。
• 若创建哈希表时要填入项数未知，建议选择链地址法，因为链地址法受装填因子影响小。
• 若创建哈希表时要填入项数可预测时，也建议选择链地址法，虽然实现较复杂，但当实际增加比预期更多的数据时，不会导致性能快速下降。

参考

[1] Java数据结构和算法（第二版）