Java模擬實(shí)現(xiàn)HashMap算法流程詳解

更新時(shí)間：2023年02月08日 16:41:10 作者：程序猿教你打籃球

在java開發(fā)中，HashMap是最常用、最常見的集合容器類之一，文中通過示例代碼介紹HashMap為啥要二次Hash，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)吧

1、前言

上期講解了 HashMap 和 HashSet 的一些相關(guān)源碼，本期我們就來簡單的模擬實(shí)現(xiàn)一下 HashMap，當(dāng)然肯定沒有源碼那么的復(fù)雜，但是簡單的結(jié)構(gòu)還是要去實(shí)現(xiàn)一下的，當(dāng)然，這也是數(shù)據(jù)結(jié)構(gòu)課程中最后一起了，后續(xù)博主也會(huì)帶來 MySQL基礎(chǔ)，和 Java EE 一些相關(guān)的內(nèi)容。如果數(shù)據(jù)結(jié)構(gòu)在學(xué)習(xí)的過程中，感到特別困難的話，記得多畫圖，多調(diào)試。

2、成員變量的設(shè)定

public class MyHashMap<K, V> {
    private Entry<K, V>[] table; //哈希表
    private int size; // 有效數(shù)據(jù)個(gè)數(shù)
    private static final float DEFAULT_LOAD_FACTOR = 0.75f; //負(fù)載因子設(shè)定
    private static final int DEFAULT_CAPACITY = 6; //默認(rèn)容量
    // 節(jié)點(diǎn)
    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;
        }
    }
}

這里我們采用數(shù)組來存儲(chǔ)我們的數(shù)據(jù)，而每個(gè)數(shù)組的元素是 Entry 這樣的節(jié)點(diǎn)，Entry 中包含一個(gè) next 引用，用來存放下一個(gè)節(jié)點(diǎn)，從而實(shí)現(xiàn)數(shù)組中每個(gè)元素可以是一個(gè)鏈表的結(jié)構(gòu)，那么大概是這樣的一個(gè)結(jié)構(gòu)：

通常我們畫數(shù)組都是橫過來畫的，只不過這次我們把數(shù)組豎過來畫的，這樣能更清晰看到鏈表的結(jié)構(gòu)，從美觀上也更漂亮。

簡而言之，我們今天實(shí)現(xiàn)的結(jié)構(gòu)就是數(shù)組元素中放鏈表的結(jié)構(gòu)，當(dāng)然涉及到了泛型的知識，如果對泛型還不夠了解，可以看下博主 JavaSE 系列泛型的博客。

3、構(gòu)造方法

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;
}

因?yàn)槭悄M實(shí)現(xiàn)，我們就盡可能的簡化，體現(xiàn)出 HashMap 底層的結(jié)構(gòu)即可，這我們就默認(rèn)令 HashMap 的大小為6，也有一個(gè)帶參數(shù)的構(gòu)造方法，可以指定哈希表的大小。

有了上述的準(zhǔn)備工作，我們這里就可以來實(shí)現(xiàn)下主要的幾個(gè)方法了，主要實(shí)現(xiàn) put，get，resize(擴(kuò)容)，hash 這些方法。

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

這里我們簡單設(shè)計(jì)一下即可，就獲取對象的 hashCode % 哈希表的長度即可：

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

判斷是否達(dá)到閾值，也就是是否超過設(shè)定的負(fù)載因子了，就需要考慮擴(kuò)容的情況，上期介紹到，求負(fù)載因子：哈希表的長度 / 元素個(gè)數(shù)，有了這樣的公式，那自然就好判斷是否到達(dá)了閾值了：

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

5、put方法

在 JDK1.7 及之前鏈表采用的是頭插的方式，JDK1.8 及以后采用的是尾插方式，那么我們就來模擬實(shí)現(xiàn)一下尾插的一個(gè)邏輯。

這里思考插入時(shí)的兩種情況：

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

直接在當(dāng)前哈希表元素 new 一個(gè)節(jié)點(diǎn)插入即可。

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

2. 通過 hash 值，得到哈希表的位置上已經(jīng)存在元素了，也就是 hash 位置不為 null 的情況下。

遍歷鏈表沒有與要插入的 key 相同的元素的情況下，直接在最后插入。
遍歷鏈表發(fā)現(xiàn)了存在相同 key 的元素的情況下，更新 key 對應(yīng)的 value 值，即可。

分析上述的情況，也有圖解的情況，接下來就可以來實(shí)現(xiàn)我們的代碼了：

public V put(K key, V value) {
    return putVal(hash(key), key, value);
}
private V putVal(int hash, K key, V value) {
    // 通過 hash 值, 找到對應(yīng)位置
    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 后面插入節(jié)點(diǎn)
        prev.next = new Entry<>(key, value);
    }
    size++;
    // 判斷是否超過了閾值考慮擴(kuò)容問題。
    if (loadFactor()) {
        resize();
    }
    return value;
}

這里我是采用 prev 記錄 cur 的前一個(gè)節(jié)點(diǎn)，當(dāng) cur 為 null 就結(jié)束循環(huán)了，進(jìn)行尾插，當(dāng)然你也可也當(dāng) cur.next 為 null，結(jié)束循環(huán)，最后使得 cur.next = new Entry<>(key，value) 也是可以的。

這里每插入一個(gè)元素，都需要判斷是否超過了設(shè)定的 0.75 的負(fù)載因子了，如果超過的話，就需要重新調(diào)整哈希表的大小。

6、resize 方法

給哈希表擴(kuò)容的目的就是減少?zèng)_突的概率，但是這里得考慮到一個(gè)問題，可以直接擴(kuò)容嗎？我們 hash 函數(shù)設(shè)置是 key.hashCode % table.length，那么如果哈希表的長度改變了，之前表中元素 key 對應(yīng)的 hash 值也會(huì)發(fā)生改變，所以我們通過新的 hash 值，不一定能找到之前元素的位置了。所以擴(kuò)容之后，原來表中所有元素的位置都要通過新的 hash 值放入新的位置上。

private void resize() {
    // 重新擴(kuò)容勢必會(huì)考慮到一個(gè)問題, 重新 hash 的問題
    // 即現(xiàn)在表中的元素, 要通過新的 hash 值, 放入擴(kuò)容后新的位置上
    // 二倍式擴(kuò)容
    Entry<K, V>[] oldTable = table;
    table = (Entry<K, V>[])new Entry[table.length * 2];
    // 將 oldTable 的數(shù)據(jù)通過新的 hash, 拷貝進(jìn) table 中
    copyData(oldTable);
}
private void copyData(Entry<K, V>[] oldTable) {
    // 遍歷這個(gè) oldTable 將數(shù)據(jù)拷貝進(jìn)他 table 中
    for (int i = 0; i < oldTable.length; i++) {
        Entry<K, V> node = oldTable[i];
        while (node != null) {
            // 不能直接將 node 插入進(jìn)去, 因?yàn)?node.next 后面可能還有其他元素
            // 所以我們要拷貝一份新的 node 進(jìn)行插入
            Entry<K, V> insertNode = new Entry<>(node.key, node.value);
 
            int index = hash(node.key); // node要被hash到的新位置
            Entry<K, V> cur = table[index];
            // table當(dāng)前位置沒有元素, 直接插入該節(jié)點(diǎn)作為鏈表的頭節(jié)點(diǎn)
            if (cur == null) {
                table[index] = insertNode;
            } else {
                Entry<K, V> prev = null;
                // 如果當(dāng)前數(shù)組下標(biāo)已經(jīng)有元素了, 就遍歷數(shù)組中鏈表往后找
                while (cur != null) {
                    prev = cur;
                    cur = cur.next;
                }
                prev.next = insertNode;
            }
            // 插入 oldTable[i] 當(dāng)前鏈表中節(jié)點(diǎn)后, node 往后走, 判斷還有沒有節(jié)點(diǎn)需要重新 hash 插入
            node = node.next;
        }
    }
}

表中的每個(gè)元素是一個(gè)鏈表，但是需要對個(gè)元素進(jìn)行重新 hash，不能直接移動(dòng)整條鏈表，只能拿出每個(gè)元素，分別重新 hash 放入新的位置上，所以這里我采取將老節(jié)點(diǎn)復(fù)制出來進(jìn)行重新hash。

這里我也寫了一個(gè)測試樣例，來證明該代碼上下文代碼結(jié)合跑起來擴(kuò)容后是會(huì)重新 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("擴(kuò)容前: ");
    System.out.println(map);
    map.put(13, 5);
    System.out.println("擴(kuò)容后: ");
    System.out.println(map);
}

由于默認(rèn)數(shù)組大小是 6，當(dāng)插入完第五個(gè)元素后，則會(huì)達(dá)到閾值，就需要擴(kuò)容了，這里我重寫了 toString 方法，能看到打印結(jié)果就是模擬出數(shù)組加鏈表結(jié)構(gòu)的打印，很明顯能看到，擴(kuò)容前，5 下標(biāo)位置有 key=17 和 key=11 兩個(gè)元素，而擴(kuò)容后 5 下標(biāo)只剩下 key = 17 一個(gè)元素了，而 key=11 則被重新 hash 到了 11 位置下。

7、get 方法

這個(gè)方法就比較簡單了，通過傳過來的 key 返回對應(yīng) key 的 value值，利用傳過來 key 通過 hash 函數(shù)獲取 index 位置，這個(gè)位置可能沒有元素，可能是一條鏈表，但鏈表中也可能不存在key，也可能存在 key，如果 index 位置沒有元素，或者遍歷 index 位置都沒找到 key，那么就返回 null，找到了即返回 key 對應(yīng)的 value 值即可。代碼如下：

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

這次模擬實(shí)現(xiàn) HashMap 相較于源碼我們還是簡單了很多，主要是練習(xí)數(shù)組加鏈表這樣的一個(gè)結(jié)構(gòu)，和練習(xí)重新hash 的一個(gè)問題。那么 Java 實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)初階的內(nèi)容到此就告一段落了

到此這篇關(guān)于Java模擬實(shí)現(xiàn)HashMap算法流程詳解的文章就介紹到這了,更多相關(guān)Java HashMap內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: