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 个元素。在谈论哈希表时，这些元素中的每一个都称为一个 **桶**。

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 处。

哈希函数返回的数字称为 **哈希码**。

在将“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”会创建一个称为 **冲突** 的东西，因为“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)\)！有关时间复杂度的更多信息，请点击这里。

哈希集 vs. 哈希表

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

以下是哈希集和哈希表之间的区别和相似之处

哈希表总结

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

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

哈希函数使用元素的键生成一个哈希码。

哈希码指示元素属于哪个桶，因此现在我们可以直接访问该哈希表元素：修改它、删除它，或者只是检查它是否存在。具体的哈希函数将在接下来的两页中详细解释。

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

本教程使用链式来解决冲突，方法是使用数组或链表来允许同一个桶中有多个元素。

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

结论

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

使用哈希集还是哈希表取决于您的需求：只是想知道某样东西是否存在，还是查找有关它的详细信息。