Java模擬實現HashMap演演算法流程詳解

2023-02-08 22:00:19

1、前言

上期講解了 HashMap 和 HashSet 的一些相關原始碼，本期我們就來簡單的模擬實現一下 HashMap，當然肯定沒有原始碼那麼的複雜，但是簡單的結構還是要去實現一下的，當然，這也是資料結構課程中最後一起了，後續博主也會帶來 MySQL基礎，和 Java EE 一些相關的內容。如果資料結構在學習的過程中，感到特別困難的話，記得多畫圖，多偵錯。

2、成員變數的設定

public class MyHashMap<K, V> {
    private Entry<K, V>[] table; //雜湊表
    private int size; // 有效資料個數
    private static final float DEFAULT_LOAD_FACTOR = 0.75f; //負載因子設定
    private static final int DEFAULT_CAPACITY = 6; //預設容量
    // 節點
    public static class Entry<K, V> {
        private K key;
        private V value;
        private Entry<K, V> next;
        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}

這裡我們採用陣列來儲存我們的資料，而每個陣列的元素是 Entry 這樣的節點，Entry 中包含一個 next 參照，用來存放下一個節點，從而實現陣列中每個元素可以是一個連結串列的結構，那麼大概是這樣的一個結構：

通常我們畫陣列都是橫過來畫的，只不過這次我們把陣列豎過來畫的，這樣能更清晰看到連結串列的結構，從美觀上也更漂亮。

簡而言之，我們今天實現的結構就是陣列元素中放連結串列的結構，當然涉及到了泛型的知識，如果對泛型還不夠了解，可以看下博主 JavaSE 系列泛型的部落格。

3、構造方法

public MyHashMap() {
    this.table = (Entry<K, V>[])new Entry[DEFAULT_CAPACITY];
    this.size = 0;
}
public MyHashMap(int capacity) {
    this.table = (Entry<K, V>[])new Entry[capacity];
    this.size = capacity;
}

因為是模擬實現，我們就儘可能的簡化，體現出 HashMap 底層的結構即可，這我們就預設令 HashMap 的大小為6，也有一個帶引數的構造方法，可以指定雜湊表的大小。

有了上述的準備工作，我們這裡就可以來實現下主要的幾個方法了，主要實現 put，get，resize(擴容)，hash 這些方法。

4、hash方法以及閾值判斷方法

這裡我們簡單設計一下即可，就獲取物件的 hashCode % 雜湊表的長度即可：

private int hash(K key) {
    return (key == null) ? 0 : key.hashCode() % table.length;
}

判斷是否達到閾值，也就是是否超過設定的負載因子了，就需要考慮擴容的情況，上期介紹到，求負載因子：雜湊表的長度 / 元素個數，有了這樣的公式，那自然就好判斷是否到達了閾值了：

private boolean loadFactor() {
    return size * 1.0 / table.length >= DEFAULT_LOAD_FACTOR;
}

5、put方法

在 JDK1.7 及之前連結串列採用的是頭插的方式，JDK1.8 及以後採用的是尾插方式，那麼我們就來模擬實現一下尾插的一個邏輯。

這裡思考插入時的兩種情況：

1. 通過 hash 值，得到雜湊表的位置上不存在元素，也就是 hash 位置為 null 的情況下。

直接在當前雜湊表元素 new 一個節點插入即可。

我們就按照上述的兩種情況來進行插入元素。

2. 通過 hash 值，得到雜湊表的位置上已經存在元素了，也就是 hash 位置不為 null 的情況下。

遍歷連結串列沒有與要插入的 key 相同的元素的情況下，直接在最後插入。
遍歷連結串列發現了存在相同 key 的元素的情況下，更新 key 對應的 value 值，即可。

分析上述的情況，也有圖解的情況，接下來就可以來實現我們的程式碼了：

public V put(K key, V value) {
    return putVal(hash(key), key, value);
}
private V putVal(int hash, K key, V value) {
    // 通過 hash 值, 找到對應位置
    Entry<K, V> cur = table[hash];
    Entry<K, V> prev = null;
    if (cur == null) {
        table[hash] = new Entry<>(key, value);
    }  else {
        while (cur != null) {
            // 碰到相同值的情況
            if (cur.key.equals(key)) {
                cur.value = value; //更新下value值
                return value;
            }
            prev = cur;
            cur = cur.next;
        }
        // prev 後面插入節點
        prev.next = new Entry<>(key, value);
    }
    size++;
    // 判斷是否超過了閾值考慮擴容問題。
    if (loadFactor()) {
        resize();
    }
    return value;
}

這裡我是採用 prev 記錄 cur 的前一個節點，當 cur 為 null 就結束迴圈了，進行尾插，當然你也可也當 cur.next 為 null，結束迴圈，最後使得 cur.next = new Entry<>(key，value) 也是可以的。

這裡每插入一個元素，都需要判斷是否超過了設定的 0.75 的負載因子了，如果超過的話，就需要重新調整雜湊表的大小。

6、resize 方法

給雜湊表擴容的目的就是減少衝突的概率，但是這裡得考慮到一個問題，可以直接擴容嗎？我們 hash 函數設定是 key.hashCode % table.length，那麼如果雜湊表的長度改變了，之前表中元素 key 對應的 hash 值也會發生改變，所以我們通過新的 hash 值，不一定能找到之前元素的位置了。所以擴容之後，原來表中所有元素的位置都要通過新的 hash 值放入新的位置上。

private void resize() {
    // 重新擴容勢必會考慮到一個問題, 重新 hash 的問題
    // 即現在表中的元素, 要通過新的 hash 值, 放入擴容後新的位置上
    // 二倍式擴容
    Entry<K, V>[] oldTable = table;
    table = (Entry<K, V>[])new Entry[table.length * 2];
    // 將 oldTable 的資料通過新的 hash, 拷貝進 table 中
    copyData(oldTable);
}
private void copyData(Entry<K, V>[] oldTable) {
    // 遍歷這個 oldTable 將資料拷貝進他 table 中
    for (int i = 0; i < oldTable.length; i++) {
        Entry<K, V> node = oldTable[i];
        while (node != null) {
            // 不能直接將 node 插入進去, 因為 node.next 後面可能還有其他元素
            // 所以我們要拷貝一份新的 node 進行插入
            Entry<K, V> insertNode = new Entry<>(node.key, node.value);
 
            int index = hash(node.key); // node要被hash到的新位置
            Entry<K, V> cur = table[index];
            // table當前位置沒有元素, 直接插入該節點作為連結串列的頭節點
            if (cur == null) {
                table[index] = insertNode;
            } else {
                Entry<K, V> prev = null;
                // 如果當前陣列下標已經有元素了, 就遍歷陣列中連結串列往後找
                while (cur != null) {
                    prev = cur;
                    cur = cur.next;
                }
                prev.next = insertNode;
            }
            // 插入 oldTable[i] 當前連結串列中節點後, node 往後走, 判斷還有沒有節點需要重新 hash 插入
            node = node.next;
        }
    }
}

表中的每個元素是一個連結串列，但是需要對個元素進行重新 hash，不能直接移動整條連結串列，只能拿出每個元素，分別重新 hash 放入新的位置上，所以這裡我採取將老節點複製出來進行重新hash。

這裡我也寫了一個測試樣例，來證明該程式碼上下文程式碼結合跑起來擴容後是會重新 hash 放入新的位置的：

public static void main(String[] args) {
    MyHashMap<Integer, Integer> map = new MyHashMap<>();
    map.put(1, 1);
    map.put(17, 2);
    map.put(21, 3);
    map.put(11, 4);
    System.out.println("擴容前: ");
    System.out.println(map);
    map.put(13, 5);
    System.out.println("擴容後: ");
    System.out.println(map);
}

由於預設陣列大小是 6，當插入完第五個元素後，則會達到閾值，就需要擴容了，這裡我重寫了 toString 方法，能看到列印結果就是模擬出陣列加連結串列結構的列印，很明顯能看到，擴容前，5 下標位置有 key=17 和 key=11 兩個元素，而擴容後 5 下標只剩下 key = 17 一個元素了，而 key=11 則被重新 hash 到了 11 位置下。

7、get 方法

這個方法就比較簡單了，通過傳過來的 key 返回對應 key 的 value值，利用傳過來 key 通過 hash 函數獲取 index 位置，這個位置可能沒有元素，可能是一條連結串列，但連結串列中也可能不存在key，也可能存在 key，如果 index 位置沒有元素，或者遍歷 index 位置都沒找到 key，那麼就返回 null，找到了即返回 key 對應的 value 值即可。程式碼如下：

public V get(K key) {
    // 通過 hash 獲取當前 key 所在的位置
    int index = hash(key);
    // 通過 index 位置找到 key 對應的 value
    Entry<K, V> cur = table[index];
    while (cur != null) {
        if (cur.key.equals(key)) {
            return cur.value;
        }
        cur = cur.next;
    }
    return null;
}

這次模擬實現 HashMap 相較於原始碼我們還是簡單了很多，主要是練習陣列加連結串列這樣的一個結構，和練習重新hash 的一個問題。那麼 Java 實現資料結構初階的內容到此就告一段落了

到此這篇關於Java模擬實現HashMap演演算法流程詳解的文章就介紹到這了,更多相關Java HashMap內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！