最近在复习算法和数据结构 ，这章把hash表的概念和相关题目进行汇总。
1.1、哈希表和数组、以及链表的对比：
(1).数组的特点：寻址容易，插入和删除困难；数组存储连续,查找一个元素的时间复杂度为O(1)；
(2).链表的特点：寻址困难，插入和删除容易。链表存储区是离散的，遍历链表的元素的时间复杂度为O(N)。
(3).hash-table是根据关键值（key-value）来直接进行访问的数据结构，它结合了数组和链表的优点。hash表的难点
在于设计hash函数，以及解决冲突。这里我们会在后面提及；
这里是一些联系人的信息，如果要存储这些信息你会怎么做？我们比较直观的想法是，设计一个结构体，用链表来存储。结构体里面包含一个char型数组存放名字，char字符串存放电话号码，和一个结构体指针用来存放下个结构体的地址。
[cpp]view plaincopy
张三 13980593357
李四 15828662334
王五 13409821234
张帅 13890583472
当要查找”王五 15828662334“这条记录是否在这张链表中时，可能会从链表的头结点开始遍历，依次将每个结点中的姓名同”李四“进行比较，直到查找成功或者失败为止，这种做法的时间复杂度为O(n)。即使采用二叉排序树进行存储，也最多为O(logn)。假设能够通过”王五“这个信息直接获取到该记录在表中的存储位置，就能省掉中间关键字比较的这个环节，复杂度直接降到O(1)。Hash表就能够达到这样的效果。
Hash表采用一个映射函数 f : key —> address 将关键字映射到该记录在表中的存储位置，从而在想要查找该记录时，可以直接根据关键字和映射关系计算出该记录在表中的存储位置，通常情况下，这种映射关系称作为Hash函数，而通过Hash函数和关键字计算出来的存储位置(注意这里的存储位置只是表中的存储位置，并不是实际的物理地址)称作为Hash地址。比如上述例子中，假如联系人信息采用Hash表存储，则当想要找到“李四”的信息时，直接根据“李四”和Hash函数计算出Hash地址即可。
常见的hash函数有三种，分别是：直接取余法、乘积取整法、平方取中法。下面一一介绍：
直接取余法根据字面意思我们就能理解到，它的基本实现是用关键字直接除以散列表的大小(我们一般取跟元素个数最
接近的质数作为散列表的大小)。如果知道Hash表的最大长度为m，可以取不大于m的最大质数p，然后对关键字进
行取余运算，h(key)=key%p。很多的书上认为，哈希表的大小最好是选择一个大的质数，并且最好不要和2的整数幂接近。最不好的选择是哈希表的大小恰好是2的整数幂。
这里可以这么认为：计算机是用二进制存储的，当一个二进制数除以一个2的整数幂的时候，结果就是这个二进制数的后几位，前面的位都丢失了，也就意味着丢失了一部分信息，进而导致哈希表中的元素分布不均匀。为了避免产生冲突，我们可以采用加、乘法、移位等等运算关系来进行处理，然后再取余数，获得哈希地址。
下面是个例子。
[cpp]view plaincopy
staticintadditiveHash(String key,intprime)//prime为我们选取的hash表大小。
{
inthash, i;
for(hash = key.length(), i = 0; i < key.length(); i++)
hash += key.charAt(i);
return(hash % prime);
}
关键字k乘以一个在(0,1)中的实数（最好是无理数），得到一个(0,1)之间的实数；取出其小数部分，乘以m，再取整数部分，即得K在Hash表中的位置。
对关键字进行平方运算，然后取结果的中间几位作为Hash地址。假如有以下关键字序列{421，423，436}，平
方之后的结果为{177241，178929，190096}，那么可以取{72，89，00}作为Hash地址。
2.1"One-Way Hash"算法
这个算法是Blizzard的创作，是一个非常高效的把字符串转换成整数的算法，举个例子，字符串"unitneutralacritter.grp"，通过这个算法得到的结果是0xA26067F3。
[cpp]view plaincopy
unsignedlongHashString(char*lpszFileName, unsignedlongdwHashType)
{
unsignedchar*key = (unsignedchar*)lpszFileName;
unsignedlongseed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;
intch;
while(*key != 0)
{
ch = toupper(*key++);//toupper是转换为大写
seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);
seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;
}
returnseed1;
}
运用上面的函数就可以把字符串转化为整数，接下来我们用这个整数就可以通过hash函数产生hash地址了。
[cpp]view plaincopy
intGetHashTablePos(char*lpszString, SOMESTRUCTURE *lpTable,intnTableSize)
{
intnHash = HashString(lpszString), nHashPos = nHash % nTableSize;
if(lpTable[nHashPos].bExists && !strcmp(lpTable[nHashPos].pString, lpszString))
returnnHashPos;
else
return-1;//Error value
}
其他的字符串转换成整数算法，可以查阅相关书籍，这不再深入分析。
最常用的一种解决哈希冲突的方法，我们可以理解为“链表的数组”，如图：
左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。
这里给个例子：设有 m ＝ 5 ， H(K) ＝ K mod 5 ，关键字值序例 5 ， 21 ， 17 ， 9 ， 15 ， 36 ， 41 ， 24 ，按外链地址法所建立的哈希表如下图所示：
用开放定址法解决冲突的做法是：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定 的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的 地址则表明表中无待查的关键字，即查找失败。
注意：
①用开放定址法建立散列表时，建表前须将表中所有单元(更严格地说，是指单元中存储的关键字)置空。
②空单元的表示与具体的应用相关。
按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、线性补偿探测法、随机探测等。
该方法的基本思想是：
将散列表T[0..m-1]看成是一个循环向量，若初始探查的地址为d(即h(key)=d)，则最长的探查序列为
d，d+l，d+2，…，m-1，0，1，…，d-
即:探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循环到T[0]，T[1]，…，直到探查到T[d-1]为止。
探查过程终止于三种情况：
(1)若当前探查的单元为空，则表示查找失败（若是插入则将key写入其中）；
(2)若当前探查的单元中含有key，则查找成功，但对于插入意味着失败；
(3)若探查到T[d-1]时仍未发现空单元也未找到key，则无论是查找还是插入均意味着失败(此时表满)。
利用开放地址法的一般形式，线性探查法的探查序列为：
hi=(h(key)+i)％m 0≤i≤m-1//即di=i
用线性探测法处理冲突，思路清晰，算法简单，但存在下列缺点：
① 处理溢出需另编程序。一般可另外设立一个溢出表，专门用来存放上述哈希表中放不下的记录。此溢出表最简
单的结构是顺序表，查找方法可用顺序查找。
② 按上述算法建立起来的哈希表，删除工作非常困难。假如要从哈希表 HT 中删除一个记录，按理应将这个记录所
在位置置为空，但我们不能这样做，而只能标上已被删除的标记，否则，将会影响以后的查找。
③ 线性探测法很容易产生堆聚现象。所谓堆聚现象，就是存入哈希表的记录在表中连成一片。按照线性探测法处
理冲突，如果生成哈希地址的连续序列愈长 ( 即不同关键字值的哈希地址相邻在一起愈长 ) ，则当新的记录加入该
表时，与这个序列发生冲突的可能性愈大。因此，哈希地址的较长连续序列比较短连续序列生长得快，这就意味
着，一旦出现堆聚 ( 伴随着冲突 ) ，就将引起进一步的堆聚。
线性补偿探测法的基本思想是：
将线性探测的步长从 1 改为 Q ，即将上述算法中的 j ＝ (j ＋ 1) % m 改为： j ＝ (j ＋ Q) % m ，而且要求 Q 与
m 是互质的，以便能探测到哈希表中的所有单元。
【例】 PDP-11 小型计算机中的汇编程序所用的符合表，就采用此方法来解决冲突，所用表长 m ＝ 1321 ，选用
Q ＝ 25 。
随机探测的基本思想是：
将线性探测的步长从常数改为随机数，即令： j ＝ (j ＋ RN) % m ，其中 RN 是一个随机数。在实际程序中应预先
用随机数发生器产生一个随机序列，将此序列作为依次探测的步长。这样就能使不同的关键字具有不同的探测次
序，从而可以避 免或减少堆聚。基于与线性探测法相同的理由，在线性补偿探测法和随机探测法中，删除一个记
录后也要打上删除标记。
