3.2.1-哈希表的基本概念

《3.2.1-哈希表的基本概念》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3查找与排序技术3.1基本的查找技术3.2哈希表技术3.3基本的排序技术3.4二叉排序树及其查找3.5多层索引树及其查找3.6拓扑分类3.2哈希表技术3.2.1哈希表的基本概念3.2.2几种常用的哈希表哈希表、HashTable、散列表、杂凑表由结点的关键字k计算Hash码(散列地址)f(k)Hash表技术:关键字-地址转换法是一种存储结构,也是一种查找方法.Hash表技术的目标-提高查找效率Hash表的存储空间-一维数组3.2.1哈希表的基本概念1.直接查找技术2.Hash表3.Hash码的构造1.直接查找技术直接查找表设表的长度为n如果存在一个函数i=i(k)，对于表中的任

2、意一个元素的关键字k，满足以下条件：(1)1≤i(k)≤n;(2)对于任意的元素关键字k1≠k2,恒存在i(k1)≠i(k2)。则称此表为直接查找表.其中函数i=i(k)称为关键字k的映象函数.关键字k与表项序号i之间一一对应对直接查找表的操作(1)填入1)计算关键字k的映象函数i=i(k);2)将关键字k及有关元素信息填入到第i项.(2)取出1)计算关键字k的映象函数i=i(k);2)检查表中第i项:若为空,则表中没有关键字为k的元素;否则,取出第i项中的元素。补充例:直接查找表线性表的关键字集合:{and,begin,do,end,for,go,if,then,while}

3、直接查找表array[1..26]映象函数i(k)=ASCII(k[1])-ASCII(‘a’)+1i123456789ki101112131415161718ki1920212223242526kandbegindoendforgoifthenwhile关键字k的首字母2.Hash表例3.2:将关键字序列依次填入长度为n=12的表中,映象函数为i＝INT(k/3)＋1表项序号i123456789101112关键字k093126190113021127160521冲突:两个不同的关键字,映象函数值相同同义词:发生冲突的两个关键字.(01和02是同义词)0931261901130

4、2112716052141197151410628关键字kINT(k/3)+1设表的长度为n如果存在一个函数i=i(k),对于表中的任意一个元素的关键字k,满足以下条件:(1)1≤i(k)≤n则称此表为Hash表。其中函数i=i(k)称为关键字k的Hash码Hash表的定义比较直接查找表(1)1≤i(k)≤n(2)k1≠k2,i(k1)≠i(k2)不允许冲突存在Hash表(1)1≤i(k)≤n允许冲突存在Hash表技术的关键(1)构造合适的Hash码减少冲突即Hash码的均匀性好(2)确定解决冲突的方法Hash码i=i(k)的构造原则:(1)Hash码的均匀性好(2)Hash码

5、的计算尽量简单(3)Hash码的值域在表长的范围之内1≤i(k)≤n3.Hash码的构造(1)截段法(2)分段叠加法(3)除法(4)乘法Hash码的构造方法(1)截段法关键字0931261901130211Hash码001111010011001101010011二进制表示0100111111110101001100001011010001001011截取位数:假设hash表的长度n=8(2)分段叠加法key=58242324169,hash表长度为100058242324169+1315Hash码:315移位叠加58232424196+1243Hash码:243边界叠加(3)

6、除法(除余法)k:关键字n:hash表的长度i=mod(k,n)例:hash表的长度n=7,i=mod(k,n)关键字序列:8,16,32,64,128当mod(k,n)=0时,取i=n表项序号1234567关键字8163264128除余法的一般形式k:关键字n:hash表的长度i=mod(k,p)例:hash表的长度n=8,i=mod(k,n)关键字序列:8,16,32,64,128表项序号12345678关键字8163264128一般选p为小于或等于hash表长度n的某个最大素数(4)乘法k:关键字n:hash表的长度i=mod(k*φ,n)