第10课 哈希查找

哈希表查找方法原理哈希表查找方法什么是哈希表•哈希表是一种常见的数据结构，也被称为散列表。

•它可以提供快速的插入、删除和查找操作，时间复杂度在平均情况下为O(1)。

•哈希表由数组组成，每个数组元素称为桶(bucket)。

•存储数据时，通过哈希函数将数据映射到对应的桶中。

哈希函数的作用•哈希函数是哈希表的核心部分，它将数据转换为哈希值。

•哈希函数应该具备以下特点：–易于计算：计算哈希值的时间复杂度应尽量低。

–均匀分布：哈希函数应能将数据均匀地映射到不同的桶中，以避免桶的过度填充或者空闲。

–独特性：不同的输入应该得到不同的哈希值，以尽量减少冲突。

哈希冲突及解决方法•哈希冲突指两个或多个数据被哈希函数映射到同一个桶的情况。

•常见的解决哈希冲突的方法有以下几种：–链地址法(Chaining)：将相同哈希值的数据存储在同一个桶中，通过链表等数据结构来解决冲突。

–开放地址法(Open Addressing)：当发生冲突时，通过特定的规则找到下一个可用的桶来存储冲突的数据，如线性探测、二次探测等。

–再哈希法(Rehashing)：当发生冲突时，使用另一个哈希函数重新计算哈希值，并将数据存储到新的桶中。

哈希表的查找方法•哈希表的查找方法分为两步：1.根据哈希函数计算数据的哈希值，并得到对应的桶。

2.在桶中查找目标数据，如果找到则返回，否则表示数据不存在。

哈希表的查找性能•在理想情况下，哈希表的查找时间复杂度为O(1)。

•然而，由于哈希冲突的存在，查找时间可能会稍微增加。

•如果哈希函数设计得不好，导致冲突较多，可能会使查找时间复杂度接近O(n)。

•因此，选择合适的哈希函数和解决冲突的方法对于提高哈希表的查找性能非常重要。

总结•哈希表是一种高效的数据结构，适用于快速插入、删除和查找操作的场景。

•哈希函数的设计和解决冲突的方法直接影响哈希表的性能。

•在实际应用中，需要根据数据特点选择合适的哈希函数和解决冲突的方法，以提高哈希表的查找性能。

哈希表（Hash）的查找一、哈希表相关概念1、哈希函数的基本概念哈希表又称散列表。

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

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

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

按这种方法建立的表称为哈希表或散列表。

理想情况下，哈希函数在关键字和地址之间建立了一个一一对应关系，从而使得查找只需一次计算即可完成。

由于关键字值的某种随机性，使得这种一一对应关系难以发现或构造。

因而可能会出现不同的关键字对应一个存储地址。

即k1≠k2，但H(k1)=H(k2)，这种现象称为冲突。

把这种具有不同关键字值而具有相同哈希地址的对象称“同义词”。

在大多数情况下，冲突是不能完全避免的。

这是因为所有可能的关键字的集合可能比较大，而对应的地址数则可能比较少。

对于哈希技术，主要研究两个问题：（1）如何设计哈希函数以使冲突尽可能少地发生。

（2）发生冲突后如何解决。

2、哈希函数的构造方法常见的构造方法有很多种，如直接定址法，数字分析法，平方取中法等。

接下来，我们介绍其中的几种：（1）除留余数法取关键字k被某个不大于表长m的数p除后所得余数作为哈希函数地址的方法。

即：H（k）＝k mod ｐ这种方法的关键是选择好p。

使得数据集合中的每一个关键字通过该函数转化后映射到哈希表的任意地址上的概率相等。

理论研究表明，一般取p为小于ｍ的最大质数或不包含小于20的质因素的合数。

（2）平方取中法先将关键字平方，然后取其中间几位作为散列地址。

所取位数由地址空间范围决定。

若地址空间小于所取位数值决定的范围，可通过乘以一比例因子来解决。

（3）折叠法把关键字分割成位数相等（最后一部分的位数可以不同）的几部分，然后通过折叠后将几部分进行相加，丢掉进位位，所得值即为散列地址。

散列的位数由地址空间的位数而定。

分割方法：从右至左相加方法有两种：移位叠加：将分割后的各部分低位对齐相加。

详解哈希表的查找哈希表和哈希函数在记录的存储位置和它的关键字之间是建立一个确定的对应关系（映射函数），使每个关键字和一个存储位置能唯一对应。

这个映射函数称为哈希函数，根据这个原则建立的表称为哈希表(Hash Table)，也叫散列表。

以上描述，如果通过数学形式来描述就是：若查找关键字为key，则其值存放在f(key) 的存储位置上。

由此，不需比较便可直接取得所查记录。

注：哈希查找与线性表查找和树表查找最大的区别在于，不用数值比较。

冲突若key1 ≠ key2 ，而f(key1) = f(key2)，这种情况称为冲突(Collision)。

根据哈希函数f(key)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这一映射过程称为构造哈希表。

构造哈希表这个场景就像汽车找停车位，如果车位被人占了，只能找空的地方停。

构造哈希表由以上内容可知，哈希查找本身其实不费吹灰之力，问题的关键在于如何构造哈希表和处理冲突。

常见的构造哈希表的方法有 5 种：（1）直接定址法说白了，就是小学时学过的一元一次方程。

即 f(key) = a * key + b。

其中，a和b 是常数。

（2）数字分析法假设关键字是R进制数（如十进制）。

并且哈希表中可能出现的关键字都是事先知道的，则可选取关键字的若干数位组成哈希地址。

选取的原则是使得到的哈希地址尽量避免冲突，即所选数位上的数字尽可能是随机的。

（3）平方取中法取关键字平方后的中间几位为哈希地址。

通常在选定哈希函数时不一定能知道关键字的全部情况，仅取其中的几位为地址不一定合适；而一个数平方后的中间几位数和数的每一位都相关，由此得到的哈希地址随机性更大。

取的位数由表长决定。

（4）除留余数法取关键字被某个不大于哈希表表长 m 的数 p 除后所得的余数为哈希地址。

即f(key) = key % p (p ≤ m)这是一种最简单、最常用的方法，它不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。

哈希查找_数据结构实验报告哈希查找_数据结构实验报告一：实验目的本实验旨在掌握哈希查找算法的原理和实现方法，深入了解数据结构中的哈希查找技术，并通过实际操作加深对哈希查找的理解。

二：实验原理哈希查找是一种基于哈希函数的查找技术，通过将关键字通过哈希函数映射到哈希表中的位置进行查找。

其主要原理步骤如下：1. 创建哈希表：根据需求确定哈希表的大小，在内存中分配对应大小的空间。

2. 哈希函数的选择：根据关键字的特性选择适合的哈希函数，将关键字映射到哈希表的存储位置。

3. 插入操作：将关键字通过哈希函数计算得到索引位置，如果该位置为空，则直接插入；如果该位置已存在关键字，则发生冲突，需要解决冲突。

4. 冲突解决：常见的冲突解决方法包括线性探测、二次探测和链地址法等。

5. 查找操作：通过哈希函数计算得到关键字的索引位置，进行查找操作。

如果该位置为空，则表示查找失败；如果该位置不为空，则继续比较关键字是否相等。

6. 删除操作：将关键字标记为删除状态，或将该位置置为空。

三：实验步骤本实验中，我们以哈希表实现哈希查找算法，具体步骤如下：1. 创建哈希表：- 确定哈希表的大小。

- 在内存中分配对应大小的空间。

- 将所有位置初始化为空。

2. 哈希函数的选择：- 根据关键字的特性选择适合的哈希函数。

- 哈希函数应尽量保证均匀分布，避免冲突。

3. 插入操作：- 输入待插入的关键字。

- 通过哈希函数计算得到关键字的索引位置。

- 如果该位置为空，则直接插入关键字；如果该位置不为空，则发生冲突，需要解决冲突。

4. 冲突解决：- 使用线性探测法解决冲突：- 从发生冲突的位置向后逐个查找下一个为空的位置，直到找到空位置或遍历完整个哈希表。

- 如果找到空位置，则将关键字插入该位置；如果遍历完整个哈希表仍没有空位置，则插入失败。

- 使用链地址法解决冲突：- 在每个哈希表位置上维护一个链表，将冲突的关键字插入到链表中。

5. 查找操作：- 输入待查找的关键字。

哈希查找的名词解释
哈希查找（HashSearch）是一种快速检索技术，通过计算一个项目的哈希值，来快速检索该项目是否存在于数据表中。

它的原理是：数据集合中的每一个元素首先通过哈希函数映射成一个数字，然后根据这个数字对查询表进行定位，再根据查找表中的信息检索出查找的数据。

哈希查找可用于查看某个数据是否存在于某集合之中，也可以用于查看某个数据的各种相关信息。

哈希函数：
哈希函数是一种将原始数据映射成散列值的函数，它常用于实现哈希操作，即从原始数据中找到一个映射而来的数据。

根据哈希函数，相同的原始数据将会映射到相同的散列值上，由此来节省查找时间，提高查找效率。

桶：
桶（Bucket）是哈希查找的一种技术，它是把所有映射到同一散列值上的元素放在同一个桶中，以加快查找速度。

哈希查找时，先根据哈希函数计算出元素的散列值，然后根据这个散列值在桶中查找，直到找到查找元素为止。

哈希表：
哈希表（Hash Table）是一种存储数据的数据结构，它由一个固定大小的数组组成，其中每个元素都以键值对保存数据，其中键是一个数字或字符串，而值是任意类型的数据。

哈希表很容易根据键快速查找到对应的值，因此，使用哈希表可以实现快速查找操作。

一、实验名称：
查找算法的应用----哈希查找
二、实验目的：
1．进一步了解查找算法的用途；
2．进一步巩固哈希函数及哈希表等有关概念；
3．掌握哈希表的创建及查找的过程和方法；
4．比较哈希查找与其它查找算法的不同，体会哈希查找的优缺点。

三、实验内容：
任意给定N个元素，用除留余数法构造哈希函数，用线性探测再散列的方法建立哈希表，在哈希表中进行查找，并在屏幕上显示哈希表及查找结果。

求出等概率条件的平均查找长度，验证结果是否正确。

四、实验要求
1．哈希表中元素的类型为结构体类型。

2．输出哈希表的内容，验证其是否正确。

3．任意给定一个关键字进行查找，验证查找结果是否正确。

给定的这个关键字应有两类：存在和不存在。

4．求出等概率条件的平均查找长度。

五、实验程序代码：
完整的源程序。

六、实验数据处理及实验结果：
实验中输入的数据及执行结果
七、实验小结：
上机中出现的问题、解决方法，对所学知识的进一步理解，以后需要注意的问题等。

实验日期：年月日
交报告日期：年月日。

哈希查找的流程Hash lookup is a fundamental algorithm used in computer science to quickly retrieve data from a large dataset. The process involves using a hash function to map data to a unique key, which is then used to store and retrieve the data efficiently.哈希查找是计算机科学中使用的基本算法，用于从大型数据集中快速检索数据。

该过程涉及使用哈希函数将数据映射到唯一键，然后使用该键来高效地存储和检索数据。

From a technical perspective, the first step in a hash lookup process is to apply a hash function to the search key. This generates a unique hash value that is used as an index to access the corresponding data in a hash table. The hash table is a data structure that stores key-value pairs and allows for constant-time retrieval of data.从技术角度来看，哈希查找过程中的第一步是对搜索键应用哈希函数。

这将生成一个唯一的哈希值，该值用作索引来访问哈希表中的相应数据。

哈希表是一种存储键值对的数据结构，可以实现数据的常数时间检索。

One of the key advantages of hash lookup is its efficiency in retrieving data, especially in large datasets. This is because the use of a hash function allows for constant-time access to data, regardless of the size of the dataset. As a result, hash lookup is commonly used in applications where quick data retrieval is crucial, such as database systems and information retrieval systems.哈希查找的一个关键优势是它在检索数据方面的效率，特别是在大型数据集中。

哈希查找算法,处理冲突常用的方法摘要：一、哈希查找算法简介二、处理冲突的常用方法1.开放寻址法2.链地址法3.循环链地址法4.树状地址法三、各方法优缺点分析四、总结正文：一、哈希查找算法简介哈希查找算法是一种在有序表中进行查找的方法，通过将待查找元素的键值映射到对应的存储位置，从而实现快速查找。

哈希查找算法把关键码映射到数组的一个位置，如果该位置为空，就将该元素放入该位置；如果不为空，说明发生了冲突，需要采用一定的方法处理冲突。

二、处理冲突的常用方法1.开放寻址法开放寻址法是在哈希表中预留一部分空间来处理冲突。

当发生冲突时，查找失败，遍历预留空间，直到找到空位置存放元素。

这种方法的优点是实现简单，缺点是会增加查找的时间复杂度。

2.链地址法链地址法是在哈希表的每个位置都存放一个链表，发生冲突时，将冲突元素添加到对应位置的链表中。

这种方法的优点是充分利用了哈希表的空间，缺点是需要维护链表，时间复杂度较高。

3.循环链地址法循环链地址法是链地址法的改进版本，通过引入循环链表来解决冲突。

当链表长度超过预设阈值时，重新分配哈希表空间，并将原链表中的元素重新哈希。

这种方法的优点是避免了链表过长，缺点是需要额外的空间来存储链表指针。

4.树状地址法树状地址法是将哈希表分为多个层次，每层使用不同的处理冲突方法。

发生冲突时，根据层次遍历树结构，直到找到空位置。

这种方法的优点是层次结构更加合理，缺点是树状结构的维护成本较高。

三、各方法优缺点分析开放寻址法优点：实现简单，时间复杂度较低。

开放寻址法缺点：空间利用率不高，可能导致哈希表空间浪费。

链地址法优点：空间利用率高，适用于大规模数据处理。

链地址法缺点：需要维护链表，时间复杂度较高。

循环链地址法优点：避免了链表过长，提高了查找效率。

循环链地址法缺点：需要额外的空间存储链表指针，且重新分配哈希表空间时会影响性能。

树状地址法优点：层次结构合理，空间利用率较高。

树状地址法缺点：维护成本较高，实现复杂。

常见的查找算法（七）：哈希查找 散列表（Hash table，也叫哈希表），是根据键（Key）⽽直接访问在内存存储位置的数据结构。

也就是说，它通过计算⼀个关于键值的函数，将所需查询的数据映射到表中⼀个位置来访问记录，这加快了查找速度。

这个映射函数称做散列函数，存放记录的数组称做散列表。

散列函数的规则是：通过某种转换关系，使关键字适度的分散到指定⼤⼩的的顺序结构中，越分散，则以后查找的时间复杂度越⼩，空间复杂度越⾼。

1. 直接定址法：取关键字或关键字的某个线性函数值为散列地址。

即hash(k) = k 或 hash(k) = a · k + b，其中a、b为常数（这种散列函数叫做⾃⾝函数）2. 数字分析法：假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若⼲数位组成哈希地址。

3. 平⽅取中法：取关键字平⽅后的中间⼏位为哈希地址。

通常在选定哈希函数时不⼀定能知道关键字的全部情况，取其中的哪⼏位也不⼀定合适，⽽⼀个数平⽅后的中间⼏位数和数的每⼀位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。

取的位数由表长决定。

4. 折叠法：将关键字分割成位数相同的⼏部分（最后⼀部分的位数可以不同），然后取这⼏部分的叠加和（舍去进位）作为哈希地址。

5. 随机数法6. 除留余数法：取关键字被某个不⼤于散列表表长m的数p除后所得的余数为散列地址。

即 hash(k) = k mod p， p<=m。

不仅可以对关键字直接取模，也可在折叠法、平⽅取中法等运算之后取模。

对p的选择很重要，⼀般取素数或m，若p选择不好，容易产⽣冲突。

Hash是⼀种典型以空间换时间的算法，⽐如原来⼀个长度为100的数组，对其查找，只需要遍历且匹配相应记录即可，从空间复杂度上来看，假如数组存储的是byte类型数据，那么该数组占⽤100byte空间。

现在我们采⽤Hash算法，我们前⾯说的Hash必须有⼀个规则，约束键与存储位置的关系，那么就需要⼀个固定长度的hash表，此时，仍然是100byte的数组，假设我们需要的100byte⽤来记录键与位置的关系，那么总的空间为200byte，⽽且⽤于记录规则的表⼤⼩会根据规则，⼤⼩可能是不定的。