Hash表定义
散列表（Hash table，也叫哈希表），是根据关键字值(Key value)直接进行访问的数据结构。也就是说，它通过把关键字(关键字通过Hash算法生成)映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
Hash算法定义
哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值，这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母，随后的哈希都将产生不同的值。要找到散列为同一个值的两个不同的输入，在计算上是不可能的，所以数据的哈希值可以检验数据的完整性。一般用于快速查找和加密算法。
关键字K生成常用方法
关键字生成的目标:构造冲突较低的散列地址，保证散列表中数据的离散度。大部分情况下，我们都不清楚关键字的分布，可以采取以下常用的启发式散列算法。若我们清楚数据的分布，可以根据具体的分布情况来设计特定的散列算法。
除法散列法
取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词
公式：H(key) = key % p （p<=m）
平方散列法
当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。
公式：H(key) = ((key * Key) >> X) << Y
斐波那契（Fibonacci）散列法
和平方散列法类似，此种方法使用斐波那契数列的值作为乘数而不是自己。
- 对于16位整数而言，这个乘数是40503。
- 对于32位整数而言，这个乘数是2654435769。
- 对于64位整数而言，这个乘数是11400714819323198485。
公式：H(key) = ((key * 2654435769) >> X) << Y
随机数法
选择一随机函数，取关键字的随机值作为散列地址，通常用于关键字长度不同的场合。
公式：H(key) = Radmon(key)
处理碰撞
开放寻址法
开放寻址法把所有的元素都存放在散列表中，也就是每个表项包含动态集合的一个元素（元素可以为NULL）。
- 在开放寻址法中，当要插入一个元素时，可以连续地检查散列表的个各项（连续检查是可以通过不同的算法获得偏移位），直到找到一个空槽来放置这个元素为止。
- 当查找一个元素时，要检查所有的表项，直到找到所需的元素，或者最终发现元素不在表中。
- 在开放寻址法中，对散列表元素的删除操作执行起来比较困难。当我们从槽i中删除关键字时，不能仅将此位置元素置空。因为这样做的话，会导致在无法判断此位置是否有元素。应该用个特殊的值表示该元素已经删除。
公式：Hi=(H(key) + di) MOD m , [i=1,2，…，k(k<=m-1)]
其中H(key）为散列函数，m为散列表长，di为增量序列，可有下列三种取法:
- di=1,2,3，…，m-1，称线性探测再散列
- di=12,-12,22,-22，⑶2，…，±（k)2,(k<=m/2）称二次探测再散列
- di=伪随机数序列，称伪随机探测再散列
再散列法
产生碰撞时，再使用另一个散列函数计算地址，直到碰撞不再发生，这种方法不易产生“聚集”，但增加了计算时间（一个地址的产生可能会经过多个散列函数的计算）
公式：Hi=Hn(key), [n=1,2 ...,]
有一个包含一组哈希函数 H1...Hn 的集合。当需要从哈希表中添加或获取元素时，首先使用哈希函数 H1。如果导致碰撞，则尝试使用 H2，以此类推，直到 Hn。所有的哈希函数都与 H1 十分相似，不同的是它们选用的乘法因子。
拉链法
产生碰撞时，把哈希到同一个槽中的所有元素都放到一个链表中。拉链法采用额外的数据结构来处理碰撞，其将哈希表中每个位置（slot）都映射到了一个链表。
公共溢出区
建立一个公共溢出区，当发生碰撞时，把碰撞元素放到缓冲区。
参考
- 百度百科
- 博文：从头到尾彻底解析Hash表算法 （http://blog.csdn.net/v_JULY_v/article/details/6256463）
- 其他资料，不一一列出