数据结构

散列表（hash table）是扩展于普通数组的一种数据结构。

对普通数组可以直接寻址，能在 O(1) 时间复杂度内完成对数组中任意元素的访问，但它需要为每个可能的关键字保留一个元素位置，也称为槽（slot），因此需要占用很大的存储空间，同时又由于关键字可能并不是整型类型的，因此普通数组的使用场景相对有限。

在散列表中，不是直接将关键字作为数组的下标，而是通过关键字来计算得出相应的数组下标。在计算关键字对应的数组下标时，可能会发生「冲突」，即多个关键字被映射到了同一个数组下标，此时需要额外的算法来解决冲突问题，常用的算法有 链接法（Java 中的 HashMap、Redis 中的 Hash）和 开放寻址法（Python 中的 dict）。

散列函数

在散列表中，元素通过散列函数（hash function）根据关键字来计算得出对应的数组下标位置，散列函数会将关键字均匀地分散到散列表的各个槽中。当一个关键字 k 被散列函数 h 映射到了槽 h(k) 上时，h(k) 为关键字 k 的散列值，如下图所示。

  1.                          +------+
  2.                          |      |
  3. +-------------+          +------+
  4. | k1----------|--------->|      |h(k1)
  5. |          k2-|------+   +------+
  6. |    k3-------|---+--|-->|      |h(k3)=h(k4)
  7. |       k4----|--/   |   +------+
  8. +-------------+      +-->|      |h(k2)
  9.                          +------+
  10.                          |      |
  11.                          +------+
  12.                          |      |
  13.                          +------+

当两个关键字被映射到同一个槽中时，即发生了冲突。理想情况下的解决方式是，试图选择一个合适的散列函数来避免所有的冲突，使得散列函数尽可能地实现随机性，但现实情况下总是还会有出现冲突的可能性。

解决冲突

链接法

链接法的实现方式是，把散列到同一个槽中的所有元素都放在一个链表或者红黑树（JDK 8 对 HashMap 的优化）中。

  1.                          +------+
  2.                          |      |
  3. +-------------+          +------+
  4. | k1----------|--------->|  k1  |
  5. |          k2-|------+   +------+  +------+
  6. |    k3-------|---+--|-->|  k3  |->|  k4  |
  7. |       k4----|--/   |   +------+  +------+
  8. +-------------+      +-->|  k2  |
  9.                          +------+
  10.                          |      |
  11.                          +------+
  12.                          |      |
  13.                          +------+

当散列表能存放 n 个元素，并且散列表具有 m 个槽时，则定义 装载因子（load factor）为 n/m，用于评估链接法中一个链表平均能存储的元素个数。

在链接法中，对散列表的查询操作的最差时间复杂度为 O(n)，即所有元素都散列到了同一个槽中。散列表的平均性能与散列函数关联密切，如果散列函数能把关键字均匀地分散到不同槽中，那么查询操作的平均时间复杂度可能降低到 O(1)。

如果在链接法中的链表节点为双向链表，那么散列表的插入操作和删除操作即使在最坏情况下的时间复杂度也为 O(1)。

开放寻址法

开放寻址法的实现方式是，将所有元素都存放在散列表的槽中，通过 TODO

参考资料

  • 《算法导论》第 11 章