文章目录
散列表的基本概念散列方法（杂凑法）散列函数（杂凑函数）散列表（杂凑表）冲突使用散列表需要解决的两个问题
散列函数的构造方法构造散列函数考虑的因素构造散列函数应遵循的原则构造散列函数的常用方法直接定址法除留余数法
处理冲突的方法开放定址法（开地址法）线性探测法二次探测法伪随机探测法
链地址法（拉链法）链地址法建立散列表步骤链地址法的优点
散列表的查找实例散列表的查找效率分析小总结
散列表的基本概念
基本思想：记录的存储位置与关键字之间存在对应关系。 对应关系——hash函数。 Loc(i) = H(keyi)
散列方法（杂凑法）
选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放； 查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比对，确定查找是否成功。
散列函数（杂凑函数）
散列方法中使用的转换函数。
散列表（杂凑表）
按上述思想构造的表。 散列函数：H(key) = k
冲突
不同的关键码映射到同一个散列地址。 kei1≠key2，但是H(key1)=H(key2) 在散列查找方法中，冲突是不可能避免的，只能尽可能减少。
使用散列表需要解决的两个问题
（1）构造好的散列函数
所选函数尽可能简单，以便提高转换速度；所选函数对关键码计算出的地址，应在散列地址集中致均匀分布，以减少空间浪费。
（2）制定一个好的解决冲突的方案 查找时，如果从散列函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律地查询其它相关单元。
散列函数的构造方法
构造散列函数考虑的因素
执行速度（即计算散列函数所需时间）；关键字的长度；散列表的大小；关键字的分布情况；查找频率。
构造散列函数应遵循的原则
要求一：n个数据原仅占用n个地址，虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小。 要求二：无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突。
构造散列函数的常用方法
直接定址法数字分析法平方取中法折叠法除留余数法随机数法
直接定址法
Hash(key) = a.key + b（a、b为常数） 优点：以关键码key的某个线性函数值为散列地址，不会产生冲突。 缺点：要占用连续地址空间，空间效率低。
例：{100, 300, 500, 700, 800, 900}，散列函数Hash(key) = key/100（a=1/100, b=0）
除留余数法
Hash(key) = key mod p （p是一个整数） 关键：如何选取合适的p？ 技巧：设表长为m，取p≤m且为质数。
例：{15, 23, 27, 38, 53, 61, 70}，散列函数Hash(key) = key mod 7
处理冲突的方法
开放定址法（开地址法）链地址法（拉链法）再散列法（双散列函数法）建立一个公共溢出区
开放定址法（开地址法）
基本思想：有冲突时就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据元素存入。
例如：除留余数法 Hi = (Hash(key) + di) mod m ，di为增量序列。
常用方法： 线性探测法：di为1,2，…，m-1线性序列。 二次探测法：di为12，-12，22，…，q2二次序列。 伪随机探测法：di为伪随机数序列。
线性探测法
Hi = (Hash(key)+di) mod m（1≤i 一旦冲突就找下一个地址，直到找到空地址存入。 例：关键码集为{47, 7, 29, 11, 16, 92, 22, 8, 3}，散列表长度m=11；散列函数为Hash(key)=key mod 11;拟用线性探测法解决散列冲突。建散列表如下： 解释： ① 47、7均是由散列函数得到的没有冲突的散列地址； ② Hash(29)=7，散列地址有冲突，需寻找下一个空的散列地址：由H1=(Hash(29)+1) mod 11 = 8，散列地址8为空，因此将29存入。 ③ 11、16、92均是由散列函数得到的没有冲突的散列地址； ④ 另外，22、8、3同样在散列地址上有冲突，也是由H1找到空的散列地址的。 所以：平均查找长度ASL=(1+2+1+1+1+4+1+2+2)/9=1.67 二次探测法 关键码集为{47, 7, 29, 11, 16, 92, 22, 8, 3}，设散列函数为Hash(key)=key mod 11，Hi=(Hash(key)+di) mod m， 其中：m为散列表长度，m要求是某个4k+3的质数；di为增量序列12, -12, 22, -22, … ,q2 Hash(3)=3，散列地址冲突，由H1=(Hash(3)+12) mod 11 = 4，仍然冲突； H2=(Hash(3)-12) mod 11 = 2，找到空的散列地址，存入。 伪随机探测法 Hi=(Hash(key)+di) mod m （1≤i 链地址法（拉链法） 基本思想：相同散列地址的记录链成一单链表。 m个散列地址就设m个单链表，然后用一个数组将m个单链表的头指针存储起来，形成一个动态的结构。 例如：一组关键字为{19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}，散列函数为Hash(key) = key mod 13 链地址法建立散列表步骤 Step1：取数据元素的关键字key，计算其散列函数值（地址）。若该地址对应的链表为空，则将该元素插入此链表；否则执行Step2解决冲突。Step2：根据选择的冲突处理方法，计算关键字key的下一个存储地址。若该地址对应的链表不为空，则利用链表的前插法或者后插法将该元素插入此链表。 链地址法的优点 非同义词不会冲突，无“聚集”现象。链表上结点空间动态申请，更适合于表长不确定的情况。 散列表的查找 给定值查找值k，查找过程： ① 给定待查找的关键字key, 根据造表时设定的散列函数计算H0=H(key)。 ② 若单元H0为空， 则所查元素不存在。 ③ 若单元H0中元素的关键字为key, 则查找成功。 ④ 否则重复下述解决冲突的过程： • 按处理冲突的方法， 计算下一个散列地址Hi; • 若单元Hi为空， 则所查元素不存在； • 若单元Hi中元素的关键字为key, 则查找成功。 #define NULLKEY 0 // 单元为空的标记 int SearchHash(HashTable HT,KeyType key) { //在散列表 HT中查找关键字为key的元素，若查找成功， 返回散列表的单元标号，否则返回-1 H0=H(key); // 根据散列函数H (key)计算散列地址 if(HT[H0].key==NULLKEY) return -1; // 若单元H0为空， 则所查元素不存在 else if(HT[H0].key==key) return H0; // 若单元HO中元素的关键字为key, 则查找成功 else { for(i=1;i { Hi=(H0+i)%m; // 按照线性探测法计算下一个散列地址Hi if(HT[Hi].key==NULLKEY) return -1; //若单元Hi为空， 则所查元素不存在 else if(HT[Hi].key==key) return Hi; // 若单元Hi中元素的关键字为key, 则查找成功 } return -1; } } 实例 已知一组关键字(19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79)散列函数为：H(key)=key MOD 13，散列表长度为m=16，设每个记录的查找概率相等。 散列表的查找效率分析 使用平均查找长度ASL来衡量查找算法，ASL取决于 散列函数处理冲突的方法散列表的装填因子α α = 表中填入的记录数/哈希表的长度 α越大，表中记录数越多，说明表装得越满，发生冲突的可能性就越大，查找时比较次数就越多。 小总结 散列表技术具有很好的平均性能，优于一些传统的技术。链地址法优于开地址法。除留余数法作散列函数优于其他类型函数。 参考链接
发表评论