DSA 雜湊對映

雜湊對映

雜湊對映是一種 雜湊表 資料結構，通常包含大量條目。

使用雜湊對映，我們可以非常快速地搜尋、新增、修改和刪除條目。

雜湊對映用於查詢有關某事物的詳細資訊。

在下面的模擬中，人們儲存在一個雜湊對映中。可以使用一個人唯一的社會安全號碼（雜湊對映的鍵）來查詢某個人，然後我們可以看到這個人的名字（雜湊對映的值）。

要理解雜湊對映的工作原理，最好先看一下前面兩頁關於 雜湊表 和 雜湊集合 的內容。理解下面的單詞也很重要。

• 條目：由一個鍵和一個值組成，形成一個鍵值對。
• 鍵：雜湊對映中每個條目都是唯一的。用於生成雜湊碼，該雜湊碼決定了條目在雜湊對映中的儲存桶。這確保了每個條目都可以被高效地定位。
• 雜湊碼：從條目的鍵生成的數字，用於確定該雜湊對映條目屬於哪個儲存桶。
• 儲存桶：雜湊對映由許多這樣的儲存桶或容器組成，用於儲存條目。
• 值：可以是幾乎任何型別的資訊，例如一個人的姓名、出生日期和地址。值可以是多種不同型別資訊的組合。

查詢雜湊碼

雜湊碼由一個 雜湊函式 生成。

上面模擬中的雜湊函式會獲取社會安全號碼中的數字（不包括連字元），將它們加在一起，然後對字元的總和進行模 10 運算（% 10），以獲得 0 到 9 之間的雜湊碼數字。

這意味著，根據每個人的社會安全號碼的雜湊碼，該人將被儲存在雜湊對映的十個可能儲存桶中的一個。當我們要從雜湊對映中搜索或刪除某個人時，會生成並使用相同的雜湊碼。

只要相應儲存桶中只有一個人，雜湊碼就可以提供即時訪問。

在上面的模擬中，Charlotte 的社會安全號碼是 123-4567。將數字加在一起得到總和 28，然後模 10 的結果是 8。這就是為什麼她屬於儲存桶 8。

雜湊對映中的直接訪問

在雜湊對映中搜索 Charlotte 時，我們必須使用社會安全號碼 123-4567（雜湊對映的鍵），它會生成雜湊碼 8，如上所述。

這意味著我們可以直接轉到儲存桶 8 來獲取她的名字（雜湊對映的值），而無需搜尋雜湊對映中的其他條目。

在這些情況下，我們說雜湊對映在搜尋、新增和刪除條目時具有恆定時間 \(O(1)\)，這與使用陣列或連結串列相比非常快。

但是，在最壞的情況下，所有人都儲存在同一個儲存桶中，如果我們試圖查詢的人是該儲存桶中的最後一個人，我們就需要將所有其他社會安全號碼與該儲存桶中的號碼進行比較，才能找到我們要找的人。

在這種最壞的情況下，雜湊對映的時間複雜度為 \(O(n)\)，與陣列和連結串列相同。

為了保持雜湊對映的快速執行，因此重要的是要有一個能夠將條目均勻分佈到儲存桶中的雜湊函式，並且儲存桶的數量大致等於雜湊對映的條目數。

擁有比雜湊對映條目多得多的儲存桶是浪費記憶體，而擁有比雜湊對映條目少得多的儲存桶則是浪費時間。

雜湊對映實現

Python 中的雜湊對映通常透過使用 Python 自帶的 dictionary 資料型別 來實現，但為了更好地理解雜湊對映的工作原理，我們在這裡不使用它。

要在 Python 中實現雜湊對映，我們建立一個名為 SimpleHashMap 的類。

在 SimpleHashMap 類內部，我們有一個用於初始化雜湊對映的 __init__ 方法，一個用於雜湊函式的 hash_function 方法，以及用於基本雜湊對映操作的方法：put、get 和 remove。

我們還建立了一個 print_map 方法，以便更好地瞭解雜湊對映的外觀。

class SimpleHashMap:
    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, key):
        # Sum only the numerical values of the key, ignoring non-numeric characters
        numeric_sum = sum(int(char) for char in key if char.isdigit())
        return numeric_sum % 10  # Perform modulo 10 on the sum

    def put(self, key, value):
        # Add or update a key-value pair
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # Update existing key
                return
        bucket.append((key, value))  # Add new key-value pair if not found

    def get(self, key):
        # Retrieve a value by key
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for k, v in bucket:
            if k == key:
                return v
        return None  # Key not found

    def remove(self, key):
        # Remove a key-value pair
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]  # Remove the key-value pair
                return

    def print_map(self):
        # Print all key-value pairs in the hash map
        print("Hash Map Contents:")
        for index, bucket in enumerate(self.buckets):
            print(f"Bucket {index}: {bucket}")

使用 SimpleHashMap 類，我們可以建立與本頁頂部相同的雜湊對映。

class SimpleHashMap:
    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, key):
        # Sum only the numerical values of the key, ignoring non-numeric characters
        numeric_sum = sum(int(char) for char in key if char.isdigit())
        return numeric_sum % 10  # Perform modulo 10 on the sum

    def put(self, key, value):
        # Add or update a key-value pair
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # Update existing key
                return
        bucket.append((key, value))  # Add new key-value pair if not found

    def get(self, key):
        # Retrieve a value by key
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for k, v in bucket:
            if k == key:
                return v
        return None  # Key not found

    def remove(self, key):
        # Remove a key-value pair
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]  # Remove the key-value pair
                return

    def print_map(self):
        # Print all key-value pairs in the hash map
        print("Hash Map Contents:")
        for index, bucket in enumerate(self.buckets):
            print(f"Bucket {index}: {bucket}")

# Creating the Hash Map from the simulation
hash_map = SimpleHashMap(size=10)

# Adding some entries
hash_map.put("123-4567", "Charlotte")
hash_map.put("123-4568", "Thomas")
hash_map.put("123-4569", "Jens")
hash_map.put("123-4570", "Peter")
hash_map.put("123-4571", "Lisa")
hash_map.put("123-4672", "Adele")
hash_map.put("123-4573", "Michaela")
hash_map.put("123-6574", "Bob")

hash_map.print_map()

# Demonstrating retrieval
print("\nName associated with '123-4570':", hash_map.get("123-4570"))

print("Updating the name for '123-4570' to 'James'")
hash_map.put("123-4570","James")

# Checking if Peter is still there
print("Name associated with '123-4570':", hash_map.get("123-4570"))