專案地址：https://gitee.com/caochenlei/data-structures

第一章 哈希表介紹

設計一個寫字樓通訊錄，存放該寫字樓所有公司的通訊資訊，座機號碼作為 key（假設座機號碼最長是 8 位），公司詳情（名稱、地址等）作為 value，要求添加、洗掉、搜索的時間復雜度要求是 O(1)，實作代碼如下：

我們發現上述代碼可以實作要求，但是空間復雜度極大，空間利用率極低，非常浪費記憶體空間，其實陣列 companies 就是一個哈希表，

哈希表（Hash Table，也叫散串列），是根據關鍵碼值（Key Value）而直接進行訪問的資料結構，也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度，這個映射函式叫做 哈希函式（散列函式） ，存放記錄的陣列叫做 哈希表（散串列） ，

第二章 哈希沖突

哈希沖突（Hash Collision，也叫哈希碰撞），簡單的來說就是：2 個不同的 key，經過哈希函式計算出相同的結果，

解決哈希沖突有很多種方法，我們這里重點介紹鏈地址法（Separate Chaining），簡單的來說就是：通過鏈表將同一index元素串起來，

第三章 哈希函式

哈希函式指將哈希表中元素的關鍵鍵值映射為元素存盤位置的函式，

哈希表中哈希函式的實作步驟，大概如下：

• 先生成 key 的哈希值（必須是整數），
• 再讓 key 的哈希值跟陣列的大小進行相關運算，生成一個索引值，

為了提高效率，可以使用 & 位運算取代 % 運算，但是這是有前提的，那就是必須將陣列的長度設計為 2 的冪（2ⁿ），

良好的哈希函式，可以讓哈希值更加均勻分布，減少哈希沖突次數，提升哈希表的性能，

那么問題又來了，對于 key 來說，可能是不同的資料型別，那如何計算他的哈希值呢？

key 的常見種類可能有：整數、浮點數、字串、自定義物件，不同種類的 key，哈希值的生成方式不一樣，但目標是一致的，盡量讓每個 key 的哈希值是唯一的，盡量讓 key 的所有資訊參與運算，并且最終生成的哈希值必須是一個整數，

Integer整數： 整數值當做哈希值，比如 10 的哈希值就是 10

Float浮點數： 將存盤的二進制格式轉為整數值

Long整數、Double浮點數：

這個 >>> 和 ^ 的作用是什么？

由于Long和Double的底層二進制位數遠遠超過了Integer的32位，為了滿足盡量讓 key 的所有資訊參與運算，所以通過 >>> 右移，讓當前值的高32位和低32位進行運算，混合計算出32位的整數哈希值，最終計算出來的數值高32無意義，舍去即可，這里給出一個案例：

字串：

我們首先來思考一個問題，整數 5489 是如何計算出來的？

5489 = 5 ? 10³ + 4 ? 10² + 8 ? 10¹ + 9 ? 10⁰

而我們的字串是由若干個字符組成的，比如字串 jack，由 j、a、c、k 四個字符組成，字符的本質就是一個整數，

因此，jack 的哈希值可以表示為 j ? n³ + a ? n² + c ? n¹ + k ? n⁰，等價于 [ ( j ? n + a ) ? n + c ] ? n + k ，

在JDK中，乘數 n 為 31，為什么用 31？

由于 31 不僅僅是符合2ⁿ – 1，它還是個奇素數（既是奇數，又是素數，也就是質數），素數和其他數相乘的結果比其他方式更容易產成唯一性，減少哈希沖突，有那么多素數，那為啥是31呢，是經過觀測分布結果后的選擇，并且JVM會將 31 * i 優化成 (i << 5) – i，

自定義物件：

自定義物件需要實作 equals 和 hashCode 方法，以下示例代碼的 equals 和 hashCode 方法由 idea 自動生成，

注意：這里實作 equals 方法和生成 hashCode 并沒有直接聯系，僅僅是為了后邊寫代碼方便，也就一塊生成了，

這里給出 Objects.hash(...) 的底層實作：

第四章 哈希表實作

【實作代碼】

public class HashTable<Key, Value> {
    private int M;                              //哈希表的大小
    private int N;                              //鍵值對的對數
    private SymbolTable<Key, Value>[] table;    //存放鏈表物件的陣列，這里采用無序符號表，也可以用紅黑樹

    public HashTable(int M) {
        this.M = M;
        table = new SymbolTable[M];
        for (int i = 0; i < M; i++) {
            table[i] = new SymbolTable<>();
        }
    }

    //獲取哈希表鍵值個數
    public int size() {
        return N;
    }

    //判斷哈希表是否為空
    public boolean isEmpty() {
        return N == 0;
    }

    //獲取指定key哈希值
    private int hash(Key key) {
        return key.hashCode() & (table.length - 1);
    }

    //向哈希表中添加鍵值
    public void put(Key key, Value value) {
        table[hash(key)].put(key, value);
        N++;
    }

    //洗掉哈希表中的key
    public void delete(Key key) {
        table[hash(key)].delete(key);
        N--;
    }

    //獲取key對應的value
    public Value get(Key key) {
        return table[hash(key)].get(key);
    }

    //獲取哈希表中所有key的集合
    public Set<Key> keySet() {
        Set<Key> keySet = new HashSet<>();
        for (SymbolTable<Key, Value> keyValueSymbolTable : table) {
            keySet.addAll(keyValueSymbolTable.keySet());
        }
        return keySet;
    }

    //獲取哈希表中所有value的集合
    public Set<Value> valueSet() {
        Set<Value> valueSet = new HashSet<>();
        for (SymbolTable<Key, Value> keyValueSymbolTable : table) {
            valueSet.addAll(keyValueSymbolTable.valueSet());
        }
        return valueSet;
    }
}

【測驗代碼】

public class HashTableTest {
    public static void main(String[] args) {
        HashTable<Integer, String> hashTable = new HashTable<>(16);

        hashTable.put(1, "劉備");
        hashTable.put(2, "張飛");
        hashTable.put(3, "關羽");
        hashTable.put(4, "趙云");
        hashTable.put(5, "曹操");
        hashTable.put(6, "呂布");

        System.out.println(hashTable.size());
        System.out.println(hashTable.isEmpty());
        System.out.println(hashTable.keySet());
        System.out.println(hashTable.valueSet());
        for (Integer key : hashTable.keySet()) {
            System.out.println(key + "：" + hashTable.get(key));
        }
        for (Integer key : hashTable.keySet()) {
            hashTable.delete(key);
        }
        System.out.println(hashTable.size());
        System.out.println(hashTable.isEmpty());
        System.out.println(hashTable.keySet());
        System.out.println(hashTable.valueSet());
    }
}

【運行效果】

6
false
[1, 2, 3, 4, 5, 6]
[關羽, 張飛, 呂布, 劉備, 曹操, 趙云]
1：劉備
2：張飛
3：關羽
4：趙云
5：曹操
6：呂布
0
true
[]
[]