當前位置:首頁 > IT技術(shù) > 其他 > 正文

HashMap源碼分析
2022-04-29 13:47:48

一、HashMap底層實現(xiàn)

HashMap底層結(jié)構(gòu):數(shù)組+鏈表+紅黑樹

Java中的HashMap是以鍵值對(key-value)的形式存儲元素的。HashMap需要一個hash函數(shù),它使用hashCode()和equals()方法來向集合/從集合添加和檢索元素。當調(diào)用put()方法的時候,HashMap會計算key的hash值,然后把鍵值對存儲在集合中合適的索引上。如果key已經(jīng)存在了,value會被更新成新值

HashMap的一些重要的特性是它的容量(capacity),負載因子(load factor)和擴容極限(threshold resizing)

二、初始化HashMap

源碼: 三種構(gòu)造函數(shù)

 
//initialCapacity:初始化大小,loadFactor:加載因子
public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        } else {
            if (initialCapacity > 1073741824) {
                initialCapacity = 1073741824;
            }

            if (loadFactor > 0.0F && !Float.isNaN(loadFactor)) {
                this.loadFactor = loadFactor;
                this.threshold = tableSizeFor(initialCapacity);
            } else {
                throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
            }
        }
    }

    public HashMap(int initialCapacity) {
        this(initialCapacity, 0.75F);
    }

    public HashMap() {
        this.loadFactor = 0.75F;
    }

   public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = 0.75F;
        this.putMapEntries(m, false);
    }

?

默認值大小

private static final long serialVersionUID = 362498820763181265L;
    static final int DEFAULT_INITIAL_CAPACITY = 16;//HashMap的默認容量,16;
    static final int MAXIMUM_CAPACITY = 1073741824;//最大容量
    static final float DEFAULT_LOAD_FACTOR = 0.75F;//默認加載因子 0.75
    static final int TREEIFY_THRESHOLD = 8;//Bucket中鏈表長度大于該默認值,轉(zhuǎn)化為紅黑樹 8
    static final int UNTREEIFY_THRESHOLD = 6;
    static final int MIN_TREEIFY_CAPACITY = 64;

三、put操作

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // 鍵為 null 單獨處理
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    // 確定桶下標
    int i = indexFor(hash, table.length);
    // 先找出是否已經(jīng)存在鍵為 key 的鍵值對,如果存在的話就更新這個鍵值對的值為 value
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    // 插入新鍵值對
    addEntry(hash, key, value, i);
    return null;
}

?

四、擴容原理

//判斷增加元素后的容量是否大于老容量
if
(++this.size > this.threshold) { this.resize(); } final HashMap.Node<K, V>[] resize() { HashMap.Node<K, V>[] oldTab = this.table; int oldCap = oldTab == null ? 0 : oldTab.length; int oldThr = this.threshold; int newThr = 0;//臨界值=capacity*loadfactor int newCap; if (oldCap > 0) {
        //如果容量大于最大容量,將threshold改為2倍的容量-1
if (oldCap >= 1073741824) { this.threshold = 2147483647; return oldTab; }         //如果新容量的2倍還是小于最大容量,或者容量小于16容量就翻二倍 if ((newCap = oldCap << 1) < 1073741824 && oldCap >= 16) { newThr = oldThr << 1; } } else if (oldThr > 0) { newCap = oldThr; } else { newCap = 16; newThr = 12;
    }
return newTab; }

?

總結(jié):

HashMap的擴容機制:當`hashmap`被初始化創(chuàng)建的時候容量為16,由于初始化的加載因子的值為0.75,所以在集合大小為16*0.75=12的時候開始進行擴容,擴容的大小為當前集合的大小的2倍,也就是32,下一次集合大小為32*0.75=24時開始擴容.....
在Java8中,如果一條鏈表的元素個數(shù)超過樹化閾值(默認是8),并且集合的大小>=閾值(默認64),就會進行樹化(紅黑樹)

?

本文摘自 :https://www.cnblogs.com/

開通會員,享受整站包年服務立即開通 >