Hash 表是一种将键映射到值的抽象数据结构，可以实现 key-value 键值对的存储与查找。

如上图，把 key 传给哈希函数（hash function），然后计算出 hash 值，hash 值映射到存储桶数组的下标，从而找到 value 值。这就建立了 hash 表中 key 和 value 的映射关系。

Hash 函数

hash function 在 hash 表中起到了非常关键的作用。hash 函数传入参数是 key，返回值是 hash 值。如果想建立完美的映射关系，hash function 最好能支持以下特性。

1. 传入相同的 key ，经过 hash function 得到「始终相同」的 hash 值。
2. 传入不同的key，经过 hash function 得到「始终不同」的 hash 值。

第一点保证了 key 和 hash 值对应关系的稳定性。第二点保证对应关系的唯一性，不过在实际场景中这几乎是不可能做到的，只能尽可能的减少不同 key 得到相同下标的概率。不同的 key 得到相同的 hash 值的现象称为 hash 冲突。

业界比较有名的 hash 算法：MD5、SHA系列。

支持操作

Hash 表通常需要支持插入、查找、删除操作。

插入：根据传入的 key ，经过 hash function 生成 hash 值，把 hash 值映射到数组中。在数组中存储指向 value 的地址。

查找：和插入过程一样，只不过最后返回查询到的 value 值。查找过程中除了 hash function 运算，就是在数组中根据下标找到值的过程。数组根据下标查找数据的时间复杂度是O(1)，所以我们也常说 Hash 表查找的时间复杂度接近 O(1)。（因为存在 hash 冲突，其实 O(1) 是不准确的）

删除：删除过程一般采用软删除，把需要删除的元素找到之后标记为已删除，然后采用其它策略完成真正的删除。软删除避免了数组中删除元素时重新移动元素的问题。带来的副作用是删除元素并没有真正释放存储空间。

Hash 冲突

上文中提到的 hash function 无法做到“传入不同的key，经过 hash function 得到「始终不同」的 hash 值”。当不同的 key 得到相同的 hash 值时，就出现了 hash冲突。

解决 hash 冲突有两类方法：链表发和开放寻址发。

链表发是最常用的方法。

就像它的名字，它通过链表来存储出现 hash 冲突的元素。对某个 key 进行 hash 运算生成 hash 值，当发现 hash 表中已经存在这个 hash 值，但是 key 不相同时，采用链表，把这个 key 和 value 存在当前元素的后面。

开放寻址法的核心思想是在发生 hash 冲突时，重新探测一个空闲位置来存储数据。当下次查找时，根据相同的探测规则来查找到相应的 value 。开放寻址有线性探测、二次探测、双重 hash 等多种方法。

对于一些动态增加的 hash 表，随着 hash 表中数据增多，hash 冲突的概率会越来越大，也会导致其操作性能下降。通常通过装载因子来衡量一个 hash 表可能发生冲突的概率。

装载因子=填入表中的元素个数/散列表的长度

当装载因子过大，比如超过0.8时，往往通过对 hash 表进行动态扩容来减少 hash 冲突。动态扩容过程中需要进行 rehash 操作，往往会占用比较高的 cpu 和 存储。比较经典的解决方案是采用渐进式 rehash，缓慢的对 hash 表完成扩容。

局限性

总体来讲 hash 表是一种非常高效的索引数据结构，不过它也有一些局限性：

1. 因为 key 和 hash 值的存储往往是无序的，所以通常认为 hash 表不擅长范围查找，更适合，单值查找。
2. hash 表的 key 通常需要全部加载到内存中，多有当有大量 key 时会占用比较多的内存。（用磁盘来存储 key ，会产生很多随机磁盘 I/O ，效率比较低）

总结

本文我们主要介绍了 hash 表的基本概念、基本操作、 hash 冲突以及 hash 表的一些局限性。