> For the complete documentation index, see [llms.txt](https://anjia1.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://anjia1.gitbook.io/ds-algo/linear/hash-table.md).
# 2.4 哈希表
线性表结构+哈希函数，解决哈希碰撞
哈希表，Hash Table，又称 Hash 表或散列表。
哈希表能通过关键码或关键字 key 来进行直接访问 `hash_table[key]`，它由两部分构成：
1. 一个数据结构：通常是数组（或者链表）
2. 哈希函数：输入关键码 key，会返回数据结构的索引
## 哈希函数
哈希函数，Hash Function，又称 Hash 函数或散列函数。
哈希函数计算出来的值 `hash(key)` ，通常叫哈希值或 Hash 值或散列值。举个最简单的例子，关键码 key 是整数，哈希函数是 `hash(key) = key`。此时哈希表就退化成了一个数组，key 就是数组下标。
其实，哈希表就是数组的一种扩展，它很好地利用了数组支持按照下标随机访问数据的特性。哈希表对外表现为一个更强大的数组，其核心就在于哈希函数让“索引”变得更强大了。 `hash_table[key] = value`，实际上数据是存储在“数据结构”的 `hash(key)` 位置上，即 `data_structure[hash(key)] = value`。
一般情况下，关键码 key 是一个比较复杂的信息，比如字符串或很大的数。此时，就需要设计一个哈希函数 `hash(key)`，将复杂信息 key 映射到一个较小的值域内，然后再以此作为索引去访问与之对应的数据结构。举个例子，`hash_table["lies"] = 233`，如下图：
它在执行赋值操作的时候，实际上操作了两步：
1. 第一步，计算哈希函数 `hash("lies") = 9`。示例中用的算法是将字符串中的每个字符的 ASCII 码相加，再模 20，通过取模的方式，将下标限定在了 \[0, n-1] 范围内。
2. 第二步，再通过哈希值 9 来访问对应的数据结构——数组，即 `array[9] = 233`
## 哈希碰撞
哈希碰撞，Hash Collisions，又称哈希冲突或散列冲突或散列碰撞。
哈希碰撞是指两个不同的 key 计算出了相同的 hash 结果。把复杂信息映射到小的值域，发生碰撞是不可避免的。
一个好的哈希函数，可以减少碰撞发生的几率，让数据尽可能地均衡分布。碰撞少了，均匀分布了，容器的效率也会越高。哈希函数通常不会太复杂，因为复杂了会消耗较多的计算时间，进而影响哈希表的性能。哈希函数多种多样，比如直接寻址法、平方取中法、折叠法、随机数法，比如将每个字母的 ASCll 码值"进位"相加再取模，即 $$\frac{('n'-'a') \* 26^3 + ('i'-'a') \* 26^2 + ('c'-'a') \* 26 + ('e'-'a')}{78978}$$。
但是，无论多好的哈希函数，发生碰撞都是不可避免的，所以，我们还是需要一种终极的解决方案。
### 解决
常用的解决哈希碰撞的方法有两类：
1. 开放寻址法（open addressing）。思想是如果出现了哈希碰撞，就重新探测一个空闲位置，将其插入。探测方法有线性探测（linear probing）、二次探测（quadratic probing）、双重散列（double hashing）。
2. 链表法（chaining），也称开散列法。它是一种更常用的哈希冲突解决办法。
### **开散列法**
开散列法也称“挂链法”，它在表头数组的每个位置上“挂”着一个链表，如下图所示：
开散列法的 hash 函数依然用于计算数组下标，然后数组的每个位置存储一个链表的表头指针，每个链表保存着具有同样 hash 值的数据（同时也会存 key）。
开散列结合了数组和链表，可以解决哈希碰撞的问题，从而实现一个哈希表。在工程上也有广泛的应用，比如电话号码簙（姓名-电话）、用户信息表（用户名-信息）、缓存（LRU Cache）、键值对存储（Redis 数据库）、Java 的 LinkedHashMap 容器等。
我们知道，数组的优点是支持随机访问，缺点是需要连续内存。链表的优点是内存可以不连续，缺点是访问/查找是线性的。这里的哈希表将数组和链表混合使用，便同时利用了二者的优势，也规避了它们的不足。
开散列法（数组挂链法）的效率取决于 hash 函数写得怎么样。
| 时间复杂度 | 操作 | 说明 |
| ------- | --------------------- | ----------------------------- |
| 期望：O(1) | 插入
查询
删除
| 数据分布比较均匀 |
| 最坏：O(n) | 插入
查询
删除
| 数据全被映射到了
相同的 hash 值
|
当然，我们一般不会针对字符串写一个 hash 函数，因为编程语言已经帮我们写好了一些非常好的字符串的哈希函数，我们可以直接使用，比如集合和映射这样的库/数据类型。
## 集合、映射
* 集合（set）：存储不重复元素（的一个容器）
* 映射（map）：存储关键码 key 不重复的键值对
它们又分别分为两类：
* 无序集合/映射：一般用哈希表来实现，O(1)
* 有序集合/映射：遍历时按照元素/key 的大小进行排列，一般用平衡二叉搜索树（即平衡树）来实现，O(logN)
对于语言的内置类型（int, string）都已经有默认的非常好的 hash 函数，不需要我们自己写，我们可以直接在集合和映射里使用。比如：
1. C++
* set, map 是有序的，使用红黑树实现
* unordered\_set, unordered\_map 是无序的， 使用哈希表实现的
* multiset, multimap 多重集合/映射（允许 key 重复）
2. Java 里的 Set 和 Map 不重复
* HashSet, HashMap 无序的
* TreeSet, TreeMap 有序的
3. Python
* 集合 `{'aa', 'bb', 'cc'}`, `set(['aa', 'bb', 'cc'])`
* 字典 dict \~ JSON 对象
## 总结
这部分重点介绍了哈希表，它的两个核心是哈希函数和哈希碰撞。哈希碰撞有两种常用的解决方法，即开放寻址法和链表法。哈希函数的好坏决定了哈希碰撞的概率大小，也直接决定了哈希表的性能。
哈希表来源于数组，它借助哈希函数对“索引”进行了扩展，以利用数组支持按照下标随机访问元素的特性。无序集合和无序映射一般都是用哈希表来实现的，大部分编程语言都提供了这两种数据类型，我们可以直接使用。
严格来说，无序集合和无序映射是一个容器/接口，它们可以用哈希表来实现，而哈希表是一个实现方法/数据结构。然后，哈希表的底层又是通过[数组](/ds-algo/linear/array.md)或者[链表](/ds-algo/linear/linked-list.md)这两种最基本的数据结构来实现的。
### 主要参考
*
*