HashMap設計原理與實作（下篇）200行帶你寫自己的HashMap！！！

我們在上篇文章哈希表的設計原理當中已經大體說明了哈希表的實作原理，在這篇文章當中我們將自己動手實作我們自己的HashMap，完整的代碼在文章末尾，

在本篇文章當中主要通過線性探測法，從最基本的陣列再到HashMap當中節點的設計，一步一步的實作一個能夠實作Key、Value映射的容器，寫出我們自己的哈希表MyHashMap，讓可以具備HashMap最常見的兩個功能，put和get方法，

我們的陣列當中應該存盤什么樣資料？

在上篇哈希表的設計原理當中我們已經仔細說明，在HashMap當中我們是使用陣列去存盤具體的資料的，那么在我們的陣列當中應該存盤什么樣的資料呢？假設在HashMap的陣列當中存盤的資料型別為Node，那么這個類需要有哪些欄位呢？

首先一點我們肯定需要存盤Value值，因為我們最終需要通過get方法從HashMap當中取出我們所需要的值，
第二點當我們通過get方法去取值的時候是通過Key（鍵值）去取的，當哈希值產生沖突的時候，我們不僅需要通過哈希值確定位置，還需要通過比較通過函式get傳遞的Key和陣列當當中存盤的資料的key是否相等，因此我們需要存盤鍵值Key，
第三點為了避免重復計算哈希值（因為有的物件的哈希值計算還是比較費時間），我們可以使用一個欄位去存盤計算好的哈希值，

根據以上三點我們的Node類的設計如下：

  private static class Node<K, V> {
    /**
     * 用于存盤我們計算好的 key 的哈希值
     */
    final int hash;

    /**
     * Key Value 中的 Key 物件
     */
    final K key;

    /**
     * Key Value 中的 Value 物件
     */
    V value;

    /**
     * hash 是鍵值 key 的哈希值  key 是鍵 value 是值
     * @param hash
     * @param key
     * @param value
     */
    public Node(int hash, K key, V value) {
      this.hash = hash;
      this.key = key;
      this.value = https://www.cnblogs.com/Chang-LeHung/p/value;
    }

    public V setValue(V newValue) {
      V oldValue = newValue;
      value = newValue;
      return oldValue;
    }

    @Override
    public String toString() {
      return key +"=" + value;
    }
  }

我們的陣列長度應該怎么設定？

在討論這個問題之前我們首先來回歸一下位運算的操作，在計算機當中資料都是二進制存盤那么二進制運算是如何操作的呢？

int a = 7;
int b = 3;
System.out.println(a & b); // 輸出結果為3

上述代碼的位運算操作如下：

進行位運算是，二進制數的對應位置進行相應的操作，&運算的結果只有兩個位元位的資料都是1時，運算結果才等于1，其余的情況都為0，因此3 & 7 = 3，

通過put函式放入HashMap當中的資料首先需要將key的哈希值與陣列的長度進行取余運算得到對應的下標，再將資料放入到陣列對應的下標當中，但是在實際的操作當中我們將底層陣列的長度設定為2的整數次冪，并且使用位運算&去進行取余數操作，而這樣操作主要有一下三點原因：

位運算&的程式執行效率，比取余%操作更加高效，需要的時間越短，
當陣列的長度為2的整數次冪的時候，得到的下標越均勻，造成的哈希沖突更少，
任何一個數a對\(2^n\)取余數得到的結果與a跟\(2^n - 1\)進行&操作結果是相等的，即：

\[a \% 2^n = a \& (2^n - 1) \]

我們現在先來解釋一下第三點，令a = 127，n = 4，那么：127%16 = 15，127 & 15 = 15，

首先我們需要明白求余數的意義是什么？127對16取余，就是用127一直減去16，直到某個結果小于16為止，得到的值為求余數結果，

上圖當中紅框當中包括的位置就是小于16的部分

上圖當中紅框框住的部分是16的倍數，因此在求余數的時候上圖當中紅框框住的部分就沒有了，都為0，只會剩下小于16的部分，這跟15進行&操作得到的結果是一致的，這也就解釋了上面提到的第三條，

在第二條中我們提到了使用陣列長度為2的整數次冪可以在一定程度上減少哈希沖突，因為進行下標運算的時候是與\(2^n - 1\)進行&操作，而\(2^n - 1\)的二進制表示最后一部分位置上的數都是1，

比如下圖中的資料都是2的整數次冪減一之后的結果：

RoundUp函式

因為我們需要陣列的長度是2的整數次冪，而我們之后在初始化函式當中會允許用戶輸入一個陣列長度的大小，但是用戶輸入的數字可能不是2的整數次冪，因此我們需要將用戶輸入的資料變成2的整數次冪，我們可以將用戶輸入的資料變成大于等于這個數的最小的2的整數次冪，

比如說如果用戶輸入的是12我們需要將其變成16，如果輸入的是28我們需要將其變成32，我們可以通過下面這個函式做到這一點：

  /**
   * 回傳第一個大于或者等于 capacity 且為 2 的整數次冪的那個數
   * @param capacity
   * @return
   */
  static int roundUp(int capacity) {
    int n = capacity - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    // 如果最終得到的資料小于 0 則初始長度為 1
    // 如果長度大于我們所允許的最大的容量 則將初始長度設定為我們
    // 所允許的最大的容量
    // MAXIMUM_CAPACITY = 1 << 30;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
  }

上面的代碼還是很難理解的，讓我們一點一點的來分析，首先我們使用一個2的整數次冪的數進行上面移位操作的操作！

從上圖當中我們會發現，我們咋一個數的二進制數的32位放一個1，經過移位之后最終32位的位元數字全部變成了1，根據上面數字變化的規律我們可以發現，任何一個位元經過上面移位的變化，這個位元后面的31個位元位都會變成1，像下圖那樣：

因此上述的移位操作的結果只取決于最高一位的位元值為1，移位操作后它后面的所有位元位的值全為1，而在上面函式的最后，如果最終的容量沒有大于我們設定的最大容量MAXIMUM_CAPACITY，我們回傳的結果就是上面移位之后的結果 +1，又因為移位之后最高位的1到最低位的1之間的位元值全為1，當我們+1之后他會不斷的進位，最終只有一個位元位置是1，因此它是2的整數倍，

在roundUp函式當中，給初始容量減了個1，這樣做的原因是讓這個函式的回傳值大于等于傳入的引數capacity：

roundUp(4) == 4 // 就是當傳入的資料已經是 2 的整數次冪的時候也回傳傳入的值
roundUp(3) == 4
roundUp(5) == 8

哈希函式

  /**
   * 這個 key 是 put 函式傳進來的 key
   * @param key
   * @return
   */
  static int hash(Object key) {
    int h;
    // 呼叫物件自己實作的 hashCode 方法
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

上面的函式之所以要將物件的哈希值右移16，是因為我們的陣列的長度一般不會超過\(2^{16}\)，因為\(2^{16}\)已經是一個比較大的值了，因此當哈希值與\(2^n - 1\)進行&操作的時候，高位通常沒有使用到，這樣做的原理是可以充分利用資料哈希值當中的資訊，

擴容機制

當我們一直往HashMap加入資料的話，陣列遲早會被用完，當陣列用完之后我們就需要進行擴容，我們要記住一點擴容之后的陣列長度也需要滿足2的整數次冪，因為上面我們已經提到陣列的長度需要是2的整數次冪，因此擴容之后的長度也需要保持是2的整數次冪，

但是在實際情況當中我們并不是當陣列完全被使用完之后才進行擴容，因為如果陣列快被使用完之后，再加入資料產生哈希沖突的可能性就會很大，因此我們通常會設定一個負載因子(load factor)，當陣列的使用率超過這個值的時候就進行擴容，即當(陣列長度為L，陣列當中資料個數為S，負載因子為F)：

\[S \ge L \times F \]

Java代碼實作HashMap

先看一下我們需要的欄位

public class MyHashMap<K, V> {

  /**
   * 默認陣列的容量
   */
  static final int DEFAULT_CAPACITY = 16;

  /**
   * 默認負載因子
   */
  static final float DEFAULT_LOAD_FACTOR = 0.75f;

  /**
   * 哈希表中陣列的最大長度
   */
  static final int MAXIMUM_CAPACITY = 1 << 30;

  /**
   * 真正存盤資料的陣列
   */
  Node<K, V>[] hashTable;

  /**
   * 哈希表陣列當中存盤的資料的個數
   */
  int size;

  /**
   * 哈希表當中的負載因子
   */
  float loadFactor = 0.75f;

  /**
   * 哈希表擴容的閾值 = 哈希表的長度 x 負載因子
   * 當超過這個值的時候進行擴容
   */
  int threshold;
}

`put`函式的實作

public void put(K key, V value) {

    if (null == key)
        throw new RuntimeException("哈希表的鍵值不能為空");
    int hash = hash(key);
    // 這表示使用了空參建構式 而且是第一次呼叫 put 函式
    if (null == hashTable) {
        hashTable = (Node<K, V>[]) new Node[DEFAULT_CAPACITY];
        // 計算陣列長度對應的擴容閾值
        threshold = (int)(hashTable.length * loadFactor);
        // 進行 & 運算得到資料下標
        hashTable[hash & (DEFAULT_CAPACITY - 1)] = new Node<K, V>(hash, key, value);
    }else {
        int n = hashTable.length;
        int idx = hash & (n - 1);
        // 如果陣列不為空 說明已經有資料存在了
        // 如果哈希值相同的話說明是同一個物件了
        // 也可以進行跳出
        while (null != hashTable[idx] && !key.equals(hashTable[idx].key))
            idx = (idx + 1) & (n - 1);
        // 如果是通過 null != hashTable[idx] 條件跳出則是新添加資料
        // 如果是通過 !key.equals(hashTable[idx].key) 條件跳出
        // 則是因為 put 函式的 key 已經存在這次操作是更新資料
        hashTable[idx] = new Node<K, V>(hash, key, value);
    }
    // 如果陣列當中使用過的資料超過閾值
    if (++size > threshold) {
        resize();
    }
}

擴容(`resize`函式)實作

  /**
   * 如果你已經看懂 put 函式的代碼，那這個代碼就比較簡單了
   * 因為只是單純的將原陣列的資料重新進行哈希并且加入到新陣列
   */
  private void resize() {
    int n = (hashTable.length << 1);
    threshold = (int) (n * loadFactor);
    Node<K, V>[] oldTable = hashTable;
    hashTable = (Node<K, V>[]) new Node[n];
    for (int i = 0; i < oldTable.length; i++)  {
      if (null == oldTable[i])
        continue;
      Node<K, V> node = oldTable[i];
      int idx = node.hash & (n - 1);
      while (null != hashTable[idx] && !node.key.equals(hashTable[idx].key))
        idx = (idx + 1) & (n - 1);
      hashTable[idx] = node;
    }
  }

`get`函式實作

public V get(K key) {
    if (null == key)
        throw new RuntimeException("查詢的鍵值不能為空");
    int hash = hash(key);
    int n = hashTable.length;
    int idx = hash & (n - 1);
    if (null == hashTable[idx])
        return null;
    // 這里同樣需要進行線性探測
    // 因為哈希值相同時 key 值
    // 不一定相同 因為會有哈希沖突
    for (;;) {
        // 當陣列當中的資料不為空
        // 且資料當中的哈希值和傳入 key
        // 的哈希值相等 而且鍵值相等
        // 就是找到了對應的資料
        if (null != hashTable[idx]
            && hash == hashTable[idx].hash
            && key.equals(hashTable[idx].key))
            break;
        idx = (idx + 1) & (n -1);
    }
    return hashTable[idx].value;
}

完整代碼

import java.util.*;

public class MyHashMap<K, V> {

  /**
   * 默認陣列的容量
   */
  static final int DEFAULT_CAPACITY = 16;

  /**
   * 默認負載因子
   */
  static final float DEFAULT_LOAD_FACTOR = 0.75f;

  /**
   * 哈希表中陣列的最大長度
   */
  static final int MAXIMUM_CAPACITY = 1 << 30;

  /**
   * 真正存盤資料的陣列
   */
  Node<K, V>[] hashTable;

  /**
   * 哈希表陣列當中存盤的資料的個數
   */
  int size;

  /**
   * 哈希表當中的負載因子
   */
  float loadFactor = 0.75f;

  /**
   * 哈希表擴容的閾值 = 哈希表的長度 x 負載因子
   * 當超過這個值的時候進行擴容
   */
  int threshold;

  /**
   * 回傳第一個大于或者等于 capacity 且為 2 的整數次冪的那個數
   * @param capacity
   * @return
   */
  static int roundUp(int capacity) {
    int n = capacity - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    // 如果最終得到的資料小于 0 則初始長度為 1
    // 如果長度大于我們所允許的最大的容量 則將初始長度設定為我們
    // 所允許的最大的容量
    // MAXIMUM_CAPACITY = 1 << 30;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
  }

  private static class Node<K, V> {
    /**
     * 用于存盤我們計算好的 key 的哈希值
     */
    final int hash;

    /**
     * Key Value 中的 Key 物件
     */
    final K key;

    /**
     * Key Value 中的 Value 物件
     */
    V value;

    /**
     * hash 是鍵值 key 的哈希值  key 是鍵 value 是值
     * @param hash
     * @param key
     * @param value
     */
    public Node(int hash, K key, V value) {
      this.hash = hash;
      this.key = key;
      this.value = https://www.cnblogs.com/Chang-LeHung/p/value;
    }

    public V setValue(V newValue) {
      V oldValue = newValue;
      value = newValue;
      return oldValue;
    }

    @Override
    public String toString() {
      return key +"=" + value;
    }
  }

  public MyHashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
  }

  public MyHashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity <= 0) {
      throw new RuntimeException("初始化長度不能小于0");
    }
    if (initialCapacity > MAXIMUM_CAPACITY)
      initialCapacity = MAXIMUM_CAPACITY;

    initialCapacity = roundUp(initialCapacity);
    hashTable = (Node<K, V>[]) new Node[initialCapacity];
    this.loadFactor = loadFactor;
    threshold = (int) (loadFactor * initialCapacity);
  }

  public MyHashMap(int capacity) {
    this(capacity, DEFAULT_LOAD_FACTOR);
  }

  static int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

  public void put(K key, V value) {

    if (null == key)
      throw new RuntimeException("哈希表的鍵值不能為空");
    int hash = hash(key);

    if (null == hashTable) {
      hashTable = (Node<K, V>[]) new Node[DEFAULT_CAPACITY];
      threshold = (int)(hashTable.length * loadFactor);
      hashTable[hash & (DEFAULT_CAPACITY - 1)] = new Node<K, V>(hash, key, value);
    }else {
      int n = hashTable.length;
      int idx = hash & (n - 1);
      while (null != hashTable[idx] && !key.equals(hashTable[idx].key))
        idx = (idx + 1) & (n - 1);
      hashTable[idx] = new Node<K, V>(hash, key, value);
    }
    if (++size > threshold) {
      resize();
    }
  }

  private void resize() {
    int n = (hashTable.length << 1);
    threshold = (int) (n * loadFactor);
    Node<K, V>[] oldTable = hashTable;
    hashTable = (Node<K, V>[]) new Node[n];
    for (int i = 0; i < oldTable.length; i++)  {
      if (null == oldTable[i])
        continue;
      Node<K, V> node = oldTable[i];
      int idx = node.hash & (n - 1);
      while (null != hashTable[idx] && !node.key.equals(hashTable[idx].key))
        idx = (idx + 1) & (n - 1);
      hashTable[idx] = node;
    }
  }

  public V get(K key) {
    if (null == key)
      throw new RuntimeException("查詢的鍵值不能為空");
    int hash = hash(key);
    int n = hashTable.length;
    int idx = hash & (n - 1);
    if (null == hashTable[idx])
      return null;
    for (;;) {
      if (null != hashTable[idx]
          && hash == hashTable[idx].hash
          && key.equals(hashTable[idx].key))
        break;
      idx = (idx + 1) & (n -1);
    }
    return hashTable[idx].value;
  }

  @Override
  public String toString() {
    StringBuilder builder = new StringBuilder();
    builder.append("[");
    for (int i = 0; i < hashTable.length; i++) {
      builder.append(hashTable[i]);
      builder.append(", ");
    }
    builder.delete(builder.length() - 2, builder.length());
    builder.append("]");
    return builder.toString();
  }
}

測驗我們自己實作的`HashMap`

測驗代碼：

public static void main(String[] args) {

    MyHashMap<String, Integer> map = new MyHashMap<>();
    Random random = new Random();
    HashMap<String, Integer> map1 = new HashMap<>();
    ArrayList<String> strs = new ArrayList<>();
    ArrayList<Integer> list = new ArrayList<>();
    for (int i = 0; i < 1000000; i++) {
        String s = UUID.randomUUID().toString().substring(0, 4);
        int n = random.nextInt(1000);
        strs.add(s);
        list.add(n);
    }
    System.out.println("開始測驗插入 put 函式");
    long start = System.currentTimeMillis();
    for (int i = 0; i < list.size(); i++) {
        map1.put(strs.get(i), list.get(i));
    }
    long end = System.currentTimeMillis();
    System.out.println("HashMap：花費的時間 = " + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < list.size(); i++) {
        map.put(strs.get(i), list.get(i));
    }
    end = System.currentTimeMillis();
    System.out.println("MyHashMap：花費的時間 = " + (end - start));

    System.out.println("開始測驗查找 get 函式");

    start = System.currentTimeMillis();
    for (int i = 0; i < list.size(); i++) {
        map.get(strs.get(i));
    }
    end = System.currentTimeMillis();
    System.out.println("MyHashMap：花費的時間 = " + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < list.size(); i++) {
        map1.get(strs.get(i));
    }
    end = System.currentTimeMillis();
    System.out.println("HashMap：花費的時間 = " + (end - start));
}

輸出結果：

開始測驗插入 put 函式
HashMap：花費的時間 = 232
MyHashMap：花費的時間 = 324
開始測驗查找 get 函式
MyHashMap：花費的時間 = 186
HashMap：花費的時間 = 222

從上面的結果可以看出來我們自己實作的HashMap在插入資料的時候花費的時間比較長，JDK的HashMap使用的是鏈地址法，他們擴容的次數肯定會比我們少，因為我們一個位置只能放一個資料，而JDK的能放多個，

但是我們查找的時候效率會高一點，因為JDK的哈希表還涉及鏈表的操作（可能還涉及紅黑樹），因此我們的效率可能會高一點，

總結

在本篇文章當中我們自己實作了一個線性探測的哈希表，但是我們并沒有實作remove函式，大家可以自己去實作這個函式，也不太困難！！！整篇文章的內容主要包含以下內容：

節點Node的設計，
陣列長度的設計，
roundUp函式設計，
哈希函式的設計，
擴容機制，

本篇內容還是比較多的，希望大家有所識訓，我是LeHung，我們下期再見！！！

更多精彩內容合集可訪問：https://github.com/Chang-LeHung/CSCore

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/498639.html

標籤：其他

上一篇：protobuf 的交叉編譯使用（C++）

下一篇：leetcode 455. Assign Cookies 分發餅干(簡)

HashMap設計原理與實作（下篇）200行帶你寫自己的HashMap！！！

HashMap設計原理與實作（下篇）200行帶你寫自己的HashMap！！！

我們的陣列當中應該存盤什么樣資料？

我們的陣列長度應該怎么設定？

RoundUp函式

哈希函式

擴容機制

Java代碼實作HashMap

先看一下我們需要的欄位

put函式的實作

擴容(resize函式)實作

get函式實作

完整代碼

測驗我們自己實作的HashMap

總結

`put`函式的實作

擴容(`resize`函式)實作

`get`函式實作

測驗我們自己實作的`HashMap`