哈希表

一般哈希
将一个很大的值域映射到 0~N 的空间上，一般 N 为 105 或 106。
一般映射是使用取模的方法，且 mod 的数一般取质数，该质数一般离 2 的整次幂尽可能的远，因为这样取的话，冲突的可能性最小。
这里取 x mod 大于105的质数，第一个为 100003，主要区别在于映射时的冲突如何处理。
一般只有添加和查找两个操作，很少会有删除的操作。

存储结构

1 开放寻址法

只开了一个一维数组没有开链表，一般长度为题目数据范围的 2 ~ 3 倍（经验范围，这样发生冲突的可能性较低）。
处理冲突：h(x) = k，若该位置已有数值，则后移一位，直至移至一个空位存储。

添加：h(x) = k，有数就后移，没数就存储，若有相同数则无需操作。
查找：h(x) = k，当前位有数判断是否为 x ，不是就后移，直至找到或者遇到空位，遇到空位说明不存在 x 。
删除：先查找，找到后将该数据打标记，而不是真的从表中删除。

2 拉链法

开一个一维数组（例如 0 ~ 105 - 1）存储所有的值，数组中的每一位存储 e[ ] 和 ne[ ]，因为把每一位看作一个槽，里面放一个链表，理想的情况下每个槽只有一个数，冲突的时候会需要链表。
对于 mod 后相同结果的值，存放在相同位置的链表中，如下图：

添加和查找：h(x)
删除：使用一个布尔变量，为该数打一个标记。而不是真的从哈希表中删除该数。