高级程序员-数据结构

，如果同时存在关键字 Zhou，则上述函数不可取。 换句话说，为使平均查找长度等于 0，必须找到一个能将查找表中所有关键字都能“散列” 在表中不同位置的哈希函数。 若两个关键字不同 key1 ≠ key2，而哈希函数值相同 f(key1) = f(key2)，则称这两个关键字(对 于该哈希函数 f 而言)为“同义词”，并称这种现象为“冲突”。 因此，虽然哈希函数的设定很灵活，但对于动态查找表很难找到不存在同义词的哈希函数， 原因是，一是表长不确定，二是通常哈希函数是一个压缩映象。 由此冲突很难避免，唯一弥补的办法是，在发生冲突时设法解决，例如将关键字 Zhou 存 入表中地址为 0 的空位中等。 哈希表的定义: 根据设定的哈希函数 H(key) 和选择的处理冲突的方法，将一组关键字映象到一个有限的、 地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位 置，称这种表为哈希表，这一映象的过程亦被称为“散列”。 因此，为构造哈希表，应解决两个问题: 1. 选择一个“好的”(尽可能少产生冲突) 哈希函数; 2. 找到一种恰当“处理冲突” 的方法。 若对于关键字集合中的任意一个关键字，经哈希函数映象到地址集合中任何一个地址的概率 相等，则称此类哈希函数为均匀的哈希函数。 对数值型的关键字，常用的构造均匀的哈希函数的方法有如下几种: 一、直接定址法 取关键字本身或关键字的某个线性函数作为哈希函数。即 Hash(key) = key 或 Hash(key)=a×key + b ( a 和 b 均为常数 ) 直接定址所得地址集的大小和关键字集的大小相同，关键字和地址一一对应，决不会产生 冲突。 二、数字分析法 如果可能出现的关键字的数位相同，且取值事先知道，则可对关键字进行“数字分析”， 取其中“分布均匀”的若干数位或它们的组合作为哈希函数值。 三、平方取中法 如果关键字的所有各位分布都不均匀，则可对关键字进行“平方取中”，即取关键字的平 方值的中间若干位作为哈希函数值。由于一个数的平方值的中间几位数能受到该数所有位的 影响，将使随机分布的关键字得到的哈希函数值也随机。 四、折叠法 若关键字的位数很多，且每一位上数字分布大致均匀，则可对它们进行移位叠加或间界叠加， 取其叠加和为哈希函数值。 移位叠加是将分割后的每一部分的最低位对齐，然后相加；间界叠加是从一端向另一端沿分 割界来回折叠，然后对齐相加。 例如，key = 110 108 380 428 895， 则其移位叠加得到的哈希地址为 921，间界叠加得到的哈希地址为 010。(哈希表的表长为 1000) 五、除留余数法 以关键字被某个数 p 除后所得余数作为哈希函数值。即 Hash(key) = key MOD p 其中，MOD表示“取模”运算，p 为不大于表长的素数或不包含小于 20 的质因素的合数。 六、随机数法 当关键字不等长时，可取关键字的某个伪随机函数值作为哈希函数值。 Hash(key) = random(key) 对于非数值型关键字，则需先将它们转化为数字。 实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的 范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。 处理冲突的方法： 一、开方定址法 构造一个地址序列: ( )( ) 1,2, , ( 1i iH H key d MOD m i s s m= + = ≤L )− 为产生冲突的关键字找“下一个”地址，直至找到表中一个当前尚空闲的位置为止。 www.ccidedu.com www.ccidedu.com (1）di = 1，2，3，…，m-1 ⎯ 线性探测再散列 例如: {19，56，23，14，68，82，70，36，91}， 哈希表的表长为 11，哈希函数为 Hash(key)=key % 11 0 1 2 3 4 5 6 7 8 9 10 56 23 14 68 82 70 36 19 91 (2）di = 1^2，-1^2，2^2，-2^2，…，±k^2（k≤m/2）⎯⎯平方(二次)探测再散列 0 1 2 3 4 5 6 7 8 9 10 56 23 14 70 82 68 36 19 91 (3）di 为伪随机数列或者 di=i×H2(key) ⎯⎯ 伪随机探测再散列 或 双散列函数探测 假设 di = i × ( (3key)%10 + 1 ) 0 1 2 3 4 5 6 7 8 9 10 23 56 68 14 70 82 91 19 36 二、链地址法 将所有关键字为“同义词”的记录链接在一个线性链表中。 例如，假设同上例关键字序列，哈希表的表长为 7， 哈希函数为 Hash(key)=key % 7 在开放定址处理冲突构建的哈希表中进行查找时，首先计算给定值的哈希函数值， 若表中该位置上没有记录，则表明关键字等于给定值的记录不存在； www.ccidedu.com 若该位置上的记录的关键字和给定值不等，则依据建表时设定的增量值寻找“下一个”地址， 直至某个位置上的记录的关键字等于给定值; 或者是一个没有记录的位置。 该地址恰为新记录的插入位置。 在链地址处理冲突构建的哈希表中进行查找时，首先计算给定值的哈希函数值， 若表中该位置上为空指针，则表明关键字等于给定值的记录不存在； 否则顺着指针进行查找，直至某个节点内的记录的关键字等于给定值; 或者确定该链表中不存在关键字等于给定值的记录。 则可将新记录插入在链表中。 可见，无论查找成功与否，哈希表的平均查找长度都不为零。 在等概率查找的假设下，前述四个例子的平均查找长度分别为: 24/9，20/9，13/9，18/9。 一般情况下，在哈希函数为“均匀”的前提下，哈希表的平均查找长度仅取决于处理冲突 的方法和哈希表的装填因子。 哈希表的装填因子 α 定义为: 在等概率查找的情况下，可以证明不同处理冲突方法构建的哈希表在查找成功时的平均查找 长度分别为 : 线性探测再散列: 随机(或平方)探测再散列: 链地址处理冲突: α = 表中记录数哈希表的表长 1 11 2 1nl S α ⎛ ⎞≈ +⎜ ⎟−⎝ ⎠ 1 ln(1 )nrS αα≈ − − 1 2nc S α≈ + 由此可见，由于哈希表的平均查找长度不是 n 的函数，而是 α 的函数，因此虽然不能做 到平均查找长度为 0，但可以设计一个哈希表，使它的平均查找长度控制在一个期望值之内。 首先选定一种处理冲突的方法，利用公式估算表长; 然后设计一个“均匀”的哈希函数。 对开放定址的哈希表，删除表中记录时， 必须在该记录所在位置作一特殊标记，同时需修改前述查找算法添加识别已被删除记录。 www.ccidedu.com 数据结构 数据结构与抽象数据类型 逻辑结构、存储结构综述 线性结构 顺序表： 有序表： 栈 队列 数组 广义表 非线性结构 排序 直接插入排序 折半插入排序 表插入排序 希尔排序 起泡排序 快速排序 简单选择排序 堆排序 性能分析 时间性能分析 空间性能分析 排序方法的稳定性能 时间复杂度 查找表 顺序表 有序表 二叉查找树(二叉排序树) 平衡二叉(查找)树 哈希表