HashMap（Python字典）設計原理與實現（上篇）——雜湊表的原理

在此前的四篇長文當中我們已經實現了我們自己的ArrayList和LinkedList，並且分析了ArrayList和LinkedList的JDK原始碼。 本篇文章主要跟大家介紹我們非常常用的一種資料結構HashMap，在本篇文章當中主要介紹他的實現原理，下篇我們自己動手實現我們自己的HashMap，讓他可以像JDK的HashMap一樣工作。

如果有公式渲染不了，可檢視這篇內容相同且可渲染公式的文章

HashMap初識

如果你使用過HashMap的話，那你肯定很熟悉HashMap給我們提供了一個非常方便的功能就是鍵值(key, value)查詢。比如我們通過學生的姓名查詢分數。

  public static void main(String[] args) {
    HashMap<String, Integer> map = new HashMap<>();
    map.put("學生A", 60);
    map.put("學生B", 70);
    map.put("學生C", 20);
    map.put("學生D", 85);
    map.put("學生E", 99);
    System.out.println("學生B的分數是：" + map.get("學生B"));
  }

我們知道HashMap給我們提供查詢get函數功能的時間複雜度為O(1)，他在常數級別的時間複雜度就可以查詢到結果。那它是如何做到的呢？

我們知道在計算機當中一個最基本也是唯一的，能夠實現常數級別的查詢的型別就是陣列，陣列的查詢時間複雜度為O(1)，我們只需要通過下標就能存取對應的資料。比如我們想存取下標為6的資料，就可以這樣：

String[] strs = new String[10];
strs[6] = "一無是處的研究僧";
System.out.println(strs[6]);

因此我們要想實現HashMap給我們提供的O(1)級別查詢的時間複雜度的話，就必須使用到陣列，而在具體的HashMap實現當中，比如說JDK底層也是採用陣列實現的。

HashMap整體設計

我們實現的HashMap需要滿足的最重要的功能是根據鍵(key)查詢到對應的值(value)，比如上面提到的根據學生姓名查詢成績。

因此我們可以有一個這樣的設計，我們可以根據資料的鍵值計算出一個數位（像這種可以將一個資料轉化成一個數位的叫做雜湊函數，計算出來的值叫做雜湊值我們後續將會仔細說明），將這個雜湊值作為陣列的下標，這樣的話鍵值和下標就有了對應關係了，我們可以在陣列對應的雜湊值為下標的位置儲存具體的資料，比如上面談到的成績，整個流程如下圖所示：

但是像這種雜湊函數計算出來的數值一般是沒有範圍的，因此我們通常通過雜湊函數計算出來的數值通常會經過一個求餘數操作(%)，對陣列的長度進行求餘數，否則求出來的數值將超過陣列的長度。比如陣列的長度是16，計算出來的雜湊值為186，那麼求餘數之後的結果為186%16=10，那麼我們可以將資料儲存在陣列當中下標為10的位置，下次我們來取的時候就取出下標為10位置的資料即可。

如何設計一個雜湊函數？

首先我們需要了解一個知識，那就是在計算機世界當中我們所含有的兩種最基本的資料型別就是，整型(short, int, long)和字串(String)，其他的資料型別可以由這些資料型別組合起來，下面我們來分析一下常見的資料型別的雜湊函數設計。

整型的雜湊函數

對於整型資料，他本來就是一個數值，因此我們可以直接將這個值返回作為他的雜湊值，而JDK中也是這麼實現的！JDK中實現整型的雜湊函數的方法：

    /**
     * Returns a hash code for a {@code int} value; compatible with
     * {@code Integer.hashCode()}.
     *
     * @param value the value to hash
     * @since 1.8
     *
     * @return a hash code value for a {@code int} value.
     */
    public static int hashCode(int value) {
        return value;
    }

字串的雜湊函數

我們知道字串底層儲存的還是用整型資料儲存的，比說說字串hello world，就可以使用字元陣列['h', 'e', 'l', 'l', 'o' , 'w', 'o', 'r', 'l', 'd']進行儲存，因為我們計算出來的這個雜湊值需要儘量不和別的資料計算出來的雜湊值衝突（這種現象叫做雜湊衝突，我們後面會仔細討論這個問題），因此我們要儘可能的充分利用字串裡面的每個字元資訊。我們來看一下JDK當中是怎麼實現字串的雜湊函數的

public int hashCode() {
    // hash 是 String 類當中一個私有的 int 變數，主要作用即儲存計算出來的雜湊值
    // 避免雜湊值重複計算 節約時間
    int h = hash; // 如果是第一次呼叫 hashCode 這個函數 hash 的值為0，也就是說 h 值為 0
    // value 就是儲存字元的字元陣列
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        // 更新 hash 的值
        hash = h;
    }
    return h;
}

上面的計算hashCode的程式碼，可以用下面這個公式表示：

• 其中s，表示儲存字串的字元陣列
• n表示字元陣列當中字元的個數

自定義型別的雜湊函數

比如我們自己定義了一個學生類，我們改設計他的雜湊函數，並且計算他的雜湊值呢？

class Student {
  String name;
  int grade;
}

我們可以根據上面提到的兩種雜湊函數，仿照他們的設計，設計我們自己的雜湊函數，比如像下面這樣。

class Student {
  String name;
  int grade;
    
  // 我們自己要實現的雜湊函數
  @Override
  public int hashCode() {
    return name.hashCode() * 31 + grade;
  }
    
  @Override
  public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    Student student = (Student) o;
    return grade == student.grade &&
        Objects.equals(name, student.name);
  }
}

事實上JDK也貼心的為我們實現了一個類，去計算我們自定義類的雜湊函數。

// 下面這個函數是我們自己設計的類 Student 的雜湊函數
@Override
public int hashCode() {
    return Objects.hash(name, grade);
}

// 下面這個函數為  Objects.hash 函數
public static int hash(Object... values) {
    return Arrays.hashCode(values);
}

// 下面這個函數為  Arrays.hashCode 函數
public static int hashCode(Object a[]) {
    if (a == null)
        return 0;

    int result = 1;

    for (Object element : a)
        result = 31 * result + (element == null ? 0 : element.hashCode());

    return result;
}

JDK幫助我們實現的雜湊函數，本質上就是將類當中所有的欄位封裝成一個陣列，然後像計算字串的雜湊值那樣去計算我們自定義類的雜湊值。

集合型別的雜湊函數

其實集合型別的雜湊函數也可以像字串那樣設計雜湊函數，我們來看一下JDK內部是如何實現集合類的雜湊函數的。

public int hashCode() {
    int hashCode = 1;
    // 遍歷集合當中的物件，進行雜湊值的計算
    for (E e : this)
        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
    return hashCode;
}

上述程式碼也可以用之前的公式來表示，其中s[i]表示集合當中第i個資料物件：

雜湊衝突

因為我們用的最終的陣列的下標是通過雜湊值取餘數得到的，那麼就有可能產生衝突。比如說我們的陣列長度為10，有兩個資料他們的雜湊值分別為8和28，他們對10取餘之後得到的結果都為8那麼改如何解決這個問題呢？

開放地址法（再雜湊法）

線性探測再雜湊

假設我們的雜湊函數為H，我們的陣列長度為m，我們的鍵為key，那麼我計算出來的下標為：

當我們有雜湊衝突的時候，我們計算下標的方法變為：

當我們第一次衝突的時候\(d_1 = 1\)，如果重新進行計算仍然衝突那麼\(d_2 = 2\) ......

比如在上圖當中我們首次計算的雜湊值\(H(key) = 5\)的結果等於5，如果有雜湊衝突，那麼下次計算出來的雜湊值為\((H(key) + 1) \% 12 = 6\)，如果還是衝突那麼計算出來的雜湊值為\((H(key) + 2) \% 12 = 7\) ......，直到找到一個空位置。談到這裡你可能會問，萬一都滿了呢？我們在下一小節再談這個問題。

二次探測再雜湊

這個雜湊方法和線性探測雜湊差不多，只不過\(d_i\)的值變化情況不一樣而已，大家可以參考線性探測進行分析，這個方法可以往陣列的兩個方法走，因為前面有一個而線性探測只能往陣列的一個方向走。此外這個方法走的距離比線性探測更大，因此可能可以在更小的衝突次數當中找到一個空位置。

偽亂數再雜湊

這個方式的大致策略和前面差不多，只不過\(d_i\)上稍微有所差異。

再雜湊法

我們可以準備多個雜湊函數，當使用一個雜湊函數產生衝突的時候，我們可以換一個雜湊函數，希望通過不同的雜湊函數得到不同的雜湊值，以解決雜湊衝突的問題。

鏈地址法

這個方法是目前使用比較多的方法，當產生雜湊衝突的時候，資料用一個連結串列將衝突的資料連結起來，比如像下面這樣：

以上就是一些常見的解決雜湊衝突的方法，因為都是文字說明沒有程式碼，你可能稍微有些難以理解，比如說我通過上面的方法儲存資料，那麼我之後怎麼拿到我存進去的資料呢？好像放進去就拿不出來了呀