DSA 雜湊表

雜湊表

雜湊表是一種旨在快速處理資料的資料結構。

雜湊表有時比陣列或連結串列更受青睞的原因是，即使處理大量資料，搜尋、新增和刪除資料也可以非常快速地完成。

在連結串列中，查詢一個名叫“Bob”的人需要花費一些時間，因為我們必須從一個節點一個節點地進行檢查，直到找到名叫“Bob”的節點。

在陣列中查詢“Bob”如果知道索引可能會很快，但當我們只知道名字“Bob”時，我們需要像連結串列一樣比較每個元素，這會花費時間。

然而，使用雜湊表，查詢“Bob”會非常快，因為有一個方法可以使用稱為雜湊函式的機制直接定位到儲存“Bob”的位置。

從頭開始構建雜湊表

為了瞭解雜湊表是什麼，讓我們嘗試從頭開始構建一個，用於儲存其中唯一的姓氏。

我們將分 5 個步驟構建雜湊集

1. 從一個數組開始。
2. 使用雜湊函式儲存姓名。
3. 使用雜湊函式查詢元素。
4. 處理衝突。
5. 基本的雜湊集程式碼示例和模擬。

步驟 1：從一個數組開始

使用陣列，我們可以像這樣儲存姓名

my_array = ['Pete', 'Jones', 'Lisa', 'Bob', 'Siri']

要在此陣列中查詢“Bob”，我們需要逐個元素比較每個姓名，直到找到“Bob”。

如果陣列是按字母順序排序的，我們可以使用二分查詢快速找到一個姓名，但插入或刪除陣列中的姓名將意味著在記憶體中移動元素的繁瑣操作。

為了使與姓名列表的互動非常快速，讓我們改用雜湊表，或者雜湊集，它是雜湊表的簡化版本。

為了簡單起見，讓我們假設列表中最多有 10 個姓名，因此陣列必須是固定大小的 10 個元素。在談論雜湊表時，這些元素中的每一個都稱為一個桶 (bucket)。

my_hash_set = [None,None,None,None,None,None,None,None,None,None]

步驟 2：使用雜湊函式儲存姓名

現在我們來實現與我們正在製作的雜湊集互動的特殊方式。

我們希望將一個姓名直接儲存到陣列中的正確位置，這就是雜湊函式發揮作用的地方。

雜湊函式可以有很多種，這取決於雜湊表的建立者。一種常見的方法是找到一種將值轉換為數字的方法，該數字等於雜湊集的一個索引號，在這種情況下是 0 到 9 之間的數字。在我們示例中，我們將使用每個字元的 Unicode 數字，將它們彙總，然後進行模 10 運算以獲得索引號 0-9。

def hash_function(value):
    sum_of_chars = 0
    for char in value:
        sum_of_chars += ord(char)

    return sum_of_chars % 10

print("'Bob' has hash code:",hash_function('Bob'))

字元“B”的 Unicode 程式碼點是 66，“o”是 111，“b”是 98。將它們相加得到 275。275 模 10 的結果是 5，所以“Bob”應該儲存在索引 5 的陣列元素中。

雜湊函式返回的數字稱為雜湊碼 (hash code)。

將“Bob”儲存在雜湊碼指示的位置（索引 5）後，我們的陣列現在看起來像這樣

my_hash_set = [None,None,None,None,None,'Bob',None,None,None,None]

我們還可以使用雜湊函式來找出如何儲存其他姓名“Pete”、“Jones”、“Lisa”和“Siri”。

使用雜湊函式將這些姓名儲存到正確位置後，我們的陣列看起來像這樣

my_hash_set = [None,'Jones',None,'Lisa',None,'Bob',None,'Siri','Pete',None]

步驟 3：使用雜湊函式查詢姓名

我們現在已經建立了一個超基本的雜湊集，因為我們不再需要逐個元素檢查陣列來找出“Pete”是否在其中，我們可以直接使用雜湊函式直接轉到正確的元素！

要找出“Pete”是否儲存在陣列中，我們將“Pete”這個名字傳給我們的雜湊函式，得到雜湊碼 9，我們直接轉到索引 9 的元素，它就在那裡。我們找到了“Pete”，而沒有檢查任何其他元素。

my_hash_set = [None,'Jones',None,'Lisa',None,'Bob',None,'Siri','Pete',None]

def hash_function(value):
    sum_of_chars = 0
    for char in value:
        sum_of_chars += ord(char)

    return sum_of_chars % 10
    
def contains(name):
    index = hash_function(name)
    return my_hash_set[index] == name

print("'Pete' is in the Hash Set:",contains('Pete'))

從雜湊集中刪除姓名時，我們也可以使用雜湊函式直接轉到該姓名所在的位置，並將該元素值設定為 None。

步驟 4：處理衝突

讓我們還將“Stuart”新增到我們的雜湊集中。

我們將“Stuart”傳給我們的雜湊函式，得到雜湊碼 3，這意味著“Stuart”應該儲存在索引 3。

嘗試儲存“Stuart”會產生所謂的衝突 (collision)，因為“Lisa”已經儲存在索引 3。

為了解決衝突，我們可以為同一個桶騰出更多空間，以這種方式解決衝突稱為連結串列。我們可以透過將每個桶實現為連結串列或陣列來為同一個桶騰出更多空間。

在將每個桶實現為陣列以容納可能多於一個姓名的空間後，“Stuart”也可以儲存在索引 3，我們的雜湊集現在看起來像這樣

my_hash_set = [
    [None],
    ['Jones'],
    [None],
    ['Lisa', 'Stuart'],
    [None],
    ['Bob'],
    [None],
    ['Siri'],
    ['Pete'],
    [None]
]

現在，在我們的雜湊集中搜索“Stuart”意味著使用雜湊函式直接進入桶 3，但然後我們必須先檢查該桶中的“Lisa”，然後才能在桶 3 的第二個元素中找到“Stuart”。

步驟 5：雜湊集程式碼示例和模擬

為了完成我們非常基本的雜湊集程式碼，讓我們新增用於在雜湊集中新增和搜尋姓名的函式，現在它是一個二維陣列。

執行下面的程式碼示例，並嘗試使用不同的值，以更好地理解雜湊集的工作原理。

my_hash_set = [
    [None],
    ['Jones'],
    [None],
    ['Lisa'],
    [None],
    ['Bob'],
    [None],
    ['Siri'],
    ['Pete'],
    [None]
]

def hash_function(value):
    return sum(ord(char) for char in value) % 10
    
def add(value):
    index = hash_function(value)
    bucket = my_hash_set[index]
    if value not in bucket:
        bucket.append(value)
        
def contains(value):
    index = hash_function(value)
    bucket = my_hash_set[index]
    return value in bucket

add('Stuart')

print(my_hash_set)
print('Contains Stuart:',contains('Stuart'))

接下來的兩頁將展示更好、更詳細的雜湊集和雜湊表實現。

嘗試下面的雜湊集模擬，以更好地瞭解雜湊集的基本工作原理。

雜湊表的使用

雜湊表很適合

• 檢查某個項是否在集合中（例如在圖書館中查詢一本書）。
• 儲存唯一項並快速找到它們（例如儲存電話號碼）。
• 將值連線到鍵（例如將姓名連線到電話號碼）。

雜湊表之所以在這些方面表現出色，最主要的原因是與陣列和連結串列相比，雜湊表非常快速，尤其是對於大型資料集。陣列和連結串列在搜尋和刪除方面具有 \(O(n)\) 的時間複雜度，而雜湊表平均只有 \(O(1)\)！在此處閱讀更多關於時間複雜度。

雜湊集與雜湊對映

雜湊表可以是雜湊集或雜湊對映。接下來的兩頁將更詳細地描述這些資料結構。

這是雜湊集和雜湊對映的異同

雜湊表總結

雜湊表元素儲存在稱為桶 (buckets) 的儲存容器中。

每個雜湊表元素都有一個稱為鍵 (key) 的唯一部分。

雜湊函式 (hash function) 接收元素的鍵以生成雜湊碼 (hash code)。

雜湊碼指明元素所屬的桶，這樣我們就可以直接訪問該雜湊表元素：修改它、刪除它，或者只是檢查它是否存在。特定雜湊函式的詳細解釋將在接下來的兩頁中給出。

當兩個雜湊表元素具有相同的雜湊碼時，就會發生衝突 (collision)，因為這意味著它們屬於同一個桶 (bucket)。衝突可以透過兩種方式解決。

連結串列 (Chaining) 是本教程中解決衝突的方法，透過使用陣列或連結串列允許多個元素存在於同一個桶中。

開放定址 (Open Addressing) 是解決衝突的另一種方法。在開放定址中，如果我們想儲存一個元素但該桶中已存在一個元素，則該元素將被儲存在下一個可用桶中。這可以透過多種方式完成，但我們在此不再進一步解釋開放定址。

結論

雜湊表是程式設計中的強大工具，可以幫助您高效地管理和訪問資料。

您選擇使用雜湊集還是雜湊對映取決於您的需求：是隻需要知道某項是否存在，還是需要查詢有關它的詳細資訊。