数据结构中的散列：函数、技术 [附示例]

介绍

散列是一种重要的数据结构，旨在解决在数组中高效查找和存储数据的问题。 例如，如果您有一个包含 20000 个号码的列表，并且您指定了一个要在该列表中搜索的号码 - 您将扫描列表中的每个号码，直到找到匹配项。

您需要花费大量时间来搜索整个列表并找到该特定号码。 这种手动扫描过程不仅耗时而且效率低下。 通过数据结构中的散列，您可以缩小搜索范围并在几秒钟内找到数字。

本博客将通过示例让您更深入地了解哈希方法、哈希表和线性探测。

什么是数据结构中的散列？

数据结构中的散列是一种使用散列函数将大量数据映射到小表中的技术。 它也被称为消息摘要功能。 它是一种从类似项目的集合中唯一标识特定项目的技术。

它使用哈希表以数组格式存储数据。 数组中的每个值都分配了一个唯一的索引号。 哈希表使用一种技术为以数组格式存储的每个值生成这些唯一索引号。 这种技术称为散列技术。

您只需要查找所需项目的索引，而不需要查找数据。 通过索引，您可以快速扫描整个列表并检索您想要的项目。 当您需要在特定位置插入数据时，索引还有助于插入操作。 无论表有多大或多小，您都可以在几秒钟内更新和检索数据。

数据结构中的散列是一个两步过程。

1. 散列函数将项目转换为小整数或散列值。 该整数用作存储原始数据的索引。
2. 它将数据存储在哈希表中。 您可以使用哈希键快速定位数据。

数据结构中的散列示例

以下是数据结构中散列的真实示例-

• 在学校，老师为每个学生分配一个唯一的卷号。 稍后，教师使用该卷号检索有关该学生的信息。
• 图书馆有无限多的书。 图书管理员为每本书分配一个唯一的编号。 这个唯一编号有助于识别书架上书籍的位置。

结帐：数据结构中的排序

哈希函数

数据结构中的散列函数将任意大小的数据映射到固定大小的数据。 它返回以下值：一个小整数值（也称为散列值）、散列码和散列和。

哈希=哈希函数（键）

索引 = 哈希 % array_size

has 函数必须满足以下要求：

• 一个好的散列函数很容易计算。
• 一个好的散列函数永远不会卡在集群中，并且在散列表中均匀分布键。
• 当两个元素或项目分配给相同的哈希值时，一个好的哈希函数可以避免冲突。

哈希表

数据结构中的散列使用散列表来存储键值对。 然后哈希表使用哈希函数生成索引。 散列使​​用此唯一索引来执行插入、更新和搜索操作。

数据结构中的散列是如何工作的？

在散列中，散列函数将字符串或数字映射到一个小的整数值。 散列表使用散列函数从列表中检索项目。 散列技术的目标是在数组中均匀分布数据。 散列为所有元素分配一个唯一键。 哈希表使用这个键来访问列表中的数据。

哈希表将数据存储在键值对中。 密钥充当散列函数的输入。 然后散列函数为每个存储的值生成一个唯一的索引号。 索引号保留与该键对应的值。 散列函数返回一个小的整数值作为输出。 散列函数的输出称为散列值。

让我们通过一个例子来理解数据结构中的散列。 想象一下，您需要在一个包含 30 个单元格的哈希表中存储一些项目（以键值对的形式排列）。

值为： (3,21) (1,72) (40,36) (5,30) (11,44) (15,33) (18,12) (16,80) (38,99)

哈希表如下所示：

另请阅读： Python 中的数据结构类型

碰撞解决技术

如果在哈希表中为两个键分配了相同的索引号，则数据结构中的哈希会发生冲突。 冲突产生了一个问题，因为哈希表中的每个索引都应该只存储一个值。 数据结构中的散列使用几种冲突解决技术来管理散列表的性能。

线性探测

数据结构中的散列会导致数组索引已被占用以存储值。 在这种情况下，散列会执行搜索操作并线性探测下一个空单元格。

线性探测示例

假设您被要求将一些项目存储在大小为 30 的哈希表中。这些项目已经以键值对格式排序。 给出的值是： (3,21) (1,72) (63,36) (5,30) (11,44) (15,33) (18,12) (16,80) (46,99) .

hash(n) 是使用散列函数计算的索引，T 是表大小。 如果 slot index = ( hash(n) % T) 已满，那么我们通过添加 1 ((hash(n) + 1) % T) 来寻找下一个 slot index。 如果 (hash(n) + 1) % T 也满了，那么我们尝试 (hash(n) + 2) % T。如果 (hash(n) + 2) % T 也满了，那么我们尝试 (hash( n) + 3) % T。

哈希表如下所示：

双重哈希

双散列技术使用两个散列函数。 当第一个函数引起冲突时，第二个哈希函数开始使用。 它提供了一个偏移索引来存储该值。

双散列技术的公式如下：

(firstHash(key) + i * secondHash(key)) % sizeOfTable

其中 i 是偏移值。 这个偏移值不断增加，直到找到一个空槽。

例如，您有两个散列函数：h1 和 h2。 您必须执行以下步骤才能找到空槽：

1. 验证 hash1(key) 是否为空。 如果是，则将值存储在此插槽中。
2. 如果 hash1(key) 不为空，则使用 hash2(key) 找到另一个槽。
3. 验证 hash1(key) + hash2(key) 是否为空。 如果是，则将值存储在此插槽中。
4. 继续递增计数器并重复 hash1(key)+2hash2(key)、hash1(key)+3hash2(key) 等，直到找到一个空槽。

双散列示例

假设您需要将一些项目存储在大小为 20 的哈希表中。给出的值是：(16, 8, 63, 9, 27, 37, 48, 5, 69, 34, 1)。

h1(n)=n%20

h2(n)=n%13

nh(n, i) = (h1 (n) + ih2(n)) mod 20

结论

双散列的计算成本很高，但它比线性探测方法更快地搜索下一个空闲槽。 文章中给出的示例仅用于说明目的。 您可以根据您的要求修改上面给出的语句。 在这篇博客中，我们了解了数据结构中散列的概念。

你可以试试这个例子来加强你的数据结构知识。 如果您想了解更多关于数据结构的信息，请查看全栈开发课程中的 upGrad Executive PG Program 。 本课程专为在职专业人士而设计，并提供严格的培训和顶级公司的工作安排。