目录

一、什么是hash？

二、Hash函数构造方法

三、hash函数的冲突

四、冲突处理

小结：

---

一、什么是hash？

　　• 哈希表是一种实现高效查找的数据结构，也叫散列。
　　• 散列方法是使用函数h将U映射到表T[0..m-1]的下标上（m=O(|U|)）。这样以U中关键字为自变量，以h为函数的运算结果就是相应结点的存储地址。从而达到在O(1)时间内就可完成查找。
 

二、Hash函数构造方法

（1）整数的Hash函数构造方法
　　1、直接取余法
　　关键字k除以m，取余数作为在Hash表中的位置。函数表达式可以写成：
　　　　　　h(k)=k mod m　　　注：一般m选择为素数

　　2、乘积取整法
　　关键字k乘以一个在(0,1)中的实数（最好是无理数），得到一个(0,1)之间的实数；取出其小数部分，乘以m，再取整数部分，即得K在Hash表中的位置。

函数表达式可以写成： 

　　例如就是一个好的选择。

　　3、平方取中法
　　把关键字K平方，然后取中间的位作为Hash函数值返回。由于K的每一位都会对其平方中间的若干位产生影响，因此这个方法的效果也是不错的。但是对于比较小的K值效果并不是很理想，实现起来也比较繁琐。为了充分利用Hash表的空间，M最好取2的整数次幂。例如,表容量M=2^4=16，，关键值K=100，那么
h(k)=8

（2）字符串的Hash函数构造方法
　　•字符串本身就可以看成一个256进制（ANSI字符串为128进制）的大整数，因此我们可以利用直接取余法，在线性时间内直接算出Hash函数值。
　　•为了保证效果，仍然不能选择太接近2^n的数；尤其是当我们把字符串看成一个2^p进制数的时候，选择m= 2^p -1会使得该字符串的任意一个排列的Hash函数值都相同。

（3）排列的Hash函数构造方法 -- 康拓展开
　　让排列与数1 - - A(m,n)之间建立一一对应的关系。
　　引理 

　　从0到n!-1的任何自然数可唯一地表示为： 

　　全排列与自然数之一一对应
　　不妨设n个元素为1,2,..,n。对应的规则如下:设序列
(an-1 ,…, a1)
对应的某一排列，其中ai可以看做是排列p中数i+1所在位置右边比i+1小的数的个数。以排列4213为例，它是元素1,2,3,4的一个排列。4的右边比4小的数的数目为3，所以a3=3。3右边比3小的数的数目为0，即a2=0
。同理a1=1 。所以排列4213对应于变进制的301，也就是十进制的19；反过来也可以从19反推到301，再反推到排列4213。
 

三、hash函数的冲突

　　• 冲突两个不同的关键字，由于散列函数值相同，因而被映 射到同一表位置上。该现象称为冲突(Collision)或碰撞。
　　• 安全避免冲突的条件 最理想的解决冲突的方法是安全避免冲突。要做到这一点 必须满足两个条件：
　　　　　①其一是|U|≤m
　　　　　②其二是选择合适的散列函数。 这只适用于|U|较小，且关键字均事先已知的情况，此 时经过精心设计散列函数h有可能完全避免冲突。
　　• 影响冲突的因素 冲突的频繁程度除了与h相关外，还与表的填满程度相关。设m和n分别表示表长和表中填人的结点数，则将 α=n/m定义为散列表的装填因子(Load Factor)。α越大， 表越满，冲突的机会也越大。通常取α≤1。

四、冲突处理

(1)用开放定址法处理冲突
　　• 冲突发生时，使用某种探查(亦称探测)技术在散列表中形成
一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的地址则表明表中无待查的关键字，即查找失败。
　　• 开放定址法的一般形式为：hi=(h(key)+di)％m （1≤i≤m-1），其中：
　　　　　①h(key)为散列函数，di为增量序列，m为表长。
　　　　　②h(key)是初始的探查位置，后续的探查位置依次是 h1，h2，… ，hm-1，即h(key)，h1，h2，… ，hm-1形成了一个探查序列。
　　　　　③若令开放地址一般形式的i从0开始，并令d0=0，则 h0=h(key)，则有： hi=(h(key)+di)％m （0≤i≤m-1），探查序列可简记为hi(0≤i≤m-1)。
注：
　　如果di值可能为1，2，3，...，m-1；称线性探测再散列。
　　如果di取值可能为1，-1，2，-2，4，-4，9，-9，16，-16，...，k*k，-k*k；(k<=m/2)，称二次探测再散列。

(2)拉链法解决冲突


=========================================================================================================

小结：

　　哈希表的应用范围很多，在某个问题中，如果需要经常查询某个元素和某个集合的关系，或者需要高效的数据存储、查找和判重，则使用哈希表是最好选择！哈希表作为一个编程简单、效率较高的数据结构，近年来在各项竞赛中频繁出现。在实际应用中，哈希表不一定是解决问题算法的核心算法，但它可以提高数据存储、查找和判重效率，从而提高了整个算法的运行效率。
========================================================================================================