如何用Python實作雜湊表

哈希表是一種重要的資料結構，在電腦科學中應用廣泛。它可以快速地在大量資料中尋找、插入或刪除一個特定的元素。用Python實作雜湊表，不僅可以深入理解雜湊表的內部工作機制，也可以增強自己的程式設計能力。在本文中，我們將詳細介紹如何用Python實作雜湊表。

1. 什麼是哈希表

哈希表又被稱為散列表，它是一種 key-value 儲存方法。它透過將 key 映射到 value 的一個索引位置來存取資料。它的基本操作包括插入、刪除和查找。

雜湊表的核心思想是使用雜湊函數將每個 key 對應到固定大小的表中。雜湊函數是一種將任意長度的輸入訊息轉換為固定長度輸出的函數。常見的雜湊函數有MD5、SHA1、SHA256等。

2. 實作雜湊表

我們用Python實作一個簡單的雜湊表，包括雜湊表的基本操作，如插入、刪除和查找等。

先定義一個Node類，表示哈希表的節點。每個節點包含一個key和一個value。

class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None

接下來定義一個HashTable類，我們用Python的list實作底層資料結構。插入key-value對時，我們需要根據key計算哈希值，並將key-value對儲存在哈希表中對應的位置。

class HashTable:
    def __init__(self):
        self.size = 100
        self.table = [None] * self.size
        
    def hash_func(self, key):
        return sum([ord(c) for c in key]) % self.size
    
    def insert(self, key, value):
        hash_value = self.hash_func(key)
        if self.table[hash_value] is None:
            self.table[hash_value] = Node(key, value)
        else:
            cur = self.table[hash_value]
            while cur.next is not None:
                cur = cur.next
            cur.next = Node(key, value)
    
    def search(self, key):
        hash_value = self.hash_func(key)
        if self.table[hash_value] is None:
            return None
        else:
            cur = self.table[hash_value]
            while cur is not None:
                if cur.key == key:
                    return cur.val
                else:
                    cur = cur.next
            return None
    
    def delete(self, key):
        hash_value = self.hash_func(key)
        if self.table[hash_value] is None:
            return
        elif self.table[hash_value].key == key:
            self.table[hash_value] = self.table[hash_value].next
        else:
            cur = self.table[hash_value]
            while cur.next is not None:
                if cur.next.key == key:
                    cur.next = cur.next.next
                    return
                else:
                    cur = cur.next

在上述程式碼中，hash_func方法根據key計算哈希值，insert方法將key-value對插入到哈希表中對應的位置上，search方法根據key查找value，delete方法根據key刪除對應的key-value對。

3. 測試雜湊表

接下來我們測試上述實作的雜湊表。

ht = HashTable()
ht.insert('apple', 2.5)
ht.insert('banana', 1.3)
ht.insert('orange', 0.7)

print(ht.search('apple')) # 2.5
print(ht.search('banana')) # 1.3
print(ht.search('orange')) # 0.7
print(ht.search('lemon')) # None

ht.delete('apple')
print(ht.search('apple')) # None

上述程式碼中，我們建立了一個HashTable物件ht，並將三個key-value對插入ht。然後，我們透過search方法找出key為'apple'、'banana'和'orange'的value，並刪除一個key為'apple'的key-value對。最後，我們再查找key為'apple'的value，應該回傳None。

4. 總結

本文介紹如何用Python實作雜湊表。我們定義了一個Node類別表示哈希表的一個節點，再定義了一個HashTable類別表示哈希表，並實作了哈希表的基本操作，例如插入、刪除和查找等。透過實作雜湊表，我們可以深入理解雜湊表的內部工作機制，並增強自己的程式設計能力。

以上是如何用Python實作雜湊表的詳細內容。更多資訊請關注PHP中文網其他相關文章！