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'))