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

哈希表的基本思想:“一次”查找成功。关键字集合映射函数H地址空间H(key)ASL的T(n)=O(1)。通常设定一个一维数组空间存储记录集合，则H(key)指示数组中的下标。称这个一维数组为哈希(Hash)表或散列表。称映射函数H为哈希函数。H(key)为哈希地址9.3.1什么是哈希表9.3哈希表1哈希表的基本思想:关键字集合映射函数H地址空间H(key一、直接地址法取关键字或关键字的某个线性函数值为哈希地址即：H(key)=key或：H(key)=a*key+b其中，a，b为常数。常用的构造哈希(散列)函数的方法：假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,…,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。二、数字分析法2一、直接地址法常用的构造哈希(散列)函数的方法：假设四、折叠法将关键字分割成位数相同的几部分，然后将这几部分叠加，舍去进位作为哈希地址。移位叠加：将分割之后的每一部分的最低位对齐，然后相加。间界叠加：从一端向令一端沿分割界来回折叠，然后相加。三、平方取中法将k平方后的中间几位取为哈希地址。位数由表长决定3四、折叠法三、平方取中法3五、除留余数法当关键字k为整数时，用关键字除以一个整数p所得余数作为哈希的地址。

H(key)=key%p4五、除留余数法49.3.3处理冲突的方法设hash表的长度为m，冲突是指j=H(K)的位置已有记录，(0≤j≤m-1)“处理冲突”——为K另找一个“空”的地址。一.开放地址法：哈希表的存储结构：typedefstruct{KeyType

key；

//关键字成员

…；

//其它成员

}elemtypetypedef

elemtype

hashtable[m]

；59.3.3处理冲突的方法设hash表的长度为m，冲突是利用下面的公式求“下一个”地址。

Hi=(H(key)+di)%m,

di是增量序列，

(i=1，2，…，k，且k≤m-1)根据d

的取值不同，开放地址法又可分为：(Ⅰ)线性探测再散列：

di=1，2，3，…，m-1(Ⅱ)二次探测再散列：

di=12，-12，22，-22，…，k2此时：Hi=(H(key)+m+di)%m,(Ⅲ)随机探测再散列

di=伪随机序列6利用下面的公式求“下一个”地址。6012345678910012345678910例如:关键字集合{19,01,23,14,55,68,11,82,36}设定哈希函数

：H(key)=key%11

(表长=11)191011232141551683191011232141684若采用线性探测再散列处理冲突若采用二次探测再散列处理冲突11682236555111382136270123在查找概率相同的情况下，查找成功时的ASLASLsucc

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

=(1*5+2*2+3+4)/9=16/9查找不成功时的ASLASLunsucc=()/11=/11若采用二次探测再散列处理冲突0123456789101910112321416845511138213629在查找概率相同的情况下,若采用二次探测再散列处理冲突0线性探测再散列的优点：只要哈希表未满，总能找到一个空地址。缺点：会产生二次聚集。

7019331801…56789…1210线性探测再散列的优点：二、链地址法在哈希表的每一个单元中存放一个指针，将所有的同义词连成一个链表。假设哈希地址在区间[0..m-1]上，则哈希表为一个指针数组。typedefstructnode{//定义链表中结点

KeyTypekey；

其它成员；

structnode*next；

}Node，*Nodeptr； typedefNodeptr

chainhash[m]；//定义指针数组11二、链地址法110123456111982685514013623ASLsucc=(6×1+2×2+3)/9=13/9例1:关键字集合{19,01,23,14,55,68,11,82,36}哈希函数H(key)=key%7

(表长=7)ASLunsucc=(4×1+1×2+3)/7=9/7120111982685514013623ASLs例2：有一组关键字{BITE,EACH,BITTER,BROOM,AND,ALSO,HASH,EGGS}，现以关键字中第一个字母在字母表中的位置为该关键字的哈希函数值，链地址哈希表如下：ASLsucc=(4*1+3*2+1*3)/8=13/8

1

ANDALSO2BITEBITTERBROOM┇5EACHEGGS┇8HASH┇2613例2：有一组关键字{BITE,EACH,BITTER,四、建立一个公共溢出区设向量hashtable[m]为基本表。另设向量overtable[V]为溢出表。所有与基本表中关键字为同义词的记录都填入溢出表例：关键字表(a，d，e，f，d1，d2，f1，g)，表长m=11，H(key)=i1%11；i1为首字母在字母表中的位置。012345678910基本表ad012345678910溢出表efd1d2f1g14四、建立一个公共溢出区例：关键字表(a，d，e，f，d19.3.4哈希表的查找及分析一.哈希表的查找查找过程和建立哈希表的过程基本一致。(1)计算哈希地址。(2)相应地址上没有记录，则查找不成功。(3)相应地址上有记录，则比较关键字，①若和给定值相等，则查找成功。②不相等，则根据造表时设定的处理冲突的方法找“下一地址”，直到哈希表中某个位置为空或者表中的关键字与给定值相同为止。159.3.4哈希表的查找及分析一.哈希表的查找15inthashsrch(hashtable

shtable，KeyTypek){//已知hash函数为hash(key),散列表的表长为m，地址序列//Hi=(hash(key)+di)%m,di=1,2,…,m-1

j=hash(k)；if(shtable[j]==nullrecd)return(0)；elseif(shtable[j].key==k)return(j)；

else

do{

j=(j+1)%m；}

//线性探测再散列while(shtable[j].key≠k

&&

shtable[j]≠nullrecd)if(shtable[j]==nullrecd)return(0)；elsereturn(j)；}}

//hashsrch

16inthashsrch(hashtableshtable二.分析比较次数取决于三个因素：哈希函数、处理冲突的方法、哈希表的装填因子

在一般情况下，处理冲突方法相同的哈希表，其平均查找长度依赖于哈希表的装填因子。(1)查找成功时的平均查找长度①线性探测ASLl≈②随机探测、二次探测ASLr≈③链地址法ASLc≈

17二.分析(1)查找成功时的平均查找长度17例：已知一个含有100个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈希表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过3。

ASLl=≤3，(1)用线性探测再散列处理冲突建立散列表存储则由：ASLl

≤3，可求出求得≤4/518例：已知一个含有100个记录的表，关键字为中国人姓氏的拼音，(3)关键字分析：开头a-z，最长6位。选择hash函数：

hash(key)=5*(i-1)+L其中，i为第一个字母在字母表中的序号，L为关键字的长度。(2)设表长：由=记录长度n/表长m,表长m=n/≥(100*5)/4=125取表长m=13319(3)关键字分析：开头a-z，最长6位。(2)设表长：由9.3、9.9、9.13、9.14、9.19、9.21作业209.3、9.9、9.13、9.14、9.19、哈希表的基本思想:“一次”查找成功。关键字集合映射函数H地址空间H(key)ASL的T(n)=O(1)。通常设定一个一维数组空间存储记录集合，则H(key)指示数组中的下标。称这个一维数组为哈希(Hash)表或散列表。称映射函数H为哈希函数。H(key)为哈希地址9.3.1什么是哈希表9.3哈希表21哈希表的基本思想:关键字集合映射函数H地址空间H(key一、直接地址法取关键字或关键字的某个线性函数值为哈希地址即：H(key)=key或：H(key)=a*key+b其中，a，b为常数。常用的构造哈希(散列)函数的方法：假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,…,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。二、数字分析法22一、直接地址法常用的构造哈希(散列)函数的方法：假设四、折叠法将关键字分割成位数相同的几部分，然后将这几部分叠加，舍去进位作为哈希地址。移位叠加：将分割之后的每一部分的最低位对齐，然后相加。间界叠加：从一端向令一端沿分割界来回折叠，然后相加。三、平方取中法将k平方后的中间几位取为哈希地址。位数由表长决定23四、折叠法三、平方取中法3五、除留余数法当关键字k为整数时，用关键字除以一个整数p所得余数作为哈希的地址。

H(key)=key%p24五、除留余数法49.3.3处理冲突的方法设hash表的长度为m，冲突是指j=H(K)的位置已有记录，(0≤j≤m-1)“处理冲突”——为K另找一个“空”的地址。一.开放地址法：哈希表的存储结构：typedefstruct{KeyType

key；

//关键字成员

…；

//其它成员

}elemtypetypedef

elemtype

hashtable[m]

；259.3.3处理冲突的方法设hash表的长度为m，冲突是利用下面的公式求“下一个”地址。

Hi=(H(key)+di)%m,

di是增量序列，

(i=1，2，…，k，且k≤m-1)根据d

的取值不同，开放地址法又可分为：(Ⅰ)线性探测再散列：

di=1，2，3，…，m-1(Ⅱ)二次探测再散列：

di=12，-12，22，-22，…，k2此时：Hi=(H(key)+m+di)%m,(Ⅲ)随机探测再散列

di=伪随机序列26利用下面的公式求“下一个”地址。6012345678910012345678910例如:关键字集合{19,01,23,14,55,68,11,82,36}设定哈希函数

：H(key)=key%11

(表长=11)191011232141551683191011232141684若采用线性探测再散列处理冲突若采用二次探测再散列处理冲突116822365551113821362270123在查找概率相同的情况下，查找成功时的ASLASLsucc

=(1*4+2*2+3+5+6)/9=22/9查找不成功时的ASLASLunsucc=(9+8+7+6+5+4+3+2+1)/11=56/11若采用线性探测再散列处理冲突012345678910191011232141551683116822365平均查找长度ASL：28在查找概率相同的情况下，若采用线性探测再散列处理冲突0在查找概率相同的情况下,查找成功时的ASLASLsucc

=(1*5+2*2+3+4)/9=16/9查找不成功时的ASLASLunsucc=()/11=/11若采用二次探测再散列处理冲突01234567891019101123214168455111382136229在查找概率相同的情况下,若采用二次探测再散列处理冲突0线性探测再散列的优点：只要哈希表未满，总能找到一个空地址。缺点：会产生二次聚集。

7019331801…56789…1230线性探测再散列的优点：二、链地址法在哈希表的每一个单元中存放一个指针，将所有的同义词连成一个链表。假设哈希地址在区间[0..m-1]上，则哈希表为一个指针数组。typedefstructnode{//定义链表中结点

KeyTypekey；

其它成员；

structnode*next；

}Node，*Nodeptr； typedefNodeptr

chainhash[m]；//定义指针数组31二、链地址法110123456111982685514013623ASLsucc=(6×1+2×2+3)/9=13/9例1:关键字集合{19,01,23,14,55,68,11,82,36}哈希函数H(key)=key%7

(表长=7)ASLunsucc=(4×1+1×2+3)/7=9/7320111982685514013623ASLs例2：有一组关键字{BITE,EACH,BITTER,BROOM,AND,ALSO,HASH,EGGS}，现以关键字中第一个字母在字母表中的位置为该关键字的哈希函数值，链地址哈希表如下：ASLsucc=(4*1+3*2+1*3)/8=13/8

1

ANDALSO2BITEBITTERBROOM┇5EACHEGGS┇8HASH┇2633例2：有一组关键字{BITE,EACH,BITTER,四、建立一个公共溢出区设向量hashtable[m]为基本表。另设向量overtable[V]为溢出表。所有与基本表中关键字为同义词的记录都填入溢出表例：关键字表(a，d，e，f，d1，d2，f1，g)，表长m=11，H(key)=i1%11；i1为首字母在字母表中的位置。012345678910基本表ad012345678910溢出表efd1d2f1g34四、建立一个公共溢出区例：关键字表(a，d，e，f，d19.3.4哈希表的查找及分析一.哈希表的查找查找过程和建立哈希表的过程基本一致。(1)计算哈希地址。(2)相应地址上没有记录，则查找不成功。(3)相应地址上有记录，则比较关键字，①若和给定值相等，则查找成功。②不相等，则根据造表时设定的处理冲突的方法找“下一地址”，直到哈希表中某个位置为空或者表中的关键字与给定值相同为止。359.3.4哈希表的查找及分析一.哈希表的查找15inthashsrch(hashtable

shtable，KeyTypek){//已知hash函数为hash(key),散列表的表长为m，地址序列//Hi=(hash(key