1 预先知识
今天涉及哈希表的有关内容。
1.1 哈希表
哈希表(Hash Table)也称散列表，是一种特殊的数据结构。其通过一定的规则将数据进行 “ 散乱排列 ” ， 并通过该规则进行快速查找。这个规则叫做 “ 哈希函数 ” ，其可以将数据转化为一个固定的索引值，后续将该数据根据索引值存储在数组的某个位置。
1.1.1 哈希函数的实现方法
在理想状态下，哈希函数会将数据均匀散列分布在哈希表中。主要有直接定址法、除留余数法等。
1）直接定址法
当数据的范围比较集中是，优先考虑使用定址法。其主要实现方法类似一种键值对，键为数据的值，值为数据出现的次数。
该方法的缺陷是当数据比较分散且范围较大时，就造成空间浪费。
2）除留余数法
其核心思想是将数据对某个数（一般是表长）进行求余运算，将运算结果作为索引值，即表示该数据存放的下标位置。假设某哈希表的大小为M，则哈希函数为 \(\text{hash}=x \% M\)
此时应当注意：
- 为了尽量减少哈希冲突出现的次数，建议M取不太接近2的整数次幂的一个素数。
- 除留余数法中，为了方便数据转化为索引值，要求哈希表的数据元素支持转换为整数。
1.1.2 哈希冲突
当一个数据通过哈希函数产生了与另一个数据相同的哈希值，那么也就意味着它们需要存储在同一个位置，显然无法满足。此时的情况就叫做哈希冲突（哈希碰撞）。我们可以通过以下两种方法进行解决：
1）开放定址法（闭散列）
开放定址法是按照某种策略将冲突的数据放置在表中的另一个空位当中。常见的策略有三种：线性探测、二次探测和双重探测。
- 线性探测：线性探测指的是从冲突位置开始，依次向后一个一个查找，直到找到空位，再将冲突元素放置在当前空位。 当查找到表尾还没有找到空位，那么从表头位置开始重新查找。（容易造成表中的冲突数据聚集，且会占用其他元素的原本位置）
- 二次探测：二次探测对线性探测进行了优化。它的查找方式是依次左右按照二次方跳跃式探测。例如先探测冲突位置的右边 \(1^{2}\) 个位置，然后左边 \(1^{2}\) 个位置，右边 \(2^{2}\) 个位置，左边 \(2^{2}\) 个位置……依次类推。（二次探测有效地减少了数据聚集问题）
2）链接址法（开散列）
其改变了传统的哈希表元素存储策略，在链地址法当中，所有数据不再直接存储在哈希表中，而是将哈希表的每一个元素设置为指针，用以维护一个链表。此时哈希表中的每一个元素称作哈希桶，其中存储的元素互相之间就是哈希冲突的。
链接地址在发生冲突时，就不会占用其他元素的原本位置，相比开放地址法效率较高。
1.1.3 装填因子
记 \(\alpha=\) 表中元素的个数/散列表的长度，当装填因子过大时，哈希表的空间利用率就越高，发生哈希冲突的概率就越高，哈希表的总体性能就越低。在实际运用过程中，我们将装填因子作为哈希表是否需要扩容的标准。
- 采用开发定址法处理冲突时，该阈值通常位于0.7-0.8之间；
- 使用链地址法时，阈值则通常为1。
懈怠了┗|｀O′|┛ 嗷~~