HASH GAME - Online Skill Game GET 300

　　免费在线.链地址法查找的性能分析 由于链地址法查找就是在单链表上查找，查找单链表中第一个结点的次数为1，第二个结点次数为2，其余依次类推。 平均查找长度： ASL=1+α/2 第二十九页，共五十八页，2022年，8月28日 例：给定关键字序列{11，78，10，1，3，2，4，21}，试分别用顺序查找、二分查找、二叉排序树查找、平衡二叉树查找、哈希查找(用线性探查法和拉链法)来实现查找，试画出它们的对应存储形式(顺序查找的顺序表，二分查找的判定树，二叉排序树查找的二叉排序树及平衡二叉树查找的平衡二叉树，两种哈希查找的哈希表)，并求出每一种查找的成功平均查找长度。设哈希函数为： H(k)=k mod 11，哈希表表长m=11。 第三十页，共五十八页，2022年，8月28日 顺序查找的顺序表（一维数组） 由图可得：顺序查找的成功平均查找长度为 ASL=(1+2+3+4+5+6+7+8)/8=4.5 第三十一页，共五十八页，2022年，8月28日 二分查找的判定树（中序序列为从小到大排列的有序序列） 由图可得：二分查找的成功平均查找长度为 ASL=(1+2*2+3*4+4)/8=2.625 第三十二页，共五十八页，2022年，8月28日 二叉排序树（关键字顺序已确定，该二叉排序树应唯一）如图(a)所示，平衡二叉树（关键字顺序已确定，该平衡二叉树也应该是唯一的），如图(b)所示。 由图(a)可得：二叉排序树查找的成功平均查找长度为 ASL=(1+2*2+3*2+4+5*2)/9=3.125 由图(b)可得：平衡二叉树的成功平均查找长度为 ASL=(1+2*2+3*3+4*2)/8=2.75 11 10 1 3 2 4 78 21 3 1 11 2 10 4 78 21 (a) 二叉排序树 (b) 平衡二叉树 第三十三页，共五十八页，2022年，8月28日 线性探查法解决冲突的哈希表如图所示。 由图可得：线性探查法的成功平均查找长度为 ASL=（1+1+2+1+3+2+8+1）/8=2.375 第三十四页，共五十八页，2022年，8月28日 链地址法解决冲突的哈希表如图所示。 由图可得：链地址法的成功平均查找长度为 ASL=(1*6+2*2)/8=1.25 第三十五页，共五十八页，2022年，8月28日 小结 1. 掌握查找的基本概念； 2. 熟练掌握静态查找表的查找算法思想并灵活应用； 3. 熟练掌握动态查找表的特点以及二叉排序树、平衡二叉树的各种操作思想 4. 了解B-、B+树的概念及插入和删除操作； 5. 熟练掌握哈希表的基本概念、哈希函数的构造方法和解决冲突的方法，并能计算平均查找长度。 第三十六页，共五十八页，2022年，8月28日 第10章 内部排序 10.1 排序的基本概念 10.2 插入排序 10.3 交换排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 10.7 各种内部排序方法的比较 第三十七页，共五十八页，2022年，8月28日 10.1 排序的基本概念 1.排序 设含有n个记录的文件｛R1，R2，…Rn｝，相应的关键字为｛K1，K2，…Kn｝，需确定一种排列P(1),P(2)…P(n)使其相应的关键字满足递增(或递减)关系： KP(1)≤KP(2)≤…KP(n) 或 KP(1)≥KP(2)≥…KP(n) 使上述文件成为一个按其关键字线) ，…RP(n)｝，这种运算就称为排序。 将数据元素的无序序列调整为有序序列的过程。 第三十八页，共五十八页，2022年，8月28日 2.排序算法的稳定性 排序码（Key） 作为排序依据的记录中的一个属性。它可以是任何一种可比的有序数据类型，它可以是记录的关键字，也可以是任何非关键字。 如果待排序的序列中，存在多个具有相同排序码的数据元素，若经过排序这些数据元素的相对次序保持不变，则称这种排序算法是稳定的，若经过排序，这些数据元素的相对次序发生了改变，则称这种排序算法是不稳定的。 第三十九页，共五十八页，2022年，8月28日 3.内部排序与外部排序 内部排序 指当文件的数据量不太大时，全部信息放内存中处理的排序方法。外部排序 当文件的数据量较大时，排序过程中需要在内、外存之间不断地进行数据交换才能达到排序的目的，这种排序称为外排序。 第四十页，共五十八页，2022年，8月28日 4.内部排序的方法 内部排序的过程是一个逐步扩大记录的有序序长度的过程。在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。使有序区中记录的数目增加一个或几个的操作称为一趟排序。 内部排序的方法很多，每种方法都有各自的优缺点，适合在不同的环境(如记录的初始排列状态等)下使用。 第四十一页，共五十八页，2022年，8月28日 数据结构第讲哈希表和插入排序 第一页，共五十八页，2022年，8月28日 9.3.1 什么是哈希表 哈希表技术的主要目标是提高查找效率。 1. 哈希函数： 根据关键字直接计算出元素所在位置的函数。 例：设哈希函数为：H(K)=K/3+1，则构造关键字序列为 1、2、5、9、11、13、16、21、27 的散列表（哈希表）为： 序号 1 2 3 4 5 6 7 8 9 10 H(K) 1 5 9 13 16 21 27 2 11 第二页，共五十八页，2022年，8月28日 2.冲突 两个不同的关键字具有相同的存储位置。 序号 1 2 3 4 5 6 7 8 9 10 H(K) 1 5 9 13 16 21 27 2 11 第三页，共五十八页，2022年，8月28日 3.哈希表 根据设定的哈希函数 H(key) 和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表便称为哈希表，这一映象过程称为哈希造表或散列，所得存储位置称为哈希地址或散列地址。 第四页，共五十八页，2022年，8月28日 在哈希存储中，若发生冲突，则必须采取特殊的方法来解决冲突问题，才能使哈希查找能顺利进行。虽然冲突不可避免，但发生冲突的可能性却与三个方面因素有关。 (1)装填因子α； 装填因子是指哈希表中己存入的元素个数 n 与哈希表的大小 m 的比值，即α=n/m（α=1）。 α越小，发生冲突的可能性越小，反之，发生冲突的可能性就越大。但是，α太小又会造成大量存贮空间的浪费，因此必须兼顾存储空间和冲突两个方面。 (2)所构造的哈希函数; (3)解决冲突的方法。 第五页，共五十八页，2022年，8月28日 ① 构造好的哈希函数，使冲突尽可能的少 ② 设计有效的解决冲突的方法 第六页，共五十八页，2022年，8月28日 第9章 查找 9.1 静态查找表 9.2 动态查找表 9.3 哈希表 9.3.1 什么是哈希表 9.3.2 哈希函数的构造方法 9.3.3 处理冲突的方法 9.3.4 哈希表的查找及其分析 第七页，共五十八页，2022年，8月28日 9.3.2 哈希函数的构造方法 例：关键码集合为{ 100，300，500，700，800，900 }， 选取哈希函数为 Hash(key)=key/100，则存储结构（哈希表）如下： 1.直接定址法 取关键字或关键字的某个线性函数值为散列地址，即（K）=K 或 H（K）=a * K + b（其中a、b为常数）。 0 1 2 3 4 5 6 7 8 9 900 800 700 500 300 100 优点：以关键码 key 的某个线性函数值为哈希地址，不会产生冲突。 缺点：要占用连续地址空间，空间效率低。 第八页，共五十八页，2022年，8月28日 2.除后余数法 取关键字被不大于散列表表长 m 的数 p 除后所得的余数为哈希函数。即 H（K）=K mod p （p≤m） 经验得知：一般可选p为质数或不包含小于20的质因素的合数。 3.平方取中法 取关键字平方后的中间几位为哈希函数。因为中间几位与数据的每一位都相关。 例：2589的平方值为6702921，可以取中间的029为地址。 第九页，共五十八页，2022年，8月28日 选用关键字的某几位组合成哈希地址。 选用原则应当是：各种符号在该位上出现的频率大致相同。 3 4 7 0 5 2 4 3 4 9 1 4 8 7 3 4 8 2 6 9 6 3 4 8 5 2 7 0 3 4 8 6 3 0 5 3 4 9 8 0 5 8 3 4 7 9 6 7 1 3 4 7 3 9 1 9 例：有一组（例如80个）关键码，其样式如下： 讨论： ① 第1、2位均是“3和4”，第3位也只有“ 7、8、9”，因此，这几位不能用，余下四位分布较均匀，可作为哈希地址选用。 位号：① ② ③ ④ ⑤ ⑥ ⑦ ② 若哈希地址取两位（因元素仅80个），则可取这四位中的任意两位组合成哈希地址，也可以取其中两位与其它两位叠加求和后，取低两位作哈希地址。 4.数字分析法 第十页，共五十八页，2022年，8月28日 5.折叠法 是将关键字按要求的长度分成位数相等的几段，最后一段如不够长可以短些，然后把各段重叠在一起相加并去掉进位，以所得的和作为地址。 适用于：每一位上各符号出现概率大致相同的情况。 移位法：将各部分的最后一位对齐相加。 间界叠加法：从一端向另一端沿分割界来回折叠后，最后一位对齐相加。 例：元 移位法： 427＋518＋96=1041 间界叠加法： 427 518 96— 724+518+69 =1311 第十一页，共五十八页，2022年，8月28日 6. 随机数法 选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random (key)，其中random为随机函数。 通常，当关键字长度不等时采用此法构造哈希函数较恰当。 第十二页，共五十八页，2022年，8月28日 实际工作中需视不同情况采用不同的哈希函数。通常考虑的因素： (1)计算哈希函数所需时间(包括硬件指令的因素)； (2)关键字的长度； (3)哈希表的大小； (4)关键字的分布情况； (5)记录的查找频率。 第十三页，共五十八页，2022年，8月28日 第9章 查找 9.1 静态查找表 9.2 动态查找表 9.3 哈希表 9.3.1 什么是哈希表 9.3.2 哈希函数的构造方法 9.3.3 处理冲突的方法 9.3.4 哈希表的查找及其分析 第十四页，共五十八页，2022年，8月28日 9.3.3 处理冲突的方法 1.开放地址法 开放地址就是表中尚未被占用的地址，当新插入的记录所选地址已被占用时，即转而寻找其它尚开放的地址。 （1）线性探测法 设散列函数 H（K）=K mod m （m为表长），若发生冲突，则沿着一个探查序列逐个探查，那么，第i次计算冲突的散列地址为： Hi=(H(K)+di) mod m (di=1,2,…,m-1) 第十五页，共五十八页，2022年，8月28日 例 关键码集为 {47，7，29，11，16，92，22，8，3}， 设：哈希表表长为m=11； 哈希函数为Hash(key)=key mod 11； 拟用线性探测法处理冲突。建哈希表： 0 1 2 3 4 5 6 7 8 9 10 47 7 29 11 16 92 22 8 3 第十六页，共五十八页，2022年，8月28日 线性探测法的优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素； 线性探测法的缺点：可能使第i 个哈希地址的同义词存入第i+1 个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……， 因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。 可采用二次探测法或伪随机探测法，以改善“堆积”问题。 第十七页，共五十八页，2022年，8月28日 1.开放地址法 （2）二次探测法 二次探测法对应的探查地址序列的计算公式为： Hi = ( H(k)+di ) mod m 其中di =12,-12,22,-22,…,j2,-j2 (j≤m/2)。 第十八页，共五十八页，2022年，8月28日 0 1 2 3 4 5 6 7 8 9 10 11 22 3 47 92 16 7 29 8 若di＝伪随机序列，就称为伪随机探测法 例 关键码集为 {47，7，29，11，16，92，22，8，3}， 设：哈希表表长为m=11； 哈希函数为Hash(key)=key mod 11； 拟用二次探测法处理冲突。建哈希表如下： Hi = ( H(k)+di ) mod m 其中di =12,-12,22,-22,…,j2,-j2 (j≤m/2) 第十九页，共五十八页，2022年，8月28日 2.链地址法 优点：插入、删除方便。 缺点：占用存储空间多。 基本思想： 将具有相同哈希地址的记录链成一个单链表，m个哈希地址就设 m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。 第二十页，共五十八页，2022年，8月28日 例：设{ 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 }的哈希函数为：Hash(key)=key mod 11，用拉链法处理冲突，建表。 0 1 2 3 4 5 6 7 8 9 10 22 11 89 3 47 37 92 29 7 16 50 8 10 ? ? ? ? ? ? ? ? ? ? ? 有冲突的元素可以插在表尾,也可以插在表头。 第二十一页，共五十八页，2022年，8月28日 3.再哈希法 Hi= RHi(key) RHi 均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。不易产生“聚集”，但是增加了计算时间。 4.建立一个公共溢出区 第二十二页，共五十八页，2022年，8月28日 第9章 查找 9.1 静态查找表 9.2 动态查找表 9.3 哈希表 9.3.1 什么是哈希表 9.3.2 哈希函数的构造方法 9.3.3 处理冲突的方法 9.3.4 哈希表的查找及其分析 第二十三页，共五十八页，2022年，8月28日 9.3.4 哈希表的查找及其分析 散列表的目的主要是用于快速查找。 在建表时采用何种散列函数及何种解决冲突的办法，在查找时，也采用同样的散列函数及解决冲突的办法。 第二十四页，共五十八页，2022年，8月28日 例：设有一组关键字{ 19, 01, 23, 14, 55, 20, 84, 27, 68, 11, 10, 77 }，采用哈希函数为： H（k）=k mod 13。采用开放地址的线性探测法解决冲突，试在0～18的散列地址空间中，对该关键字序列构造哈希表。 解：依题意 m=19，得到线性探测法对应的探查地址序列计算公式为： di=(H(k)+j) mod 19; j=1,2,……,18 其计算函数如下： 第二十五页，共五十八页，2022年，8月28日 H(19)=19 mod 13=6 H(01)=01 mod 13=1 H(23)=23 mod 13=10 H(14)=14 mod 13=1 (冲突) H(14)=(1+1) mod 19=2 H(55)=55 mod 13=3 H(20)=20 mod 13=7 H(84)=84 mod 13=6 (冲突) H(84)=(6+1) mod 19=7 (冲突) H(84)=(6+2) mod 19=8 H(27)=27 mod 13=1（冲突） H(27)=(1+1) mod 19=2 (冲突) H(27)=(1+2) mod 19=3 (冲突) H(27)=(1+3) mod 19=4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 {19,01,23,14,55,20,84,27,68,11,10,77} 01 23 14 55 20 84 27 77 10 11 68 … … 第二十六页，共五十八页，2022年，8月28日 哈希查找的性能分析 哈希查找按理论分析，它的时间复杂度应为O(1)，它的平均查找长度应为ASL=1，但实际上由于冲突的存在，它的平均查找长度将会比1大。下面将分析几种方法的平均查找长度。 第二十七页，共五十八页，2022年，8月28日 1.线性探查法的性能分析 由于线性探查法解决冲突是线性地查找空闲位置的，平均查找长度与表的大小m无关，只与所选取的哈希函数H及装填因子α的值和该处理方法有关。 这时的成功的平均查找长度为： ASL= (1+1/(1-α))/2 第二十八页，共五十八页，2022年，8月28日