哈希表是一种通过 keys 对 value 的映射，来实现数据访问的数据结构，而这种映射一般分为两个阶段：

• 将关键字 key 作为自变量， 通过一定的函数关系，计算出的因变量作为 value 的索引（index）。
• 如果该索引指向的空间上没有存储数据，则将 value 插入，否则，称为产生了一个冲突（collision），需要对冲突进行处理，之后找到新的没有数据的空间，再将 value 插入。

当key的集合很大的时候，根据生日问题（birthday problem）原理，哈希冲突实际上是不可避免的，所以几乎所有的哈希表都会有对于冲突的解决策略，主要方法：

1. 拉链法（separate chaining）：也被称为开放散列法（open hashing）或封闭定址法（closed addressing）
2. 开放定址法（open addressing），也被称为封闭散列（closed hashing）
3. 建立公共溢出区（building a public overflow area）
4. 其他方法： * 联合哈希法（coalesced hashing） * 疯狂哈希法（cuckoo hashing） * 跳房子哈希法（hopscotch hashing） * 罗宾汉哈希法（robin hood hashing） * 二选哈希法（2-choice hashing）

一个评估哈希表的关键统计数据，被定义为：load factor = n / k, n 是记录的数量，k 是桶的数量

• 随着负载因子的扩大，出现冲突的概率会越来越大，所以当超过一定阈值时，需要扩容，避免哈希表因为频繁处理冲突而越来越慢。
• 随着负载因子的缩小，桶数组中空着的槽就越来越多，所以当小过一定阈值时，需要缩容，避免空槽飙升导致的内存浪费。

• 哈希表及哈希函数研究综述
• 新式哈希表 - Swiss Tables