# 哈希函数（hash function）

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

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

# 冲突处理（collision resolution）

当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）

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

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

# 参考

* [哈希表及哈希函数研究综述](https://blog.51cto.com/changliujishu/1812523)
* [新式哈希表 - Swiss Tables](https://zhuanlan.zhihu.com/p/277732297)