哈希表
定义
哈希表又称散列表，哈希表中存储的是一些键值对 \(key-value\) ，每个 \(key\) 可以通过一个哈希函数 \(f\) ，得到 \(value\) 的存储地址。
所以我们可以通过关键字 \(key\) 通过哈希表快速得到其对应的 \(value\)，即 \(value=hash(key)\)。
类似数组的下标访问，\(value=arr[index]\)。
不同的是哈希表中的 \(key\) 不一定是下标索引，可以是字符串，类等等。只要我们能构造出对应的哈希函数 \(f\) 使每个关键字能映射到唯一一个存储空间上。
在理想情况下，每个 \(key\) 值能映射到的地址是不一样的。但是现实中常常会出现 \(f(k_1)=f(k_2)\) 的情况，这被叫做冲突
哈希函数
哈希表的核心就是哈希函数，一个好的哈希函数能有效提高哈希表的效率。
一个好的哈希函数有以下特点：
- 冲突少
- 计算时间复杂度低
- 散列地址分布均匀
常见的哈希函数有
- 直接定值法：就是取 \(key\) 的一个线下函数为散列地址。
- 除留余数法：设定一个模数 \(mod\) ，对 \(key\) 取余数，存到对应下标的地址中。
- 平方取中法：取 \(key\) 的平方后中间的几位数为散列地址。
冲突处理
无论是怎样的哈希函数，总会出现冲突，那么如何处理冲突就很重要了。
一般处理冲突有两种方法
- 开散列
- 闭散列
开散列
开散列的思路是在每个地址处维护一个链表，每当遇到冲突时就将键值加到链表中。
查找时，就遍历对应地址处的链表，对其中的每个数据比较其键值与查询的键值是否一致。
闭散列
闭散列的思路是当某个存储位置出现冲突时，就按照一定方法寻找一个没有冲突的地方，再存值。
如线性探测法如果在 \(d\) 处发生冲突，就依次检查 \(d + 1，d + 2\dots\)。
竞赛中的使用
一般哈希表在各个语言的库中都有对应的实现，如 \(c++\) 中的 \(map，unordered\_ map\)（ \(map\) 是用红黑树实现的，也能实现哈希表的功能，但是会多一个 \(\log n\) 排序的复杂度），\(Python\) 中的字典 \(dict()\) 。
所以在竞赛中一般直接调库。
参考文章：
《大话数据结构》 Oi Wiki - 哈希表