本文根據 數據結構和算法入門 視頻記錄

在前幾章的學習中，我們已經了解了數組和鏈表的基本特性，不管是數組還是鏈表，如果我們想要尋找一個特定的數值，時間復雜度都為O(n)。那有什么辦法用最快的速度來找到一個特定的元素呢，今天我們就來學習工業界中常用的數據結構“哈希表”，在哈希表中，不管是尋找、刪除、增加一個新元素，時間復雜度都是O(1)。

1. 哈希表的概念

哈希表以鍵值的方式來存儲元素，也就是說每個數據都是以鍵值（key，value）的方式存儲的，關鍵字（key）是不可重復的，而值是對應于鍵的。我們可以把哈希表簡單理解為一本字典，每個鍵（key）是一個單詞，而每個單詞都有自己對應的解釋，也就是值（value）。

1.1 哈希表的實現方式

那我們需要用什么數據結構實現哈希表呢？我們知道數組的特點是尋址容易，插入和刪除數組困難。而鏈表的特點是尋址困難，插入和刪除數據容易。那么我們能不能綜合兩者的特性，創建一種尋址容易，插入刪除也容易的數據結構呢？是的，哈希表就使用這么一種聰明的實現方式：“拉鏈法”，可以簡單理解為“一堆由鏈表組成的數組”，如圖所示：

可以看到哈希表的左側是數組，數組的每個成員包括一個指針，指向一個鏈表的頭節點，當然鏈表可能為空，也可能鏈接多個節點。

我們存儲鍵值對（key-value pair）的方式主要依靠鍵的特征，通過鍵的哈希值找到對應的數組下標，然后將其鍵值對添加到對應的鏈表中，尋找元素時，也是根據其鍵的哈希值，找到特定鏈表其對應的值。

那我們如何得到所謂的哈希值呢？我們先簡單理解一下此過程：哈希表使用哈希函數（Hash Function）將鍵（key）轉換成一個哈希值（整形數字），然后將該數組對數組長度取余，取余得到的數字就當做數組的下標，然后將其鍵值對添加到對應的鏈表中。尋找一個鍵所對應的值時，我們也是使用哈希函數將鍵轉換為對應的數組下標，并在其鏈表中定位到該關鍵字所對應的數值。

1.2 哈希函數（Hash Function）

可見哈希表能快速添加和查找元素的核心原因就是哈希函數，哈希函數能快速將一個數值轉換成哈希值（整數）。所以哈希表必須保持哈希值的計算一致，如果兩個哈希值是不相同的，那么這兩個哈希值的原始輸入也是不相同的。

那如果兩個不同的輸入得到相同的哈希值呢？這也就是所謂的哈希值沖突，這也是為什么我們結合數組和鏈表來實現哈希表，如果一個關鍵字對應的數組下標已經有其他元素了，只需要在其對應的鏈表后創建一個新的節點即可。

簡單來說，我們輸入關鍵字x，使用哈希函數f(x)計算出哈希值y，然后使用哈希值y來找特定的數組下標，并在對應位置插入新數據。在之后的實現中，我們會使用Java來實現哈希表，而JVM自動生成哈希值，我們只需要再將其哈希值和我們的哈希表數組長度取模（mod）就能拿到其對應下標。

1.3 哈希表支持的操作

為了幫助大家更好地理解哈希表的原理，我們來詳細描述一對鍵值被插入的過程，首先我們將鍵值對以鏈表節點的方式儲存，其節點包含自己的鍵和值。如果我們要將一對鍵值存入哈希表，我們需要使用哈希函數計算鍵的哈希值，并與哈希表的長度取模，然后找到對應的數組下標，如果該位置沒有其他鍵值節點，直接將其位置指向新節點即可。如果對應的位置有其他節點，直接將其新節點加到鏈表的最后面即可。

如果我們要查找一個鍵所對應的值，我們只需要計算該鍵對應的哈希值，找到數組下標所對應的頭節點后，從頭節點開始尋找我們所要的鍵值對。

以下哈希表支持的操作：

• get(K key)：通過特定的關鍵字拿到其所對應的值
• add(Key key, Value value)：將一對新的鍵值對加入哈希表
• remove(Key key)：通過關鍵字，刪除哈希表中的鍵值對
• getSize()：當前鍵值對的數量
• isEmpty()：查看哈希表是否為空

2. Java實現

下面我們就來使用Java實現哈希表，在我們定義的鍵值對中，關鍵字為字符串類型，數值為整數類型，以下是哈希表和哈希表節點的定義：

import java.util.ArrayList;public class HashMap {static class HashNode<String, Integer> {String key;Integer value;HashNode<String, Integer> next;public HashNode(String key, Integer value) {this.key = key;this.value = value;}}private ArrayList<HashNode<String, Integer>> bucketArray;private int numBuckets;private int size;public HashMap() {bucketArray = new ArrayList<>();numBuckets = 10;size = 0;for(int i = 0; i < numBuckets; i++) {bucketArray.add(null);}}
}

HashNode就是鍵值對節點的定義，其中key就是關鍵字，而value是關鍵字對應的數值，還包含了next指向下一個節點。HashMap則是哈希表的定義，其中包含了數據類型為ArrayList的bucketArray，大家可以將其理解為哈希表圖示左側的Array，bucketArray中存儲由HashNode組成的鏈表。HashMap還記錄了numBuckets代表哈希表數組的長度（不是節點的數量），size代表當前bucket的數量。在哈希表初始化時，我們初始化bucketArray，然后給numBuckets設置一個初始值10，初始化size，并在每個bucketArray上加上一個空的頭節點。

以下是getBucketIndex的定義：

private int getBucketIndex(String key) {int hashCode = key.hashCode();int index = hashCode % numBuckets;return index;
}

getBucketIndex的輸入是一個關鍵字，輸出是關鍵字對應的bucket位置。我們只需要通過Java內置的hashCode函數，將關鍵字轉化成整數形式的hashCode，然后將hashCode和numBuckets取模，就能得到對應bucket的指數。以下是add的定義：

public void add(String key, Integer value) {int bucketIndex = getBucketIndex(key);HashNode<String, Integer> head = bucketArray.get(bucketIndex);while (head != null) {if (head.key.equals(key)) {head.value = value;return;}head = head.next;}size++;head = bucketArray.get(bucketIndex);HashNode<String, Integer> newNode = new HashNode<String, Integer>(key, value);newNode.next = head;bucketArray.set(bucketIndex, newNode);if ((1.0 * size) / numBuckets >= 0.7) {ArrayList<HashNode<String, Integer>> temp = bucketArray;bucketArray = new ArrayList<>();numBuckets = 2 * numBuckets;size = 0;for (int i = 0; i < numBuckets; i++) {bucketArray.add(null);}for (HashNode<String, Integer> headNode : temp) {while(headNode != null) {add(headNode.key, headNode.value);headNode = headNode.next;}}}
}

在add方法中，我們使用getBucketIndex拿到關鍵字對應的bucket指數，并從對應bucket的頭節點開始，尋找是否有與其關鍵詞對應的節點，如果找到其節點，更新節點的數據，然后返回。如果沒有找到，我們創建一個新的鍵值對節點，然后將其next指針指向對應bukcet的頭節點，再把新節點更新為對應bucket的頭節點。如果當前鍵值對數量超過了bucket容量的70%，那么我們可以創建一個長度為當前數量兩倍的bucketArray，并把當前的節點轉移到新的bucketArray上。

get函數是通過關鍵字找到對應數組的函數：

public Integer get(String key) {int bucketIndex = getBucketIndex(key);HashNode<String, Integer> head = bucketArray.get(bucketIndex);while (head != null) {if (head.key.equals(key)) {return head.value;}head = head.next;}return null;
}

在此函數中，我們通過getBucketIndex拿到關鍵字對應的bucket指數，并拿到head頭指針，然后順著對應鏈表往下走，尋找是否有對應的關鍵字的節點，如果找到了，返回對應的數值，否則返回null。

public Integer remove(String key) {int bucketIndex = getBucketIndex(key);HashNode<String, Integer> head = bucketArray.get(bucketIndex);HashNode<String, Integer> prev = null;while (head != null) {if (head.key.equals(key))break;prev = head;head = head.next;}if (head == null) {return null;}size--;if (prev != null) {prev.next = head.next;} else {bucketArray.set(bucketIndex, head.next);}return head.value;
}

在remove函數中，我們通過getBucketIndex拿到對應的bucket指數，然后拿到頭指針，通過迭代next指針，我們可以使用刪除鏈表節點的方式來刪除對應節點。最后是兩個簡單函數size和isEmpty的定義：

public int size() {return size;
}public boolean isEmpty() {return size() == 0;
}

以上就是哈希表的定義啦，可見哈希表的插入刪除很快，可是當數組快滿，要進行數據遷移的話，性能下降得非常嚴重，所以設計數組長度時，必須知道將要儲存多少數據，才能設計出一個合理有效的哈希表。