哈希散列 Hash

Hash表

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

设想一个简单的问题，输入 $n$ 个数字 $a_i$ ，每次询问一个数字 $x$ 是否出现。

一个用Hash思想的方法就是选取一个质数 $p$ ，计算 $a_i \bmod p$ 的结果。

但是这样有一个问题，假设取模结果相同怎么办，可以使用开链Hash和闭链Hash。

为了知道冲突产生的相同散列函数地址所对应的关键字，必须选用另外的散列函数，或者对冲突结果进行处理。而不发生冲突的可能性是非常之小的，所以通常对冲突进行处理。常用方法有以下几种：

即如果出现重复，用一个链表挂在外面。
查找的话只需要遍历一遍所有Hash值相同的元素。

即如果出现重复，继续向下一个位置填充。
当然查找的话要一直向后查找到第一个空位。

几乎没有人使用。

Hash表使用的人数少之又少，因为可行的替代方法非常多，
比如说排序二分，map，unordered_map，
只有在极少数情况在意常数的时候，才会使用Hash表。

一般使用开链Hash，用链表实现，代码简单。

一般认为是 $O(1)$ ，实际情况受较多因素影响。

Luogu P4305
直接使用set即可。

Luogu P1097
直接使用map即可。