【演演算法與資料結構 10】雜湊表——高效查詢的利器

文章目錄

前言：

之前，我們先後學習了線性表、陣列、字串和樹，它們普遍都存在這樣的缺陷，那就是資料數值條件的查詢，都需要對全部資料或者部分資料進行遍歷。那麼，有沒有一種方法可以省去資料比較的過程，從而進一步提升數值條件查詢的效率呢？

答案當然是：有！這一課時我們就來介紹這樣一種高效率的查詢神器：雜湊表。

一、什麼是雜湊表

雜湊表名字源於 Hash，也可以叫作雜湊表。雜湊表是一種特殊的資料結構，它與陣列、連結串列以及樹等我們之前學過的資料結構相比，有很明顯的區別。

在這裡插入圖片描述

1.1 雜湊表的原理

雜湊表是一種資料結構，它使用雜湊函數組織資料，以支援快速插入和搜尋。雜湊表的核心思想就是使用雜湊函數將鍵對映到儲存桶。更確切地說：

當我們插入一個新的鍵時，雜湊函數將決定該鍵應該分配到哪個桶中，並將該鍵儲存在相應的桶中；
當我們想要搜尋一個鍵時，雜湊表將使用相同的雜湊函數來查詢對應的桶，並只在特定的桶中進行搜尋。

下面舉一個簡單的例子，我們來理解下：

在這裡插入圖片描述
在範例中，我們使用 y = x ％ 5 作為雜湊函數。讓我們使用這個例子來完成插入和搜尋策略：

插入：我們通過雜湊函數解析鍵，將它們對映到相應的桶中。例如，1987 分配給桶 2，而 24 分配給桶 4。
搜尋：我們通過相同的雜湊函數解析鍵，並僅在特定儲存桶中搜尋。例如，如果我們搜尋 23，將對映 23 到 3，並在桶 3 中搜尋。我們發現 23 不在桶 3 中，這意味著 23 不在雜湊表中。

1.2 設計雜湊函數

雜湊函數是雜湊表中最重要的元件，該雜湊表用於將鍵對映到特定的桶。在之前的範例中，我們使用 y = x % 5 作為雜湊函數，其中 x 是鍵值，y 是分配的桶的索引。

雜湊函數將取決於鍵值的範圍和桶的數量。下面是一些雜湊函數的範例：
在這裡插入圖片描述
雜湊函數的設計是一個開放的問題。其思想是儘可能將鍵分配到桶中，理想情況下，完美的雜湊函數將是鍵和桶之間的一對一對映。然而，在大多數情況下，雜湊函數並不完美，它需要在桶的數量和桶的容量之間進行權衡。

當然，我們也可以自定義一些雜湊函數。一般的方法有：

直接客製化法。雜湊函數為關鍵字到地址的線性函數。如，H (key) = a * key + b。這裡，a 和 b 是設定好的常數。
數位分析法。假設關鍵字集合中的每個關鍵字 key 都是由 s 位數位組成（k1,k2,…,Ks），並從中提取分佈均勻的若干位組成雜湊地址。
平方取中法。如果關鍵字的每一位都有某些數位重複出現，並且頻率很高，我們就可以先求關鍵字的平方值，通過平方擴大差異，然後取中間幾位作為最終儲存地址。
摺疊法。如果關鍵字的位數很多，可以將關鍵字分割為幾個等長的部分，取它們的疊加和的值（捨去進位）作為雜湊地址。
除留餘數法。預先設定一個數 p，然後對關鍵字進行取餘運算。即地址為 key % p。

二、解決雜湊衝突

理想情況下，如果我們的雜湊函數是完美的一對一對映，我們將不需要處理衝突。不幸的是，在大多數情況下，衝突幾乎是不可避免的。例如，在我們之前的雜湊函數（y = x ％ 5）中，1987 和 2 都分配給了桶 2，這就是一個雜湊衝突。

解決雜湊衝突應該要思考以下幾個問題：

如何組織在同一個桶中的值？
如果為同一個桶分配了太多的值，該怎麼辦？
如何在特定的桶中搜尋目標值？

那麼一旦發生衝突，我們該如何解決呢？

常用的方法有兩種：開放定址法和鏈地址法。

2.1 開放定址法

即當一個關鍵字和另一個關鍵字發生衝突時，使用某種探測技術在雜湊表中形成一個探測序列，然後沿著這個探測序列依次查詢下去。當碰到一個空的單元時，則插入其中。

常用的探測方法是線性探測法。比如有一組關鍵字 {12，13，25，23}，採用的雜湊函數為 key % 11。當插入 12，13，25 時可以直接插入，地址分別為 1、2、3。而當插入 23 時，雜湊地址為 23 % 11 = 1。

然而，地址 1 已經被佔用，因此沿著地址 1 依次往下探測，直到探測到地址 4，發現為空，則將 23 插入其中。如下圖所示：
在這裡插入圖片描述

2.2 鏈地址法

將雜湊地址相同的記錄儲存在一張線性連結串列中。例如，有一組關鍵字 {12,13,25,23,38,84,6,91,34}，採用的雜湊函數為 key % 11。如下圖所示：
在這裡插入圖片描述

三、雜湊表的應用

3.1 雜湊表的基本操作

在很多高階語言中，雜湊函數、雜湊衝突都已經在底層完成了黑盒化處理，是不需要開發者自己設計的。也就是說，雜湊表完成了關鍵字到地址的對映，可以在常數級時間複雜度內通過關鍵字查詢到資料。

至於實現細節，比如用了哪個雜湊函數，用了什麼衝突處理，甚至某個資料記錄的雜湊地址是多少，都是不需要開發者關注的。接下來，我們從實際的開發角度，來看一下雜湊表對資料的增刪查操作。

雜湊表中的增加和刪除資料操作，不涉及增刪後對資料的挪移問題（陣列需要考慮），因此處理就可以了。

雜湊表查詢的細節過程是：對於給定的 key，通過雜湊函數計算雜湊地址 H (key)。

如果雜湊地址對應的值為空，則查詢不成功。
反之，則查詢成功。

雖然雜湊表查詢的細節過程還比較麻煩，但因為一些高階語言的黑盒化處理，開發者並不需要實際去開發底層程式碼，只要呼叫相關的函數就可以了。

3.2 雜湊表的優缺點

優勢：它可以提供非常快速的插入-刪除-查詢操作，無論多少資料，插入和刪除值需要接近常數的時間。在查詢方面，雜湊表的速度比樹還要快，基本可以瞬間查詢到想要的元素。
不足：雜湊表中的資料是沒有順序概念的，所以不能以一種固定的方式（比如從小到大）來遍歷其中的元素。在資料處理順序敏感的問題時，選擇雜湊表並不是個好的處理方法。同時，雜湊表中的
key 是不允許重複的，在重複性非常高的資料中，雜湊表也不是個好的選擇。

四、設計雜湊對映

4.1 設計要求

要求：

不使用任何內建的雜湊表庫設計一個雜湊對映具體地說，設計應該包含以下的功能：

put(key, value)：向雜湊對映中插入(鍵,值)的數值對。如果鍵對應的值已經存在，更新這個值。
get(key)：返回給定的鍵所對應的值，如果對映中不包含這個鍵，返回-1。
remove(key)：如果對映中存在這個鍵，刪除這個數值對。

範例：

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);          
hashMap.put(2, 2);         
hashMap.get(1);            // 返回 1
hashMap.get(3);            // 返回 -1 (未找到)
hashMap.put(2, 1);         // 更新已有的值
hashMap.get(2);            // 返回 1 
hashMap.remove(2);         // 刪除鍵為2的資料
hashMap.get(2);            // 返回 -1 (未找到)

注意：

 所有的值都在 [0, 1000000]的範圍內。
 操作的總數目在[1, 10000]範圍內。
 不要使用內建的雜湊庫。

4.2 設計思路

雜湊表是一個在不同語言中都有的通用資料結構。例如，Python 中的 dict 、C++中的 map 和 Java 中的 Hashmap。雜湊表的特性是可以根據給出的 key 快速存取 value。

最簡單的思路就是用模運算作為雜湊方法，為了降低雜湊碰撞的概率，通常取素數的模，例如模 2069。

定義 array 陣列作為儲存空間，通過雜湊方法計算陣列下標。為了解決雜湊碰撞（即鍵值不同，但對映下標相同），利用桶來儲存所有對應的數值。桶可以用陣列或連結串列來實現，在下面的具體實現中， Python 中用的是陣列。

定義雜湊表方法，get()，put() 和 remove()，其中的定址過程如下所示：

對於一個給定的鍵值，利用雜湊方法生成鍵值的雜湊碼，利用雜湊碼定位儲存空間。對於每個雜湊碼，都能找到一個桶來儲存該鍵值所對應的數值。
在找到一個桶之後，通過遍歷來檢查該鍵值對是否已經存在。

在這裡插入圖片描述

4.3 實際案例

Python實現如下：

class Bucket:
    def __init__(self):
        self.bucket = []

    def get(self, key):
        for (k, v) in self.bucket:
            if k == key:
                return v
        return -1

    def update(self, key, value):
        found = False
        for i, kv in enumerate(self.bucket):
            if key == kv[0]:
                self.bucket[i] = (key, value)
                found = True
                break

        if not found:
            self.bucket.append((key, value))

    def remove(self, key):
        for i, kv in enumerate(self.bucket):
            if key == kv[0]:
                del self.bucket[i]


class MyHashMap(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        # better to be a prime number, less collision
        self.key_space = 2069
        self.hash_table = [Bucket() for i in range(self.key_space)]


    def put(self, key, value):
        """
        value will always be non-negative.
        :type key: int
        :type value: int
        :rtype: None
        """
        hash_key = key % self.key_space
        self.hash_table[hash_key].update(key, value)


    def get(self, key):
        """
        Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
        :type key: int
        :rtype: int
        """
        hash_key = key % self.key_space
        return self.hash_table[hash_key].get(key)


    def remove(self, key):
        """
        Removes the mapping of the specified value key if this map contains a mapping for the key
        :type key: int
        :rtype: None
        """
        hash_key = key % self.key_space
        self.hash_table[hash_key].remove(key)


# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)

複雜度分析：

時間複雜度：每個方法的時間複雜度都為 O(N/K)，其中 N 為所有可能鍵值的數量，K 為雜湊表中預定義桶的數量，在這裡 K 為 2069。這裡我們假設鍵值是均勻地分佈在所有桶中的，桶的平均大小為 N/K，在最壞情況下需要遍歷完整個桶，因此時間複雜度為 O(N/K)。
空間複雜度：O(K+M)，其中 K 為雜湊表中預定義桶的數量，M 為雜湊表中已插入鍵值的數量。

今天的分享就到這裡啦，希望對你的學習有所幫助！

在這裡插入圖片描述

【演演算法與資料結構 10】雜湊表——高效查詢的利器

文章目錄

一、什麼是雜湊表

1.1 雜湊表的原理

1.2 設計雜湊函數

二、解決雜湊衝突

2.1 開放定址法

2.2 鏈地址法

三、雜湊表的應用

3.1 雜湊表的基本操作

3.2 雜湊表的優缺點

四、 設計雜湊對映

4.1 設計要求

4.2 設計思路

4.3 實際案例

養成習慣，先贊後看！你的支援是我創作的最大動力！

四、設計雜湊對映