哈希表的定义、查找及分析

1、哈希表的基本思想:“一次”查找成功。关键字集合映射函数 H地址空间 H(key)ASL的T(n)=O(1)。通常设定一个一维数组空间存储记录集合，则H(key)指示数组中的下标。称这个一维数组为哈希(Hash)表或散列表。称映射函数 H 为哈希函数。 H(key)为哈希地址9.3.1 什么是哈希表9.3 哈希表1第一页，共二十一页。一、直接地址法取关键字或关键字的某个线性函数值为哈希地址即： H(key) = key 或： H(key) = a* key + b其中，a， b为常数。常用的构造哈希(散列)函数的方法： 假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, , u

2、s)，分析关键字集中的全体， 并从中提取分布均匀的若干位或它们的组合作为地址。二、数字分析法2第二页，共二十一页。四 、折叠法将关键字分割成位数相同的几部分，然后将这几部分叠加，舍去进位作为哈希地址。移位叠加：将分割之后的每一部分的最低位对齐，然后相加。间界叠加：从一端向令一端沿分割界来回折叠，然后相加。三、平方取中法将k平方后的中间几位取为哈希地址。位数由表长决定3第三页，共二十一页。五、 除留余数法当关键字k为整数时，用关键字除以一个整数p 所得余数作为哈希的地址。 H(key) = key % p4第四页，共二十一页。9.3.3 处理冲突的方法设hash表的长度为m，冲突是指 j=H(K

3、) 的位置已有记录，(0jm-1)“处理冲突” 为K另找一个“空”的地址。一. 开放地址法：哈希表的存储结构：typedef struct KeyType key； /关键字成员 ； /其它成员 elemtypetypedef elemtype hashtablem ；5第五页，共二十一页。利用下面的公式求“下一个”地址。 Hi = (H(key) + di ) % m, di是增量序列， (i=1，2，k，且km-1)根据d 的取值不同，开放地址法又可分为：()线性探测再散列： di = 1，2，3， ，m-1 ()二次探测再散列： di = 12，-12，22，-22，k2 此时：Hi =

4、 (H(key) +m+ di ) % m,()随机探测再散列 di = 伪随机序列6第六页，共二十一页。0 1 2 3 4 5 6 7 8 9 100 1 2 3 4 5 6 7 8 9 10例如: 关键字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 设定哈希函数 ：H(key) = key % 11 (表长=11)191011232141551683191011232141684若采用线性探测再散列处理冲突若采用二次探测再散列处理冲突1168223655511138213627第七页，共二十一页。在查找概率相同的情况下，查找成功时的ASLASLsucc =(1

5、*4+2*2+3+5+6)/9 =22/9查找不成功时的ASLASLunsucc=(9+8+7+6+5+4+3+2+1)/11=56/11若采用线性探测再散列处理冲突0 1 2 3 4 5 6 7 8 9 10191011232141551683116822365平均查找长度ASL：8第八页，共二十一页。在查找概率相同的情况下,查找成功时的ASLASLsucc =(1*5+2*2+3+4) /9 =16/9查找不成功时的ASLASLunsucc=( )/11= /11若采用二次探测再散列处理冲突0 1 2 3 4 5 6 7 8 9 101910112321416845511138213629

6、第九页，共二十一页。线性探测再散列的优点：只要哈希表未满，总能找到一个空地址。缺点：会产生二次聚集。 70 19 33 18 0 1 5 6 7 8 9 1210第十页，共二十一页。二、 链地址法在哈希表的每一个单元中存放一个指针，将所有的同义词连成一个链表。假设哈希地址在区间0 . m-1上，则哈希表为一个指针数组。typedef struct node /定义链表中结点 KeyType key； 其它成员 ； struct node *next； Node，*Nodeptr；typedef Nodeptr chainhashm；/ 定义指针数组11第十一页，共二十一页。0123456111

7、982685514013623ASLsucc=(61+22+3)/9=13/9例1: 关键字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 哈希函数 H(key) = key % 7 (表长=7)ASLunsucc=(41+12+3)/7=9/712第十二页，共二十一页。例2：有一组关键字BITE, EACH, BITTER, BROOM, AND, ALSO,HASH, EGGS ，现以关键字中第一个字母在字母表中的位置为该关键字的哈希函数值，链地址哈希表如下：ASLsucc=(4*1+3*2+1*3)/8=13/8 1 AND ALSO 2 BITE BITTE

8、R BROOM 5 EACH EGGS 8 HASH 2613第十三页，共二十一页。四、 建立一个公共溢出区设向量hashtablem为基本表。另设向量overtableV为溢出表。所有与基本表中关键字为同义词的记录都填入溢出表例：关键字表 (a，d，e，f，d1，d2，f1，g)， 表长 m=11，H(key)= i1 % 11； i1为首字母在字母表中的位置。0 1 2 3 4 5 6 7 8 9 10 基本表ad0 1 2 3 4 5 6 7 8 9 10 溢出表efd1d2f1g14第十四页，共二十一页。9.3.4 哈希表的查找及分析一.哈希表的查找查找过程和建立哈希表的过程基本一致。

9、(1) 计算哈希地址。(2) 相应地址上没有记录，则查找不成功。(3) 相应地址上有记录，则比较关键字， 若和给定值相等，则查找成功。 不相等，则根据造表时设定的处理冲突的方法找“下一地址”，直到哈希表中某个位置为空或者表中的关键字与给定值相同为止。15第十五页，共二十一页。int hashsrch(hashtable shtable，KeyType k) /已知hash函数为hash(key), 散列表的表长为m，地址序列/ Hi=(hash(key)+di)% m, di=1,2, ,m-1 j=hash(k)； if(shtablej=nullrecd) return(0)； else

10、if(shtablej.key=k)return(j)； else do j=(j+1) % m； /线性探测再散列while(shtablej.keyk & shtablejnullrecd) if (shtablej=nullrecd) return(0)； else return(j)； / hashsrch 16第十六页，共二十一页。二. 分析比较次数取决于三个因素：哈希函数、处理冲突的方法、哈希表的装填因子 在一般情况下，处理冲突方法相同的哈希表，其平均查找长度依赖于哈希表的装填因子。(1)查找成功时的平均查找长度线性探测 ASLl 随机探测、二次探测 ASLr 链地址法 ASLc

11、17第十七页，共二十一页。例：已知一个含有100个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈希表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过3。 ASLl = 3，(1) 用线性探测再散列处理冲突建立散列表存储则由 ： ASLl 3，可求出 求得 4/518第十八页，共二十一页。(3) 关键字分析：开头a-z，最长6位。 选择hash函数： hash(key) = 5*(i-1) + L 其中，i为第一个字母在字母表中的序号，L为关键字的长度。(2) 设表长：由 =记录长度n/表长m , 表长 m = n/ (100*5)/4=125 取表长 m = 13319第十九页，共二十一页。9.3 、9.9 、 9.13、9.14 、 9.19、9.21作业20第二十页，共二十一页。内容总结哈希表的基本思想:。通常设定一个一维数组空间存储记录集合，则H(key)指示数组中的下标。取关键字或关键字的某个线性函数值为哈希地址。其中，a， b为常数。常用的构造哈希(散列)函数的方法：。将关键字分割成位数相同的几部分，然后将这几部分叠加，舍去进位作为哈希地址。移位叠