Hash算法概述
哈希函数（hash function）
哈希表是一种通过 keys 对 value 的映射，来实现数据访问的数据结构，而这种映射一般分为两个阶段：
- 将关键字 key 作为自变量， 通过一定的函数关系，计算出的因变量作为 value 的索引（index）。
- 如果该索引指向的空间上没有存储数据，则将 value 插入，否则，称为产生了一个冲突（collision），需要对冲突进行处理，之后找到新的没有数据的空间，再将 value 插入。
冲突处理（collision resolution）
当key的集合很大的时候，根据生日问题（birthday problem）原理，哈希冲突实际上是不可避免的，所以几乎所有的哈希表都会有对于冲突的解决策略，主要方法：
- 拉链法（separate chaining）：也被称为开放散列法（open hashing）或封闭定址法（closed addressing）
- 开放定址法（open addressing），也被称为封闭散列（closed hashing）
- 建立公共溢出区（building a public overflow area）
- 其他方法： * 联合哈希法（coalesced hashing） * 疯狂哈希法（cuckoo hashing） * 跳房子哈希法（hopscotch hashing） * 罗宾汉哈希法（robin hood hashing） * 二选哈希法（2-choice hashing）
负载因子（load factor）
一个评估哈希表的关键统计数据，被定义为：load factor = n / k, n 是记录的数量，k 是桶的数量
- 随着负载因子的扩大，出现冲突的概率会越来越大，所以当超过一定阈值时，需要扩容，避免哈希表因为频繁处理冲突而越来越慢。
- 随着负载因子的缩小，桶数组中空着的槽就越来越多，所以当小过一定阈值时，需要缩容，避免空槽飙升导致的内存浪费。
参考
打赏作者以资鼓励：
 |  |