DSA 哈希集合

哈希集合

哈希集合是一种形式的 哈希表 数据结构，通常包含大量元素。

使用哈希集合，我们可以非常快速地搜索、添加和删除元素。

哈希集合用于查找，以检查某个元素是否是集合的一部分。

哈希集合根据元素的哈希码将唯一元素存储在存储桶中。

• 哈希码： 从元素唯一值（键）生成的数字，用于确定该哈希集合元素属于哪个存储桶。
• 唯一元素： 哈希集合不能有多个相同值的元素。
• 存储桶： 哈希集合包含许多这样的存储桶或容器来存储元素。如果两个元素的哈希码相同，则它们属于同一个存储桶。因此，存储桶通常实现为数组或链表，因为一个存储桶需要能够容纳多个元素。

查找哈希码

哈希码由 哈希函数 生成。

上面动画中的哈希函数获取输入中的姓名，并对该姓名中每个字符的 Unicode 代码点求和。

之后，哈希函数对字符的总和进行模 10 运算（% 10）以获得 0 到 9 之间的哈希码数字。

这意味着一个姓名根据其哈希码被放入哈希集合中的十个可能存储桶之一。当我们想要从哈希集合中搜索或删除一个姓名时，会生成并使用相同的哈希码。

只要对应的存储桶中只有一个姓名，哈希码就能提供即时访问。

哈希集合中的直接访问

在上面的哈希集合中搜索 Peter，意味着会生成哈希码 2（512 % 10），这将直接将我们引导到 Peter 所在的存储桶。如果那个存储桶里只有这一个名字，我们会立即找到 Peter。

在这些情况下，我们说哈希集合在搜索、添加和删除元素方面具有常数时间 \(O(1)\)，这非常快。

但是，如果我们搜索 Jens，我们需要搜索该存储桶中的其他名字，然后才能找到 Jens。在最坏的情况下，所有名字都落入同一个存储桶，而我们要搜索的名字是最后一个。在这种最坏的情况下，哈希集合的时间复杂度为 \(O(n)\)，与数组和链表的时间复杂度相同。

为了保持哈希集合的快速性，因此拥有一个能够将元素均匀分布到存储桶中的哈希函数，并拥有大约与哈希集合元素数量相等的存储桶数量非常重要。

拥有比哈希集合元素多得多的存储桶会浪费内存，而拥有比哈希集合元素少得多的存储桶会浪费时间。

哈希集合实现

Python 中的哈希集合通常通过使用 Python 自己的 set 数据类型 来实现，但为了更好地理解哈希集合的工作原理，这里我们不使用它。

要在 Python 中实现哈希集合，我们创建一个名为 SimpleHashSet 的类。

在 SimpleHashSet 类中，我们有一个用于初始化哈希集合的 __init__ 方法，一个用于哈希函数的 hash_function 方法，以及用于基本哈希集合操作的方法：add、contains 和 remove。

我们还创建了一个 print_set 方法，以便更好地查看哈希集合的外观。

class SimpleHashSet:
    def __init__(self, size=100):
        self.size = size
        self.buckets = [[] for _ in range(size)]  # A list of buckets, each is a list (to handle collisions)

    def hash_function(self, value):
        # Simple hash function: sum of character codes modulo the number of buckets
        return sum(ord(char) for char in value) % self.size

    def add(self, value):
        # Add a value if it's not already present
        index = self.hash_function(value)
        bucket = self.buckets[index]
        if value not in bucket:
            bucket.append(value)

    def contains(self, value):
        # Check if a value exists in the set
        index = self.hash_function(value)
        bucket = self.buckets[index]
        return value in bucket

    def remove(self, value):
        # Remove a value
        index = self.hash_function(value)
        bucket = self.buckets[index]
        if value in bucket:
            bucket.remove(value)

    def print_set(self):
        # Print all elements in the hash set
        print("Hash Set Contents:")
        for index, bucket in enumerate(self.buckets):
            print(f"Bucket {index}: {bucket}")

使用 SimpleHashSet 类，我们可以创建与本页顶部相同的哈希集合。

class SimpleHashSet:
    def __init__(self, size=100):
        self.size = size
        self.buckets = [[] for _ in range(size)]  # A list of buckets, each is a list (to handle collisions)

    def hash_function(self, value):
        # Simple hash function: sum of character codes modulo the number of buckets
        return sum(ord(char) for char in value) % self.size

    def add(self, value):
        # Add a value if it's not already present
        index = self.hash_function(value)
        bucket = self.buckets[index]
        if value not in bucket:
            bucket.append(value)

    def contains(self, value):
        # Check if a value exists in the set
        index = self.hash_function(value)
        bucket = self.buckets[index]
        return value in bucket

    def remove(self, value):
        # Remove a value
        index = self.hash_function(value)
        bucket = self.buckets[index]
        if value in bucket:
            bucket.remove(value)

    def print_set(self):
        # Print all elements in the hash set
        print("Hash Set Contents:")
        for index, bucket in enumerate(self.buckets):
            print(f"Bucket {index}: {bucket}")

# Creating the Hash Set from the simulation
hash_set = SimpleHashSet(size=10)

hash_set.add("Charlotte")
hash_set.add("Thomas")
hash_set.add("Jens")
hash_set.add("Peter")
hash_set.add("Lisa")
hash_set.add("Adele")
hash_set.add("Michaela")
hash_set.add("Bob")

hash_set.print_set()

print("\n'Peter' is in the set:",hash_set.contains('Peter'))
print("Removing 'Peter'")
hash_set.remove('Peter')
print("'Peter' is in the set:",hash_set.contains('Peter'))
print("'Adele' has hash code:",hash_set.hash_function('Adele'))