原文連結

前言

在日常工作中高頻次使用

HashMap

這個資料結構，且在上次的求職過程中也遇到了相關的面試題。今晚通過閱讀源碼了解該資料結構的内部設計。JDK版本1.8.0_231

正文

繼承關系

源碼分析-HashMap前言正文總結

HashMap繼承了

AbstractMap

類，實作了

Map

Cloneable

Serializable

接口。

Map 接口包含一些常用的操作方法
Cloneable 表示可以進行拷貝
Serializable 表示實作了序列化

構造方法

HashMap類存在4個構造方法

HashMap(int initialCapacity, float loadFactor)

/**
     * @param initialCapacity 初始容量
     * @param loadFactor      加載因子 預設值：0.75
     */
    public HashMap(int initialCapacity, float loadFactor) {
        // 初始容量小于0抛異常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                    initialCapacity);
        // 初始容量大于最大值 1 << 30，将最大值設定為容量
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        // 加載因子小于0或為非數字類型抛異常
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                    loadFactor);
        this.loadFactor = loadFactor;
        // 通過tableSizeFor方法擷取臨界值
        this.threshold = tableSizeFor(initialCapacity);
    }

HashMap(int initialCapacity)

// 調用上面的構造函數擷取臨界值
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

在阿裡巴巴《Java開發手冊》中有如下建議：

源碼分析-HashMap前言正文總結

HashMap()

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

HashMap(Map<? extends K, ? extends V> m)

// 将一個map合并
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

添加元素

通過調用

put()

方法添加資料，

// hash()方法用于擷取key對應的hash值
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

// 當key為null時傳回0 此處可以看出hashmap是支援null值的；
	// 當key不為null時擷取key對應的hashCode并指派給變量h， 變量h右移16位； 再進行異或運算并傳回結果
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

調用

putVal()

方法進行元素的添加

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        HashMap.Node<K, V>[] tab;
        HashMap.Node<K, V> p;
        int n, i;
        // 首先判斷table是否包含資料，沒有資料則要進行第一次擴容
        if ((tab = table) == null || (n = tab.length) == 0)
            // 調用resize()方法進行初始化
            n = (tab = resize()).length;
        // 對hash碼進行取模運算擷取key所在的位置，若p == null 表示為新元素
        if ((p = tab[i = (n - 1) & hash]) == null)

            // 将新元素插入到數組的第i個位置
            tab[i] = newNode(hash, key, value, null);

            // 不是新元素
        else {
            HashMap.Node<K, V> e;
            K k;
            // 通過equals()方法判斷元素是否存在，若存在則替換
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
                // 如判斷此時是否為樹結構
            else if (p instanceof TreeNode)
                e = ((HashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
            else {
                // 如果此時為連結清單結構，将該元素追加到最後面
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // 如果此時連結清單長度大于等于8 将連結清單轉換為紅黑樹
                        if (binCount >= TREEIFY_THRESHOLD - 1)
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) {
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // 修改記錄次數
        ++modCount;
        // 如果超過臨界值 再進行擴容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

單連結清單結構用于存儲資料

static class Node<K, V> implements Map.Entry<K, V> {
        // key所代表的hash值
        final int hash;
        // 鍵
        final K key;
        // 值
        V value;
        // 指向下一個元素 （單連結清單）
        HashMap.Node<K, V> next;

        Node(int hash, K key, V value, HashMap.Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

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

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

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

        // 通過equals()防火判斷兩個key是否相等  [在之前的面試中，有面試官提到了這個問題]
        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
                if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

擴容方法

resize()

final HashMap.Node<K, V>[] resize() {
        // table表述存儲資料的數組，如果是第一次添加資料此時為空  反之是之前已添加的資料
        HashMap.Node<K, V>[] oldTab = table;
        //
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // threshold表示臨界值
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1;
        } else if (oldThr > 0)
            newCap = oldThr;
        else {
            // 若在使用hashmap時沒有指定容量且是第一次添加資料，會在這裡繼續數組的初始化；此時容量為16，臨界值為12
            // 預設的容量 1 << 4 == 16
            newCap = DEFAULT_INITIAL_CAPACITY;
            // 臨界值：16 * 0.75
            newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float) newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
                    (int) ft : Integer.MAX_VALUE);
        }
        // 将新的臨界值指派給threshold
        threshold = newThr;
        @SuppressWarnings({"rawtypes", "unchecked"})

        // 建立一個新數組
                HashMap.Node<K, V>[] newTab = (HashMap.Node<K, V>[]) new HashMap.Node[newCap];
        table = newTab;

        // 擴容之後做資料遷移 
        
        // 如果老數組中存在資料，則将裡面的資料指派給新數組，再将老數組中的值逐一設為null
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                HashMap.Node<K, V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    // e.next == null 表述沒有出現hash沖突
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;

                        // 出現了hash沖突

                        // 如果是紅黑樹
                    else if (e instanceof TreeNode)
                        ((HashMap.TreeNode<K, V>) e).split(this, newTab, j, oldCap);
                    else {
                        // 将原有資料做遷移
                        HashMap.Node<K, V> loHead = null, loTail = null;
                        HashMap.Node<K, V> hiHead = null, hiTail = null;
                        HashMap.Node<K, V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            } else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

查找元素

使用

get()

方法擷取HashMap中資料

// 如果getNode()方法取回的值不存在傳回null，傳回擷取value值
    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

getNode()

擷取資料前先使用

hash()

方法擷取key對應的hash值

final HashMap.Node<K, V> getNode(int hash, Object key) {
        HashMap.Node<K, V>[] tab;
        HashMap.Node<K, V> first, e;
        int n;
        K k;
        // 将原數組中的資料指派給tab 并判斷tab數組的長度是否大于0 并且看能否在數組中擷取key所在的位置且不為null   校驗未通過傳回Null
        if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {

            // 判斷是否是hash沖突的元素
            if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            // 如果出現hash沖突會将元素添加到連結清單中，如果next！=null表示為連結清單結構  需要從連結清單中擷取
            if ((e = first.next) != null) {
                // 當連結清單的長度達到8時 将連結清單轉換為；此時判斷是否是紅黑樹，并從其中擷取資料
                if (first instanceof TreeNode)
                    return ((HashMap.TreeNode<K, V>) first).getTreeNode(hash, key);
                // 周遊連結清單 并擷取資料
                do {
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

總結

通過上面源碼分析，可以看出HashMap是由數組，單連結清單和紅黑樹所組成。

添加元素：首先元素依次儲存在資料中，如果此時發生hash沖突，則建立一個單連結清單在該hash位上，當單連結清單長度大于等于8時，将單連結清單轉換為紅黑樹
查找元素：判斷key對應的hash值是否存在于數組中，如果存在則從其中取出，如果元素next屬性不為null，則依次判斷樹和連結清單中是否存在再取出，如果都不存在，傳回null

源碼分析-HashMap前言正文總結

源碼分析-HashMap前言正文總結

前言

正文

繼承關系

構造方法

添加元素

查找元素

總結

繼續閱讀

nginx location中斜線的位置的重要性

資料結構與算法（27）——排序（二）

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

Linux裝置模型（中）之上層容器

scala (3) Function 和 Method