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

　　现假设关键字的全域为U = {k | 0 <= k < n}

1、直接寻址表

　　如果全域U比较小，即n的数值比较小,且没有重复元素，那么可以用数组T[0, m-1](m = n)做为直接寻址表，每个槽位T[k] = tk，tk = NIL表示不存在关键字为k的元素，否则表示有关键字为k的元素。

SEARCH(T, x)    return T[x]INSERT(T, x)    T[x] = xDELETE(T, x)    T[x] = NIL

直接寻址法限制较多，不常用。

 2、散列表

当全域U很大时，可以用函数h把U中元素k映射到表T[1, m]中的某个位置，即：

h: U{k} --> T[i], (k IN [0, n-1], i IN [0, m-1])

这样我们处理的值就从n降到了m。这里的函数h称为散列函数。

好的散列函数应该满足如下性质：每个关键字都等可能的映射到T[0, m-1]中的m个槽位中，且与其他关键字散列到哪个槽位无关

但这个性质很难满足. 散列函数假定关键字为自然数N的子集，如果关键字不是自然数，则将其变换为自然数。

一般有如下几种散列函数：

2.1、除法散列

h(k) = k mod m  // m表示槽位数，k表示关键字

一般讲m选择为与2的整数幂不太接近的质数。

2.2、乘法散列

h(k) = floor(m(kA mod 1)) // 0 < A < 1

其中 kA mod 1 表示取 kA的小数部分，floor表示向下取整。

A可以取黄金分割数 (sqrt(5) - 1) / 2

2.3 解决冲突

从全域U --> 表T, 可能存在k1和k2同时映射到T[i]的情况,发生了冲突，可以通过链接法来解决。

链接法实际是使用数组T[0, m-1], 数组的任意元素T[i]为一个链表的表头来实现的。

散列表