hash散列表的解决冲突——开放定址法(线性探索再散列法)

第9章查找一、选择题1.顺序查找一个共有n个元素的线性表，其时间复杂度为（），折半查找一个具有n个元素的有序表，其时间复杂度为（）。

【＊，★】A.O(n)B. O(log2n)C. O(n2)D. O(nlog2n)2.在对长度为n的顺序存储的有序表进行折半查找，对应的折半查找判定树的高度为（）。

【＊，★】A.nB. ⌊log2n⌋C. ⌊log2(n+1)⌋D. ⌈log2(n+1)⌉3.采用顺序查找方式查找长度为n的线性表时，平均查找长度为（）。

【＊】A.nB. n/2C. (n+1)/2D. (n-1)/24.采用折半查找方法检索长度为n的有序表，检索每个元素的平均比较次数（）对应判定树的高度（设高度大于等于2）。

【＊＊】A.小于B. 大于C. 等于D. 大于等于5.已知有序表（13，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，查找成功的比较次数为（）。

【＊】A. 1B. 2C. 3D. 46.对线性表进行折半查找时，要求线性表必须（）。

【＊】A.以顺序方式存储B. 以链接方式存储C.以顺序方式存储，且结点按关键字有序排序D. 以链接方式存储，且结点按关键字有序排序7.顺序查找法适合于存储结构为（）的查找表。

【＊】A.散列存储B. 顺序或链接存储C. 压缩存储D. 索引存储8.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（）个结点最佳。

【＊＊】A.10B. 25C. 6D. 6259.从键盘依次输入关键字的值：t、u、r、b、o、p、a、s、c、l，建立二叉排序树，则其先序遍历序列为（），中序遍历序列为（）。

【＊＊，★】A.abcloprstuB. alcpobsrutC. trbaoclpsuD. trubsaocpl10.折半查找和二叉排序树的时间性能（）。

【＊】A.相同B. 不相同11.一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（）个结点。

哈希表——线性探測法、链地址法、查找成功、查找不成功的平均长度⼀、哈希表1、概念哈希表(Hash Table)也叫散列表，是依据关键码值（Key Value）⽽直接进⾏訪问的数据结构。

它通过把关键码值映射到哈希表中的⼀个位置来訪问记录，以加快查找的速度。

这个映射函数就做散列函数。

存放记录的数组叫做散列表。

2、散列存储的基本思路以数据中每⼀个元素的keywordK为⾃变量。

通过散列函数H（k）计算出函数值，以该函数值作为⼀块连续存储空间的的单元地址，将该元素存储到函数值相应的单元中。

3、哈希表查找的时间复杂度哈希表存储的是键值对，其查找的时间复杂度与元素数量多少⽆关。

哈希表在查找元素时是通过计算哈希码值来定位元素的位置从⽽直接訪问元素的，因此，哈希表查找的时间复杂度为O（1）。

⼆、经常使⽤的哈希函数1. 直接寻址法取keyword或者keyword的某个线性函数值作为哈希地址,即H(Key)=Key或者H(Key)=a*Key+b(a,b为整数),这样的散列函数也叫做⾃⾝函数.假设H(Key)的哈希地址上已经有值了,那么就往下⼀个位置找,知道找到H(Key)的位置没有值了就把元素放进去.2. 数字分析法分析⼀组数据,⽐⽅⼀组员⼯的出⽣年⽉,这时我们发现出⽣年⽉的前⼏位数字⼀般都同样,因此,出现冲突的概率就会⾮常⼤,可是我们发现年⽉⽇的后⼏位表⽰⽉份和详细⽇期的数字区别⾮常⼤,假设利⽤后⾯的⼏位数字来构造散列地址,则冲突的⼏率则会明显减少.因此数字分析法就是找出数字的规律,尽可能利⽤这些数据来构造冲突⼏率较低的散列地址.3. 平⽅取中法取keyword平⽅后的中间⼏位作为散列地址.⼀个数的平⽅值的中间⼏位和数的每⼀位都有关。

因此，有平⽅取中法得到的哈希地址同keyword的每⼀位都有关。

是的哈希地址具有较好的分散性。

该⽅法适⽤于keyword中的每⼀位取值都不够分散或者较分散的位数⼩于哈希地址所须要的位数的情况。

【学习总结】哈希表：哈希函数构造；哈希表解决地址冲突的⽅法⼩结散列函数构造⽅法：1.直接定址法：H(key) = a*key + b2.除留余数法：H(key) = key % p(p为不⼤于散列表表长，但最接近或等于表长的质数p)3.数字分析法：选取r进制数数码分布较为均匀的若⼲位作为散列地址4.平⽅取中法：取关键字的平⽅值的中间⼏位作为散列地址5.折叠法：将关键字分割成位数相同的⼏部分，然后取这⼏部份的叠加和作为散列地址处理冲突的⽅法：1.开放定址法(闭哈希表)：在冲突的哈希地址的基础上进⾏处理，得到新的地址值。

Hi = (H(key)+di) % m(m表⽰散列表表长，di为增量序列)1）线性探测法：dii=1，2，3，…，m-12）⼆次探测法：di=12，-12，22，-22，…，k2，-k2 ( k<=m/2 )冲突发⽣时，以原哈希地址为中⼼，在表的左右进⾏跳跃式探测，⽐较灵活。

3）伪随机数法：di=伪随机数序列。

具体实现时，应建⽴⼀个伪随机数发⽣器，（如i=(i+p) % m），并给定⼀个随机数做起点。

线性探测再散列的优点是：只要哈希表不满，就⼀定能找到⼀个不冲突的哈希地址，⽽⼆次探测再散列和伪随机探测再散列则不⼀定。

注：在开放定址的情形下，不能随便物理删除表中已有元素，若删除元素将会截断其他具有相同散列地址的元素的查找地址。

若想删除⼀个元素，给它做⼀个删除标记，进⾏逻辑删除。

2.链地址法、拉链法(开哈希表)将所有哈希地址为i的元素构成⼀个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因⽽查找、插⼊和删除主要在同义词链中进⾏。

链地址法适⽤于经常进⾏插⼊和删除的情况。

3.再哈希法：同时构造多个不同的哈希函数，发⽣冲突时，使⽤其他哈希函数求值。

这种⽅法不易产⽣聚集，但增加了计算时间。

4.建⽴公共溢出区：将哈希表分为基本表和溢出表两部分，凡是和基本表发⽣冲突的元素，⼀律填⼊溢出表概述哈希法⼜称散列法、杂凑法以及关键字地址计算法等，相应的表称为哈希表。

第1章绪论一、选择题1. 算法的时间复杂度取决于（ C ）A．问题的规模 B. 待处理数据的初态 C. A和B2.计算机算法指的是（C），它必须具备（B）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性3．从逻辑上可以把数据结构分为（ C ）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构4．以下与数据的存储结构无关的术语是（ D ）。

A．循环队列 B. 链表 C. 哈希表 D. 栈5．在下面的程序段中，对x的赋值语句的频度为（ C ）FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A． O(2n) B．O(n) C．O(n2) D．O(log2n)6．连续存储设计时，存储单元的地址（ A ）。

A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续二、判断题1. 数据元素是数据的最小单位。

( F ) 【山东师范大学 2001 一、1 （2分）】2. 记录是数据处理的最小单位。

( F )3．数据的物理结构是指数据在计算机内的实际存储形式。

( T )【山东师范大学2001 一、2（2分）】4. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。

( F )5. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

( F )三、填空1．数据的物理结构包括的表示和的表示。

2. 对于给定的n个元素,可以构造出的逻辑结构有（1），（2），（3），_（4）四种。

3．数据的逻辑结构是指。

4．一个数据结构在计算机中称为存储结构。

5．数据结构中评价算法的两个重要指标是6．已知如下程序段FOR i:= n DOWNTO 1 DO {语句1}BEGINx:=x+1；{语句2}FOR j:=n DOWNTO i DO {语句3}y:=y+1; {语句4}END；语句1执行的频度为（1）；语句2执行的频度为（2）；语句3执行的频度为（3）；语句4执行的频度为（4）。

第9章查找一、选择题1.顺序查找一个共有n个元素的线性表，其时间复杂度为（），折半查找一个具有n个元素的有序表，其时间复杂度为（）。

【＊，★】A.O(n)B. O(log2n)C. O(n2)D. O(nlog2n)2.在对长度为n的顺序存储的有序表进行折半查找，对应的折半查找判定树的高度为（）。

【＊，★】A.nB.C.D.3.采用顺序查找方式查找长度为n的线性表时，平均查找长度为（）。

【＊】A.nB. n/2C. (n+1)/2D. (n-1)/24.采用折半查找方法检索长度为n的有序表，检索每个元素的平均比较次数（）对应判定树的高度（设高度大于等于2）。

【＊＊】A.小于B. 大于C. 等于D. 大于等于5.已知有序表（13，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，查找成功的比较次数为（）。

【＊】A. 1B. 2C. 3D. 46.对线性表进行折半查找时，要求线性表必须（）。

【＊】A.以顺序方式存储B. 以链接方式存储C.以顺序方式存储，且结点按关键字有序排序D. 以链接方式存储，且结点按关键字有序排序7.顺序查找法适合于存储结构为（）的查找表。

【＊】A.散列存储B. 顺序或链接存储C. 压缩存储D. 索引存储8.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（）个结点最佳。

【＊＊】A.10B. 25C. 6D. 6259.从键盘依次输入关键字的值：t、u、r、b、o、p、a、s、c、l，建立二叉排序树，则其先序遍历序列为（），中序遍历序列为（）。

【＊＊，★】A.abcloprstuB. alcpobsrutC. trbaoclpsuD. trubsaocpl10.折半查找和二叉排序树的时间性能（）。

【＊】A.相同B. 不相同11.一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（）个结点。

哈希表处理冲突的方法哈希表是一种常见的数据结构，用于实现快速查找和插入操作。

它通过将关键字映射到数组的特定位置来存储数据。

然而，当两个或多个关键字映射到同一个位置时，就会发生冲突。

为了解决冲突，哈希表采用了多种方法。

1. 链地址法（Chaining）：在哈希表中的每个位置上维护一个链表或链表数组。

如果发生冲突，新的数据将被添加到链表的末尾。

这种方法可以处理任意数量的冲突，但需要额外的空间来存储链表。

2. 开放地址法（Open Addressing）：在哈希表中的每个位置上存储一个数据，并通过探测序列来处理冲突。

探测序列是一个确定的规则，用于寻找下一个可用的位置。

常见的探测方法包括线性探测（Linear Probing），二次探测（Quadratic Probing）和双重散列（Double Hashing）。

这种方法不需要额外的存储空间，但可能会导致聚集现象，即连续的冲突会增加查找的时间复杂度。

3. 再哈希法（Rehashing）：当发生冲突时，重新计算关键字的哈希值，并将数据存储在计算得到的新位置上。

这种方法需要额外的存储空间来保存原始数据，但可以避免聚集现象，并减少冲突的概率。

4. 建立公共溢出区（Primary Clustering）：将哈希表分为两个区域，一个区域用于存储主要数据，另一个区域用于存储冲突的数据。

当发生冲突时，将数据存储在冲突区域中。

这种方法可以减少聚集现象的发生，但需要额外的存储空间来存储冲突数据。

5. 完全散列（Perfect Hashing）：在构建哈希表时，通过一系列算法和数据预处理，使得每个关键字都映射到唯一的位置，从而避免冲突。

这种方法需要较高的计算成本和空间消耗，但可以实现最佳的查找和插入性能。

以上所述的方法都是常见的哈希表处理冲突的方式。

在选择合适的方法时，需要考虑数据的特点、内存限制和性能需求等因素。

哈希表处理冲突的⼏种⽅式1、链地址法指把所有的冲突关键字存储在⼀个线性链表中，这个链表由其散列地址唯⼀标识。

2、开放定址法开放地址法通常需要有三种⽅法：线性探测、⼆次探测、再哈希法。

线性探测线性探测⽅法就是线性探测空⽩单元。

当数据通过哈希函数计算应该放在700这个位置，但是700这个位置已经有数据了，那么接下来就应该查看701位置是否空闲，再查看702位置，依次类推。

当哈希表越来越满时聚集越来越严重，这导致产⽣⾮常长的探测长度，后续的数据插⼊将会⾮常费时。

线性探测就是使⽤算术取余的⽅法计算余数，当产⽣冲突时就通过线性递增的⽅法进⾏探测，⼀直到数组的位置为空，插⼊数据项即可。

⼆次探测⼆次探测是过程是x+1,x+4,x+9,以此类推。

⼆次探测的步数是原始位置相隔的步数的平⽅。

⼆次探测可以消除在线性探测中产⽣的聚集问题，但是⼆次探测还是会产⽣⼀种更明确更细的聚集。

⼆次聚集的产⽣是在⼆次探测的基础上产⽣的现象。

例如N个数据经hash函数计算后都映射到到数组下标10，探测第⼆个数字需要以⼀步长，第三个数字需要以4步长为单位，第四个数字则需要以九为步长。

好在⼆次探测并不常⽤，解决聚集问题还是有⼀种更好的办法：再哈希法。

再哈希法再哈希是把关键字⽤不同的哈希函数再做⼀遍哈希化，⽤这个结果作为步长，对指定的关键字，探测的步长是不变的，可以说不同的关键字可以使⽤不同的步长，并且步长可以控制。

⼀般来说，再哈希函数可以采⽤以下这种：stepSize=constant-(key%constant);3、再散列法当发⽣冲突时，利⽤另⼀个哈希函数再次计算⼀个地址。

直到冲突不再发⽣。

4、建⽴⼀个公共溢出区⼀旦由哈希函数得到的地址冲突，就都填⼊溢出表。

以下是列举收集来的三个题目，三个题目是同一个意思，一，利用线性探测法构造散列表(用除余法来得出散列地址，用开放地址法解决同义词问题)题目：已知一组关键字为(26，36，41，38，44，15，68，12，06，51)，用除余法构造散列函数，用线性探查法解决冲突构造这组关键字的散列表。

解答:为了减少冲突，通常令装填因子α<l。

这里关键字个数n=10，不妨取m=13，此时α≈0.77，散列表为T[0..12]，散列函数为：h(key)=key％13。

由除余法的散列函数计算出的上述关键字序列的散列地址为(0，10，2，12，5，2，3，12，6，12)。

前5个关键字插入时，其相应的地址均为开放地址，故将它们直接插入T[0]，T[10)，T[2]，T[12]和T[5]中。

当插入第6个关键字15时，其散列地址2(即h(15)=15％13=2)已被关键字41(15和41互为同义词)占用。

故探查h1=(2+1)％13=3，此地址开放，所以将15放入T[3]中。

当插入第7个关键字68时，其散列地址3已被非同义词15先占用，故将其插入到T[4]中。

当插入第8个关键字12时，散列地址12已被同义词38占用，故探查hl=(12+1)％13=0，而T[0]亦被26占用，再探查h2=(12+2)％13=1，此地址开放，可将12插入其中。

类似地，第9个关键字06直接插入T[6]中；而最后一个关键字51插人时，因探查的地址12，0，1，…，6均非空，故51插入T[7]中。

二、题目：已知一个线性表(38，25，74，63，52，48)，假定采用h(k)=k%6计算散列地址进行散列存储，若用线性探测的开放定址法处理冲突，则在该散列表上进行查找的平均查找长度为（）。

A. 1.5B. 1.7C. 2D. 2.32、解题过程：(1)计算h(k)：38%6 = 2 25%6 = 1 74%6 = 2 63%6 = 3 52%6 = 4 48%6 = 0(2)定址：把不冲突的和冲突的全部列出来即可地址：0 1 2 3 4 51、线性表第1个元素（38）：38（第1 次不冲突）2、线性表第2个元素（25）：25（第1次不冲突）3、线性表第3个元素（74）：74（第1 次冲突，地址+ 1）4、线性表第3个元素（74）：74（第2 次不冲突）5、线性表第4个元素（63）：63（第1 次冲突，地址+ 1）6、线性表第4个元素（63）：63（第2 次不冲突）7、线性表第5个元素（52）：52（第1 次冲突，地址+ 1）8、线性表第5个元素（52）：52（第2 次不冲突）9、线性表第6个元素（48）：48（第1次不冲突）经过上述定址过程，线性表中的各个元素都有了唯一的地址。

线性探测再散列https:///qq_19446965/article/details/102290770哈希表⼜称散列表。

哈希表存储的基本思想是：以数据表中的每个记录的关键字 k为⾃变量，通过⼀种函数H(k)计算出函数值。

把这个值解释为⼀块连续存储空间（即数组空间）的单元地址（即下标），将该记录存储到这个单元中。

在此称该函数H为哈希函数或散列函数。

按这种⽅法建⽴的表称为哈希表或散列表。

处理冲突的⽅法：开放寻址法：Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法：1.di=1,2,3,…, m-1，称线性探测再散列；2.di=1^2, -1^2, 2^2,-2^2, 3^2, …, ±(k)^2,(k<=m/2)称⼆次探测再散列；3.di=伪随机数序列，称伪随机探测再散列。

再散列法：Hi=RHi(key), i=1,2,…,k. RHi均是不同的散列函数，即在同义词产⽣地址冲突时计算另⼀个散列函数地址，直到冲突不再发⽣，这种⽅法不易产⽣“聚集”，但增加了计算时间；链地址法（拉链法）：将所有关键字为同义词的记录存储在同⼀线性链表中；设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，⽤⼆次探测再散列法解决冲突，则放⼊的位置是( ) 【南京理⼯⼤学 2001 ⼀、15 （1.5分）】A．8 B．3 C．5 D．9答案为A,为什么我计算出来是D呢?我的计算步骤如下:15，38，61，84⽤哈希函数H(key)=key%11计算后得地址:4,5,6,749计算后为5,发⽣冲突.⽤⼆次探测再散列法解决冲突:1:(key+1^2)%11=(49+1)%11=6,仍然发⽣冲突.2:(key-1^2)%11=(49-1)%11=4,仍然发⽣冲突.3:(key+2^2)%11=(49+4)%11=9,不再发⽣冲突.得出结果为D。

散列表冲突处理方案散列表（Hash Table）是一种重要的数据结构，它能够快速地进行插入、查找和删除等操作。

然而，在实际应用中，冲突（Collision）是散列表中常见的问题之一。

本文将介绍散列表冲突处理的几种常见方案，以及它们的优缺点。

一、开放定址法开放定址法是一种解决冲突的常见方法。

其原理是，当发生冲突时，通过一定的探测序列找到下一个可用的空槽，将待插入的元素放入该槽内。

常用的探测序列有线性探测、二次探测以及双重散列等。

1. 线性探测线性探测是最简单的开放定址法策略。

当发生冲突时，直接往后查找下一个空槽，并将待插入元素放入该槽内。

即使数组中只有少数位置被占用，线性探测也可能导致长时间的查找。

此外，线性探测容易产生一次聚集（Primary Clustering）现象，即冲突后的元素倾向于聚集在一起，进一步影响散列表的性能。

2. 二次探测二次探测对线性探测进行了改进。

当发生冲突时，根据一个二次探测序列进行查找下一个空槽，并将待插入元素放入该槽内。

二次探测的探测序列可以是平方探测、斐波那契探测等。

相比线性探测，二次探测能够减少聚集现象，但仍然存在聚集的问题。

3. 双重散列双重散列是一种更为高效的开放定址法策略。

当发生冲突时，通过计算另一个散列函数的值，并将其与原始散列值相加，得到下一个空槽的位置。

双重散列能够更好地解决聚集问题，提高散列表的性能。

二、链表法链表法是另一种常见的散列表冲突处理方案。

基本思想是，将散列得到的相同索引值的元素存储在同一个链表中。

当插入元素时，只需要将其插入到对应索引位置的链表尾部即可。

链表法对于散列冲突的处理效果较好，但在插入和查找操作上需要额外的链表遍历开销。

三、再散列法再散列法是一种结合链表法和开放定址法的冲突处理方法。

当发生冲突时，使用一个新的散列函数对待插入的元素进行再散列，并将其放入新的散列位置。

再散列法能够在一定程度上减少冲突的概率，提高散列表的性能。

综上所述，散列表冲突处理的方案有开放定址法、链表法以及再散列法等。