数据结构中查找表.ppt

9.3.2 构造哈希函数的几种方法 9.3.2.4 直接法（Direct method） 直接法就是每一个键值对应一个存储空间，而不经过任何的数学运算动作。 例如：公司中有一百个员工，而员工编号介于1到100，直接法就是员工的编号即为数据的位置，编号1员工的数据在数据中的第一笔、编号2员工的数据在数据中的第二笔……，依次类推 直接法适用于键值较小的数据，而杂凑法大部分是用在将数值范围较大的键值，对应于少数的存储空间，以增加查找的速度，减少存储空间的浪费。 9.3.2 构造哈希函数的几种方法 学生学号 学生姓名 001 林坤忠 002 江明松 003 … … 007 黄国瑜 008 叶一萱 009 叶乃菁 … 100 梁郁伦 1 2 3 … 7 009 9 … 100 杂凑函数 001 007 009 001 007 键值 数据位置 直接法 9.3.2 构造哈希函数的几种方法 9.3.2.5 减去法（Subtraction method） 减去法就是数据的键值减去一个特定的数值，以求得数据存储的位置。 例如：公司中有100个员工，而员工编号介于1001到1100，减去法就是员工的编号减去1000后即为数据的位置，编号1001员工的数据在数据中的第1笔、编号1002员工的数据在数据中的第2笔……，依次类推。因为编号1000以前的并没有数据，所有的员工编号皆从1001开始编号。 9.3.2 构造哈希函数的几种方法 学生学号 学生姓名 001 林坤忠 002 江明松 003 … … 007 黄国瑜 008 叶一萱 009 叶乃菁 … 100 梁郁伦 1 2 3 … 7 1009 9 … 100 杂凑函数 1001 1007 009 001 007 键值 数据位置 减去法 9.3.2 构造哈希函数的几种方法 9.3.2.6 数值抽出法（Digit-Extraction） 数值抽出法就是将数据的键值中的某几位数取出后作为数据存储的位置，例如，数据的键值为一组6位数的号码，我们假设键值中的第1位、第2位、第5位数作为数据位置的索引值。 9.3.2 构造哈希函数的几种方法 学生学号 学生姓名 005308 林坤忠 120567 江明松 … … 298431 黄国瑜 … … … … 303976 梁郁伦 303976 杂凑函数 (抽出1,2,5位) 120567 298431 307 126 293 键值 数据位置 数值抽出法 0 … 126 … 293 … 307 … … 9.3.2 构造哈希函数的几种方法 原键值 旋转过程 旋转后的新键值 5062101 5062101 1506210 5062102 5062102 2506210 5062103 5062103 3506210 5062104 5062104 4506210 5062105 5062105 5506210 9.3.2.7 旋转法（Rotation method） 旋转法是将数据的键值中进行旋转，旋转法通常并不直接使用在杂凑函数上，而是搭配着其他杂凑函数使用。 例如有一组6位数的键值，将最后一位数，旋转后放置在第一位数，其余的往右移。 9.3.2 构造哈希函数的几种方法 9.3.2.8 伪随机数法（Pseudo-random method） 伪随机数法是将数据的键值经过伪随机数法的运算后的结果作为数据存储的位置，其公式如下：Y=( a * key + c ) modulo 数组的大小 如键值为321547，数组大小为107，取a=13，c=5，则: Y=（13*321547+5）%107=4180116%107=54 取54作为数据存储的位置。 9.3.3 处理冲突的方法和建表实例 当我们由一个关键字计算出一个地址i时，能否立即按该地址将相应记录入哈希表呢？当然，第i桶未存满（即桶中结点数小于w），存入相应记录是毫无疑义的，但如果这时第i桶已满，我们就把这种情况称为“冲突”把产生冲突时，当前未存入的记录称为关于所选哈希函数的同义词，由于关键字的集合比较大，它的元素包括所有可能的关键字，而地址集合中的元素仅为哈希表中的地址中的地址值，所以在一般情况下，哈希函数是一个压缩映像，因此，冲突是必不可免的，在用哈希表造表之前，不仅要首先分配好哈希表的存储空间，选取好哈希函数，还必须要选取好处理冲突的方法，即如何存储同义词的问题，通常，同义词可以存放在基本区中未占用的空间中，也可以存放在基本区以外另外开辟的存储区中，这个另开辟的空间称为“溢出区”，还可以使用链地址法为同义词动态分配空间，并把哈希地址相同的同义词链入一条链表中。 9.3.3 处理冲突的方法和建表实例 常见的解决哈希冲突的方法： 1. 开放地址法 （1）线性探测再散列