哈希表的实现（取余法）

哈希表，又叫散列表，它可以提供快速的插入查找操作，对于大规模数据的查找时间空间效率会很高。哈希表构造方式有多种，其中取余法在比赛中最常用。

如果读入很多值非常大的数，让你判断一些数是否出现过。如果用桶来记录，空间开不了那么大。如果排序后来查，时间效率又低。但可以通过hash优化解决这个问题。

取余法简单地说，就是给每个数mod一个合适的值X，得到的余数放在数组中下标与其一致的位置，由于X不会很大，且余数不会超过数X，数组的大小在0..X-1范围内，不会超空间，如果查某个数，将这个数mod X后在直接在数组中找到。

但是这样一些不同数据会出现在同一个地址上，比如说X=5，13 mod X=3，18 mod 5=3，这两个数（13,18）便产生了冲突。

为了解决冲突，可以使用挂链的形式，将冲突数据像挂链一样挂在同一位置，将13放在5的位置，将18挂在13后面，如果要查18，先18 mod 5=3 找到3的位置，先看3位置挂链上的第一个数是13，不等于18，继续往后面找，直到找到18，如果找不到，说明没有出现，按要求输出即可。我们可以发现，这样的存储方式很像（或者就是）链表的存储方式，所以我们可以使用链表来处理“挂链”的部分。这样查找的问题就解决了。

经分析可以得知，hash表查找时间最好为O(1)，最差为O(n)，由于O(n)情况对于比赛的数据一般不会出现，如果选择了合适的X值，时间效率会非常好。

如何选择X值呢，通常是选一个较大但不会使数组超空间的质数。 

具体实现：

初始化

type hash=^node; node=record dx:int64; next:hash; end;

插入操作

procedure put(x:int64); var q:hash;xx:int64; begin xx:=x mod maxn;//maxn就是那个适当的正整数X new(q); q^.dx:=x; q^.next:=a[xx]; a[xx]:=q; end;

查找操作

function find(x:int64):boolean; var p:hash; begin xx:=x mod maxn; new(p); p:=a[xx]; while p<>nil do begin if p^.dx=x then exit(true); p:=p^.next; end; exit(false); end;