哈希表是什么

Hash Table，也称哈希表。
一种数据结构，能够通过某种方法将数据组织为 key-value 的形式，以便在极短时间内访问到所需要的数据。

三要素

1. 哈希函数：能够对数据进行一系列运算后找到它应该被存储的位置，如何寻找这样的运算？
2. 冲突处理：使用哈希函数找到的位置上已经有数据了，如何解决当前数据的存储？
3. 扩容策略：当数据越来越多，冲突也越来越多，查询效率越来越低，如何扩容缓解冲突？

哈希函数

也称哈希函数。

直接定址法

一个线性函数形式，a, b 根据实际取。
该方法用得较少。
优点：

1. 冲突少，当且仅当数据的 key 相同时才会发生冲突。
2. 计算方便。只需要计算一个乘法和加法。

缺点：

1. 空间浪费。由公式可见，哈希表的大小由 key 的范围决定，，假设 key 本来只有少量的值，但是相差却很大时，就会浪费很多空间，如 key = [1, 2, 1000]

除留余数法

k 的大小决定了哈希表本身的长度，最多能存储 k 个元素。
其中 k 自取，实践表明取素数效果好，究其原因是导致的冲突少。
该方法应用广泛，常见的实现方法是拉链法。

优点：

1. 计算简单，应用广泛，实践效果好。

冲突处理

发生冲突的根本原因：对不同 key 的元素用哈希函数计算得到相同的哈希地址。

影响冲突的二因素

哈希函数

一个好的哈希函数应该尽量做到对于不同的 key 计算出不同的哈希地址，以此使得元素均匀分布，减少冲突。

装载因子

哈希表的不同实现，装载因子 α 的计算方法也不同，但规律是一样的。

• α 越小，空间利用率越低，发生冲突的可能性相对小，性能越好。
• α 越大，空间利用率越高，发生冲突的可能性相对大，性能越差。

直接定址法的装载因子 α = 记录数 / 哈希表长度。
拉链法的装载因子 α = 记录数 / 桶的个数。

策略

开放定址法

一类以发生哈希冲突的哈希地址为自变量，通过某种新的哈希函数得到一个新的空闲内存单元地址的方法。

• 通常来说，新的哈希函数往往不止一个，而是一组。
• 当计算出的哈希地址发生冲突时，把这个哈希地址放到新的哈希函数里计算，尝试找到一个可用的地址。

拉链法

把哈希表的每个存储空间看成一个桶，发生冲突的元素都放在一个桶里，用链表组织同一个桶里的元素。

扩容策略

未知待续。

常见的实现方法

最常见的实现组合是：除留余数法 + 拉链法。
各大高级编程语言的实现是这种方法的变种。