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