DSA 哈希表

哈希表

哈希表是一种旨在快速处理数据的数据结构。

哈希表有时比数组或链表更受青睐的原因是，即使处理大量数据，搜索、添加和删除数据也可以非常快速地完成。

在链表中，查找一个名叫“Bob”的人需要花费一些时间，因为我们必须从一个节点一个节点地进行检查，直到找到名叫“Bob”的节点。

在数组中查找“Bob”如果知道索引可能会很快，但当我们只知道名字“Bob”时，我们需要像链表一样比较每个元素，这会花费时间。

然而，使用哈希表，查找“Bob”会非常快，因为有一个方法可以使用称为哈希函数的机制直接定位到存储“Bob”的位置。

从头开始构建哈希表

为了了解哈希表是什么，让我们尝试从头开始构建一个，用于存储其中唯一的姓氏。

我们将分 5 个步骤构建哈希集

1. 从一个数组开始。
2. 使用哈希函数存储姓名。
3. 使用哈希函数查找元素。
4. 处理冲突。
5. 基本的哈希集代码示例和模拟。

步骤 1：从一个数组开始

使用数组，我们可以像这样存储姓名

my_array = ['Pete', 'Jones', 'Lisa', 'Bob', 'Siri']

要在此数组中查找“Bob”，我们需要逐个元素比较每个姓名，直到找到“Bob”。

如果数组是按字母顺序排序的，我们可以使用二分查找快速找到一个姓名，但插入或删除数组中的姓名将意味着在内存中移动元素的繁琐操作。

为了使与姓名列表的交互非常快速，让我们改用哈希表，或者哈希集，它是哈希表的简化版本。

为了简单起见，让我们假设列表中最多有 10 个姓名，因此数组必须是固定大小的 10 个元素。在谈论哈希表时，这些元素中的每一个都称为一个桶 (bucket)。

my_hash_set = [None,None,None,None,None,None,None,None,None,None]

步骤 2：使用哈希函数存储姓名

现在我们来实现与我们正在制作的哈希集交互的特殊方式。

我们希望将一个姓名直接存储到数组中的正确位置，这就是哈希函数发挥作用的地方。

哈希函数可以有很多种，这取决于哈希表的创建者。一种常见的方法是找到一种将值转换为数字的方法，该数字等于哈希集的一个索引号，在这种情况下是 0 到 9 之间的数字。在我们示例中，我们将使用每个字符的 Unicode 数字，将它们汇总，然后进行模 10 运算以获得索引号 0-9。

def hash_function(value):
    sum_of_chars = 0
    for char in value:
        sum_of_chars += ord(char)

    return sum_of_chars % 10

print("'Bob' has hash code:",hash_function('Bob'))

字符“B”的 Unicode 代码点是 66，“o”是 111，“b”是 98。将它们相加得到 275。275 模 10 的结果是 5，所以“Bob”应该存储在索引 5 的数组元素中。

哈希函数返回的数字称为哈希码 (hash code)。

将“Bob”存储在哈希码指示的位置（索引 5）后，我们的数组现在看起来像这样

my_hash_set = [None,None,None,None,None,'Bob',None,None,None,None]

我们还可以使用哈希函数来找出如何存储其他姓名“Pete”、“Jones”、“Lisa”和“Siri”。

使用哈希函数将这些姓名存储到正确位置后，我们的数组看起来像这样

my_hash_set = [None,'Jones',None,'Lisa',None,'Bob',None,'Siri','Pete',None]

步骤 3：使用哈希函数查找姓名

我们现在已经建立了一个超基本的哈希集，因为我们不再需要逐个元素检查数组来找出“Pete”是否在其中，我们可以直接使用哈希函数直接转到正确的元素！

要找出“Pete”是否存储在数组中，我们将“Pete”这个名字传给我们的哈希函数，得到哈希码 9，我们直接转到索引 9 的元素，它就在那里。我们找到了“Pete”，而没有检查任何其他元素。

my_hash_set = [None,'Jones',None,'Lisa',None,'Bob',None,'Siri','Pete',None]

def hash_function(value):
    sum_of_chars = 0
    for char in value:
        sum_of_chars += ord(char)

    return sum_of_chars % 10
    
def contains(name):
    index = hash_function(name)
    return my_hash_set[index] == name

print("'Pete' is in the Hash Set:",contains('Pete'))

从哈希集中删除姓名时，我们也可以使用哈希函数直接转到该姓名所在的位置，并将该元素值设置为 None。

步骤 4：处理冲突

让我们还将“Stuart”添加到我们的哈希集中。

我们将“Stuart”传给我们的哈希函数，得到哈希码 3，这意味着“Stuart”应该存储在索引 3。

尝试存储“Stuart”会产生所谓的冲突 (collision)，因为“Lisa”已经存储在索引 3。

为了解决冲突，我们可以为同一个桶腾出更多空间，以这种方式解决冲突称为链表。我们可以通过将每个桶实现为链表或数组来为同一个桶腾出更多空间。

在将每个桶实现为数组以容纳可能多于一个姓名的空间后，“Stuart”也可以存储在索引 3，我们的哈希集现在看起来像这样

my_hash_set = [
    [None],
    ['Jones'],
    [None],
    ['Lisa', 'Stuart'],
    [None],
    ['Bob'],
    [None],
    ['Siri'],
    ['Pete'],
    [None]
]

现在，在我们的哈希集中搜索“Stuart”意味着使用哈希函数直接进入桶 3，但然后我们必须先检查该桶中的“Lisa”，然后才能在桶 3 的第二个元素中找到“Stuart”。

步骤 5：哈希集代码示例和模拟

为了完成我们非常基本的哈希集代码，让我们添加用于在哈希集中添加和搜索姓名的函数，现在它是一个二维数组。

运行下面的代码示例，并尝试使用不同的值，以更好地理解哈希集的工作原理。

my_hash_set = [
    [None],
    ['Jones'],
    [None],
    ['Lisa'],
    [None],
    ['Bob'],
    [None],
    ['Siri'],
    ['Pete'],
    [None]
]

def hash_function(value):
    return sum(ord(char) for char in value) % 10
    
def add(value):
    index = hash_function(value)
    bucket = my_hash_set[index]
    if value not in bucket:
        bucket.append(value)
        
def contains(value):
    index = hash_function(value)
    bucket = my_hash_set[index]
    return value in bucket

add('Stuart')

print(my_hash_set)
print('Contains Stuart:',contains('Stuart'))

接下来的两页将展示更好、更详细的哈希集和哈希表实现。

尝试下面的哈希集模拟，以更好地了解哈希集的基本工作原理。

哈希表的使用

哈希表很适合

• 检查某个项是否在集合中（例如在图书馆中查找一本书）。
• 存储唯一项并快速找到它们（例如存储电话号码）。
• 将值连接到键（例如将姓名连接到电话号码）。

哈希表之所以在这些方面表现出色，最主要的原因是与数组和链表相比，哈希表非常快速，尤其是对于大型数据集。数组和链表在搜索和删除方面具有 \(O(n)\) 的时间复杂度，而哈希表平均只有 \(O(1)\)！在此处阅读更多关于时间复杂度。

哈希集与哈希映射

哈希表可以是哈希集或哈希映射。接下来的两页将更详细地描述这些数据结构。

这是哈希集和哈希映射的异同

哈希表总结

哈希表元素存储在称为桶 (buckets) 的存储容器中。

每个哈希表元素都有一个称为键 (key) 的唯一部分。

哈希函数 (hash function) 接收元素的键以生成哈希码 (hash code)。

哈希码指明元素所属的桶，这样我们就可以直接访问该哈希表元素：修改它、删除它，或者只是检查它是否存在。特定哈希函数的详细解释将在接下来的两页中给出。

当两个哈希表元素具有相同的哈希码时，就会发生冲突 (collision)，因为这意味着它们属于同一个桶 (bucket)。冲突可以通过两种方式解决。

链表 (Chaining) 是本教程中解决冲突的方法，通过使用数组或链表允许多个元素存在于同一个桶中。

开放寻址 (Open Addressing) 是解决冲突的另一种方法。在开放寻址中，如果我们想存储一个元素但该桶中已存在一个元素，则该元素将被存储在下一个可用桶中。这可以通过多种方式完成，但我们在此不再进一步解释开放寻址。

结论

哈希表是编程中的强大工具，可以帮助您高效地管理和访问数据。

您选择使用哈希集还是哈希映射取决于您的需求：是只需要知道某项是否存在，还是需要查找有关它的详细信息。