哈希游戏- 哈希游戏平台- 哈希游戏官方网站

　　本课内容 一 .理解Hash查找的思想和相关概念: 哈希函数 冲突和冲突处理方法 二次聚集 二.掌握哈希表的构造 根据给定的哈希函数和冲突处理方法构造哈希表 求平均查找长度 9. 6 哈希(散列)查找 基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。 例 30个地区的各民族人口统计表 以编号作关键字， 构造哈希函数：H(key)=key H(1)=1 ， H(2)=2 以地区作关键字，取地区 名称第一个拼音字母的序号 作哈希函数：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19 编号 省、市(区) 总人口 汉族 回族 …... 1 北京 2 上海 …... …... 9.6.1 基本概念 1. 哈希函数：在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。 哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象。可写成： addr(ai)=H(ki) ， 其中ai是表中一个元素， ki是ai的关键字。 addr(ai)是ai的地址， 9.6.1 基本概念 2. 哈希表： 是应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址构成的查找表。 哈希查找(又叫散列查找)：利用哈希函数进行查找的过程叫哈希查找。 哈希表的建立过程也是通过查找进行的. 3. 冲突：对于不同的关键字ki、kj，若ki?kj，但H(ki)=H(kj)的现象叫冲突(collision) 。 同义词：具有相同函数值的两个不同的关键字，称为该哈希函数的同义词。 哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；当冲突发生时，应该有处理冲突的方法。 9.6.1 基本概念 设计一个散列表应包括： 散列表的空间范围，即确定散列函数的值域； 1.构造合适的散列函数，使得对于所有可能的元素(记录的关键字)，函数值均在散列表的地址空间范围内，且出现冲突的可能尽量小； 2.处理冲突的方法。即当冲突出现时如何解决。 哈希查找要学习的内容主要包括以上2点. 9.6.1 基本概念 9.6.2 哈希函数的构造方法 哈希函数是一种映象，其设定很灵活，hash的原义为”杂凑”,只要使任何关键字的哈希函数值都落在表长允许的范围之内即可。 哈希函数“好坏”的主要评价因素有： ◆ 散列函数的构造简单； ◆ 能“均匀”地将散列表中的关键字映射到地址空间。所谓“均匀”(uniform)是指发生冲突的可能性尽可能最少。 通过经验总结出以下5种方法: 1 直接定址法 取关键字或关键字的某个线性函数作哈希地址， 即H(key)=key 或 H(key)=a·key+b(a,b为常数) 特点：直接定址法所得地址集合与关键字集合大小相等，不会发生冲突，但实际中很少使用。 原因: 许多情况下关键字的取值范围很大,可能无法事先预料. 9.6.2 哈希函数的构造方法 2 数字分析法 对关键字的取值进行分析，取关键字的若干位或组合作为哈希地址。 适用于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况。 9.6.2 哈希函数的构造方法 例： 设有80个记录，关键字为8位十进制数，哈希地址为2位十进制数。 ┇ 8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 2 8 1 3 8 7 4 2 2 8 1 3 0 1 3 6 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 8 1 3 6 8 5 3 7 8 1 4 1 9 3 5 5 ?? ? ??? ?? 分析： ? 只取8 ? 只取1 ? 只取3、4 ? 只取2、7、5 ????数字分布近乎随机 所以：取????任意两位或两位 与另两位的叠加作哈希地址 3 平方取中法 将关键字平方后取中间几位作为哈希地址。 一个数平方后中间几位和数的每一位都有关，则由随机分布的关键字得到的散列地址也是随机的。散列函数所取的位数由散列表的长度决定。这种方法适于不知道全部关键字情况，是一种较为常用的方法。 9.6.2 哈希函数的构造方法 4 折叠法 将关键字分割成位数相同的几部分(最后一部分可以不同)，然后取这几部分的叠加和作为哈希地址。 数位叠加有移位叠加和间界叠加两种。 ◆ 移位叠加：将分割后的几部分低位对齐相加。 ◆ 间界叠加：从一端到另一端沿分割界来回折迭，然后对齐相加。 适于关键字位数很多，且每一位上数字分布大致均匀情况。 9.6.2 哈希函数的构造方法 例： 设关键字为0442205864，哈希地址位数为4 。 两种不同的地址计算方法如下： 5 8 6 4 4 2 2 0 0 4 1 0 0 8 8 H(key)=0088 移位叠加 5 8 6 4 0 2 2 4 0 4 6 0 9 2 H(key)=6092 间界叠加 5 除留余数法 取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key MOD p (p?m) 是一种简单、常用的哈希函数构造方法。 这种方法的关键是p的选取，p选的不好，容易产生同义词。 p的选取的分析： ◆ 选取p=2i(p?m)：运算便于用移位来实现，但等于将关键字的高位忽略而仅留下低位二进制数。高位不同而低位相同的关键字是同义词。 ◆ 选取p=q?f (q、f都是质因数，p?m)：则所有含有q或f因子的关键字的散列地址均是q或f的倍数。 ◆ 选取p为素数或p=q?f(q、f是质数且均大于20，p?m)：常用的选取方法，能减少冲突出现的可能性。 9.6.2 哈希函数的构造方法 6 随机数法 取关键字的随机函数值作哈希地址，即H(key)=random(key) 当散列表中关键字长度不等时，该方法比较合适。 9.6.2 哈希函数的构造方法 选取哈希函数，应考虑以下因素: ◆ 计算哈希函数所需时间； ◆ 关键字的长度； ◆ 哈希表长度（哈希地址范围）； ◆ 关键字分布情况； ◆ 记录的查找频率。 9.6.3 冲突处理的方法 冲突处理： 当出现冲突时，为冲突元素找到另一个存储位置的过程。 常用的冲突处理方法有: 1 开放定址法: 包括线性探测\二次探测\随机探测 2 再哈希法 3 链地址法 4 建立公共溢出区 1. 开放定址法 基本思想：当冲突发生时，形成某个探测序列；按此序列逐个探测散列表中的其他地址，直到找到给定的关键字或一个空地址(开放的地址)为止，将发生冲突的记录放到该地址中。散列地址的计算公式是： Hi(key)=(H(key)+di) MOD m，i=1, 2, …, k(k?m-1) 其中：H(key)：哈希函数；m：散列表长度； di：第i次探测时的增量序列； Hi(key) ：经第i次探测后得到的散列地址。 常用的增量序列有: 线性探测再散列和平方探测再散列 ⑴ 线性探测法 将散列表T[0 …m-1]看成循环向量。当发生冲突时，从初次发生冲突的位置依次向后探测其他的地址。 增量序列为：di=1, 2, 3, …, m-1 设初次发生冲突的地址是h，则依次探测T[h+1]，T[h+2]…，直到T[m-1]时又循环到表头，再次探测T[0]，T[1]…，直到T[h-1]。探测过程终止的情况是： ◆ 探测到的地址为空：表中没有记录。若是查找则失败；若是插入则将记录写入到该地址； ◆ 探测到的地址有给定的关键字：若是查找则成功；若是插入则失败 ◆ 直到T[h]：仍未探测到空地址或给定的关键字，散列表满。 1. 开放定址法 例1 ：设散列表长为7，记录关键字组为：15, 14, 28, 26, 56, 23，散列函数：H(key)=key MOD 7，冲突处理采用线 H(28)=28 MOD 7=0 冲突 H1(28)=1 又冲突H2(28)=2 H(26)=26 MOD 7=5 H(56)=56 MOD 7=0 冲突 H1(56)=1 又冲突 H2(56)=2 又冲突 H3(56)=3 H(23)=23 MOD 7=2 冲突 H1(23)=3 又冲突 H3(23)=4 所得到的hash表: 0 1 2 3 4 5 6 14 15 28 56 23 26 线性探测法的特点 ◆ 优点：只要散列表未满，总能找到一个不冲突的散列地址◆ 缺点：每个产生冲突的记录被散列到离冲突最近的空地址上，从而又增加了更多的冲突机会(这种现象称为冲突的“二次聚集”)。 ⑵ 二次探测法 增量序列为：di=12,-12,22,-22,32,……±k2 (k??m/2?) 上述例题若采用二次探测法进行冲突处理，则： H(15)=15 MOD 7=1 H(14)=14 MOD 7=0 ⑵ 二次探测法 增量序列为：di=12,-12,22,-22,32,……±k2 (k??m/2?) 上述例题若采用二次探测法进行冲突处理，则： H(15)=15 MOD 7=1 H(14)=14 MOD 7=0 1. 开放定址法 H(28)=28 MOD 7=0 冲突 H1(28)=1 又冲突 H2(28)=4 H(26)=26 MOD 7=5 H(56)=56 MOD 7=0 冲突 H1(56)=1 又冲突 H2(56)=0 又冲突 H3(56)=4 又冲突 H4(56)=2 H(23)=23 MOD 7=2 冲突 H1(23)=3 二次探测法的特点 ◆ 优点：探测序列跳跃式地散列到整个表中，不易产生冲突的“聚集”现象； ◆ 缺点：不能保证探测到散列表的所有地址。 14 15 56 23 28 26 0 1 2 3 4 5 6 ⑶ 伪随机探测法 增量序列使用一个伪随机函数来产生一个落在闭区间[1，m-1]的随机序列。 例2 ： 表长为11的哈希表中已填有关键字为17，60，29的记录，散列函数为H(key)=key MOD 11 。 现有第4个记录，其关键字为38，按三种处理冲突的方法，将它填入表中。 (1) H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5+2) MOD 11=7 冲突 H3=(5+3) MOD 11=8 不冲突 1. 开放定址法 (2) H(38)=38 MOD 11=5 冲突 H1=(5+12) MOD 11=6 冲突 H2=(5-12) MOD 11=4 不冲突 (3) H(38)=38 MOD 11=5 冲突 设伪随机数序列为9，则H1=(5+9) MOD 11=3 不冲突 0 1 2 3 4 5 6 7 8 9 10 60 17 29 38 38 38 构造若干个哈希函数，当发生冲突时，利用不同的哈希函数再计算下一个新哈希地址，直到不发生冲突为止。即：Hi=RHi(key) i=1, 2, …, k RHi ：一组不同的哈希函数。第一次发生冲突时，用RH1计算，第二次发生冲突时，用RH2计算…依此类推知道得到某个Hi不再冲突为止。 ◆ 优点：不易产生冲突的“聚集”现象； ◆ 缺点：计算时间增加。 2 再哈希法 方法：将所有关键字为同义词(散列地址相同)的记录存储在一个单链表中，并用一维数组存放链表的头指针。 设散列表长为m，定义一个一维指针数组： RecNode *linkhash[m]，其中RecNode是结点类型，每个分量的初值为空。凡散列地址为k的记录都插入到以linkhash[k]为头指针的链表中，插入位置可以在表头或表尾或按关键字排序插入。 3 链地址法