【演算法與資料結構 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 為哈希表中已插入鍵值的數量，

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

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