数据结构中的哈希表：Python 示例

作者： Sarah Chen Sarah Chen
小时 - 权威教程 更新于

什么是哈希？

哈希值是一个固定长度的值，它使用数学公式生成。哈希值用于数据压缩、密码学等。在数据索引中，哈希值被使用，因为无论用于生成它们的值是什么，它们都具有固定的长度。这使得哈希值与可变长度的其他值相比，占用空间更小。

哈希函数使用数学算法将键转换为哈希。当哈希函数为多个键产生相同的哈希值时，就会发生冲突。

什么是哈希表？

哈希表是一种数据结构，它使用键值对存储值。每个值都分配了一个使用哈希函数生成的唯一键。

键的名称用于访问其关联的值。这使得在哈希表中搜索值非常快，无论哈希表中有多少项。

哈希函数

例如，如果我们想存储员工记录，并且每个员工都使用员工编号唯一标识。

我们可以使用员工编号作为键，并将员工数据作为值。

上述方法将需要额外的免费空间，其数量级为 (m * n2)，其中变量 m 是 数组的大小，变量 n 是员工编号的位数。这种方法引入了存储空间问题。

哈希函数通过获取员工编号并使用它来生成哈希整数值、固定位数，并优化存储空间来解决上述问题。哈希函数的目的是创建一个键，用于引用我们要存储的值。该函数接受要保存的值，然后使用算法计算键的值。

下面是一个简单的哈希函数的示例

h(k) = k1 % m

此处，

  • h(k) 是接受参数 k 的哈希函数。参数 k 是我们要计算键的值。
  • k1 % m 是我们哈希函数的算法，其中 k1 是我们要存储的值，m 是列表的大小。我们使用模运算符来计算键。

示例

假设我们有一个固定大小为 3 的列表以及以下值

[1,2,3]

我们可以使用上述公式来计算每个值应占用的位置。

下图显示了我们哈希表中可用的索引。

Hash Functions

步骤 1) 如下计算第一个值将占用的位置

h(1) = 1 % 3

= 1

值 1 将占用 索引 1 上的空间

步骤 2) 计算第二个值将占用的位置

h(2) = 2 % 3

= 2

值 2 将占用 索引 2 上的空间

步骤 3) 计算第三个值将占用的位置。

h(3) = 3 % 3

= 0

值 3 将占用 索引 0 上的空间

最终结果

我们填充的哈希表现在如下所示。

Hash Functions

相关文章

好的哈希函数的特性

一个好的哈希函数应具备以下特性。

  • 生成哈希的公式应在算法中使用要存储的数据的值。
  • 即使输入数据量相同，哈希函数也应生成唯一的哈希值。
  • 该函数应尽量减少冲突次数。当为多个值生成相同值时，会发生冲突。
  • 值必须在所有可能的哈希中一致地分布。

冲突

当算法为多个值生成相同的哈希时，就会发生冲突。

让我们看一个例子。

假设我们有以下值列表

[3,2,9,11,7]

假设哈希表的大小为 7，我们将使用公式 (k1 % m)，其中 m 是哈希表的大小。

下表显示了将生成的哈希值。

键 哈希算法 (k1 % m) 哈希值
3 3 % 7 3
2 3 % 7 2
9 3 % 7 2
11 3 % 7 4
7 3 % 7 0

从上述结果可以看出，值 2 和 9 具有相同的哈希值，我们不能在每个位置存储多个值。

给定的问题可以通过链式法或探测法来解决。以下各节详细讨论了链式法和探测法。

链式法

链式法是一种通过使用具有唯一索引的链表来解决冲突问题的方法。

下图可视化了链式列表的样子

Chaining

2 和 9 都占据相同的索引，但它们被存储为链表。每个列表都有一个唯一的标识符。

链式列表的优点

以下是链式列表的优点

  • 链式列表在插入数据时性能更好，因为插入的顺序是 O(1)。
  • 使用链式列表的哈希表不需要调整大小。
  • 只要有可用空间，它就可以轻松容纳大量值。

探测法

解决冲突的另一种技术是探测法。当使用探测法时，如果发生冲突，我们可以简单地继续查找一个空槽来存储我们的值。

以下是探测方法

方法 描述
线性探测 顾名思义，此方法从发生冲突的位置开始向前搜索空槽。如果到达列表末尾且没有找到空槽。则从列表开头开始探测。
二次探测 此方法使用二次多项式表达式来查找下一个可用的空槽。
双重哈希 此技术使用二次哈希函数算法来查找下一个可用的空槽。

使用我们上面的例子，使用探测法后的哈希表将如下所示

Probing

哈希表操作

以下是哈希表支持的操作

  • 插入 – 此操作用于将元素添加到哈希表
  • 搜索 – 此操作用于使用键在哈希表中搜索元素
  • 删除 – 此操作用于从哈希表中删除元素

插入数据操作

插入操作用于在哈希表中存储值。当在哈希表中存储新值时，会为其分配一个索引号。索引号是使用哈希函数计算的。哈希函数会解决计算索引号时发生的任何冲突。

搜索数据操作

搜索操作用于使用索引号在哈希表中查找值。搜索操作返回与搜索索引号相关联的值。例如，如果我们将在索引 2 处存储值 6，则索引号为 2 的搜索操作将返回值 6。

删除数据操作

删除操作用于从哈希表中删除值。要删除，操作是使用索引号完成的。一旦删除了一个值，该索引号就会被释放。它可以用于通过插入操作存储其他值。

使用 Python 示例实现哈希表

让我们看一个计算键的哈希值的简单示例

def hash_key( key, m):
    return key % m


m = 7

print(f'The hash value for 3 is {hash_key(3,m)}')
print(f'The hash value for 2 is {hash_key(2,m)}')
print(f'The hash value for 9 is {hash_key(9,m)}')
print(f'The hash value for 11 is {hash_key(11,m)}')
print(f'The hash value for 7 is {hash_key(7,m)}')

哈希表代码解释

Hash Table Code Explanation

此处，

  1. 定义一个接受参数 key 和 m 的函数 hash_key。
  2. 使用简单的模运算来确定哈希值
  3. 定义一个变量 m，其值初始化为 7。这是我们哈希表的大小
  4. 计算并打印 3 的哈希值
  5. 计算并打印 2 的哈希值
  6. 计算并打印 9 的哈希值
  7. 计算并打印 11 的哈希值
  8. 计算并打印 7 的哈希值

执行上述代码将产生以下结果。

The hash value for 3 is 3
The hash value for 2 is 2
The hash value for 9 is 2
The hash value for 11 is 4
The hash value for 7 is 0

Python 字典示例

Python 带有一个内置数据类型，称为字典。字典是哈希表的一个示例。它使用键值对存储值。哈希值会自动为我们生成，任何冲突都会在后台为我们解决。

下面的示例演示了如何在 python 3 中使用字典数据类型

employee = {
    'name': 'John Doe',
    'age': 36,
    'position': 'Business Manager.'
}

print (f"The name of the employee is {employee['name']}")
employee['position'] = 'Software Engineer'
print (f"The position of {employee['name']} is {employee['position']}")
employee.clear()

print (employee)

Python Dictionary Example

此处，

  1. 定义一个字典变量 employee。键 name 用于存储值 John Doe，age 存储 36，position 存储值 Business Manager。
  2. 检索键 name 的值并将其打印在终端上
  3. 将键 position 的值更新为 Software Engineer
  4. 打印键 name 和 position 的值
  5. 删除我们字典变量 employee 中存储的所有值
  6. 打印 employee 的值

运行上述代码将产生以下结果。

The name of the employee is John Doe.
The position of John Doe is a Software Engineer.
{}

复杂度分析

在最佳情况下，哈希表的平均时间复杂度为 O(1)。最坏情况下的时间复杂度为 O(n)。最坏情况发生在许多值生成相同的哈希键，并且我们必须通过探测来解决冲突。

实际应用

在实际应用中，哈希表用于存储数据

  • 数据库
  • 关联数组
  • 集合
  • 内存缓存

哈希表的优点

以下是使用哈希表的优点/好处

  • 哈希表在查找数据、插入和删除现有值时具有高性能。
  • 无论表中项目的数量如何，哈希表的时间复杂度都是恒定的。
  • 即使处理大型数据集，它们的性能也非常出色。

哈希表的缺点

以下是使用哈希表的缺点

  • 不能将 null 值用作键。
  • 使用哈希函数生成键时，无法避免冲突。当生成已使用的键时，会发生冲突。
  • 如果哈希函数存在许多冲突，这可能导致性能下降。

摘要

  • 哈希表使用键值对存储数据。
  • 哈希函数使用数学算法来计算哈希值。
  • 当为多个值生成相同的哈希值时，会发生冲突。
  • 链式法通过创建链表来解决冲突。
  • 探测法通过在哈希表中查找空槽来解决冲突。
  • 线性探测从发生冲突的槽开始，查找下一个空槽来存储值。
  • 二次探测在发生冲突时使用多项式表达式查找下一个空槽。
  • 双重哈希在发生冲突时使用二次哈希函数算法来查找下一个空槽。
  • 与其他数据结构相比，哈希表具有更好的性能。
  • 哈希表的平均时间复杂度为 O(1)
  • Python 中的字典数据类型是哈希表的一个示例。
  • 哈希表支持插入、搜索和删除操作。
  • 不能将 null 值用作索引值。
  • 哈希函数无法避免冲突。好的哈希函数可以最大限度地减少发生的冲突次数以提高性能。