深入理解HashMap各個(gè)方法的源碼
HashMap各個(gè)方法的源碼
put方法
首先分析第一個(gè)比較重要的方法 put 方法,源碼如下
public V put(K key, V value) { if (key == null) return putForNullKey(value); //這里判斷key是否為空,若為空則調(diào)用putForNullKey處理null值 int hash = hash(key); //根據(jù)key的hashCode計(jì)算hash值 int i = indexFor(hash, table.length);//搜索該key的hash值在table中的索引,其中table是當(dāng)HashMap用于存放entry的一個(gè)數(shù)組 //這里循環(huán)遍歷table中對(duì)應(yīng)該索引的entry,若發(fā)現(xiàn)存在key與put進(jìn)來(lái)的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++; //將key value 添加到 索引i處 addEntry(hash, key, value, i); return null; }
分析上面的源碼,我們可以得到下面的結(jié)論:
當(dāng)我們?cè)噲D將一個(gè)key-value 調(diào)用put方法放入HashMap的時(shí)候,首先會(huì)調(diào)用key的hashCode方法算出該Entry存放的位置,若兩個(gè)key的hashCode相同則在table中的存儲(chǔ)位置相同,則先調(diào)用equals方法判斷兩個(gè)key是否相同,相同則覆蓋,不相同則產(chǎn)生一個(gè)Entry鏈表(因?yàn)閠able數(shù)組中一個(gè)索引位置只能放入一個(gè)Entry,所以當(dāng)有多個(gè)key的hashCode相同時(shí),這些key就會(huì)以鏈表的形式存在,并且最后put進(jìn)來(lái)的key在鏈表的最前面)
構(gòu)造方法
然后則是HashMap的構(gòu)造方法,這里以 HashMap(int initialCapacity, float loadFactor)這個(gè)構(gòu)造器為例,源碼如下
public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); init(); }
從上面的源碼可以看出 ,初始容量不能為負(fù)數(shù),若初始容量大于最大容量,則讓它等于最大容量,負(fù)載因子必須大于0,并且傳入的initialCapacity不是HashMap的容量大小,
實(shí)際容量大小的計(jì)算規(guī)則是大于傳入的initialCapacity的最小的2的n次方,比如傳入的initialCapacity是5 那么實(shí)際容量則是8 因?yàn)?的3次方大于5。
get方法
下面再分析一下HashMap的存儲(chǔ)性能,下面的 get方法的源碼
public V get(Object key) { if (key == null) return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); } final Entry<K,V> getEntry(Object key) { int hash = (key == null) ? 0 : hash(key); for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; }
再次強(qiáng)調(diào)一下table的概念,table就是當(dāng)我們初始化一個(gè)HashMap時(shí),會(huì)自動(dòng)創(chuàng)建一個(gè)長(zhǎng)度為capacity的Entry數(shù)組,我們把這個(gè)數(shù)組存放元素的位置叫“桶”,并且每個(gè)桶只存儲(chǔ)一個(gè)Entry元素(也就是我們的鍵值對(duì)),并且當(dāng)我們put一個(gè)鍵值對(duì)時(shí),先計(jì)算key的hashCode來(lái)判斷這個(gè)鍵值對(duì)會(huì)放入哪一個(gè)桶,所以若多個(gè)key的hashCode相同時(shí),他們都要被放入一個(gè)桶里面,但是一個(gè)桶里面只能放入一個(gè)Entry(鍵值對(duì)),要解決這個(gè)問(wèn)題先看下面的代碼
Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; }
這是Entry的構(gòu)造方法,我們可以看出Entry對(duì)象包含一個(gè)Entry的引用,用來(lái)指向下一個(gè)Entry,這樣就解決了hashCode相同,存放沖突的問(wèn)題,所以當(dāng)有多個(gè)key的hashCode相同時(shí),就會(huì)形成一個(gè)Entry鏈,我們從get方法可以看出當(dāng)系統(tǒng)通過(guò)key的hashCode找到了對(duì)應(yīng)的桶的時(shí)候,會(huì)遍歷這個(gè)Entry鏈,來(lái)找到我們要取的value的key
這個(gè)時(shí)候,若剛好這個(gè)Entry在鏈表的末端(也就是我們最開(kāi)始put進(jìn)去的Entry)那么當(dāng)這個(gè)鏈表太長(zhǎng)了,勢(shì)必會(huì)影響我們的查詢(xún)性能,這個(gè)時(shí)候就引出了loadFactor(負(fù)載因子的說(shuō)法),HashMap的默認(rèn)附在因子是0.75
我對(duì)負(fù)載因子的理解就是,表示HashMap在什么時(shí)候擴(kuò)容,也就是說(shuō)若我們初始的HashMap容量是16 負(fù)載因子是0.75
那么當(dāng)有12個(gè)“桶”有了Entry時(shí),HashMap就會(huì)擴(kuò)容,并且擴(kuò)大的容量是原來(lái)容量的2倍,為什么是12呢?因?yàn)?.75x16=12。
并且負(fù)載因子是可以更改的,修改它的前提是如果內(nèi)存比較緊張就可以適當(dāng)?shù)脑黾迂?fù)載因子
若空間,內(nèi)存比較充足,更關(guān)注查詢(xún)效率則減少負(fù)載因子。為什么會(huì)這樣呢?因?yàn)槿糌?fù)載因子減少了,比如說(shuō)減少到了0.5,默認(rèn)HashMap容量大小還是16
那么當(dāng)我有8個(gè)"桶"中存放了Entry數(shù)組時(shí)我就會(huì)擴(kuò)容了,該桶里的Entry鏈相比于之前就不會(huì)那么長(zhǎng),從而提升了查詢(xún)性能。
到此這篇關(guān)于深入理解HashMap各個(gè)方法的源碼的文章就介紹到這了,更多相關(guān)HashMap方法的源碼內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
mybatis spring配置SqlSessionTemplate的使用方式
這篇文章主要介紹了mybatis spring配置SqlSessionTemplate的使用方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-08-08Dubbo在Spring和Spring Boot中的使用詳解
這篇文章主要介紹了Dubbo在Spring和Spring Boot中的使用詳解,需要的朋友可以參考下2017-10-10SpringBoot整合RabbitMQ消息隊(duì)列的完整步驟
這篇文章主要給大家介紹了關(guān)于SpringBoot整合RabbitMQ消息隊(duì)列的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-05-05AsyncConfigurerSupport自定義異步線程池處理異常
這篇文章主要為大家介紹了AsyncConfigurerSupport自定義異步線程池處理異常詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-06-06Springboot整合Freemarker的實(shí)現(xiàn)詳細(xì)過(guò)程
這篇文章主要介紹了Springboot整合Freemarker的實(shí)現(xiàn)詳細(xì)過(guò)程,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12Java工廠模式之簡(jiǎn)單工廠,工廠方法,抽象工廠模式詳解
這篇文章主要為大家詳細(xì)介紹了Java工廠模式之簡(jiǎn)單工廠、工廠方法、抽象工廠模式,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來(lái)幫助2022-02-02Java數(shù)據(jù)結(jié)構(gòu)常見(jiàn)幾大排序梳理
Java常見(jiàn)的排序算法有:直接插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序等。本文詳解介紹它們的實(shí)現(xiàn)以及圖解,需要的可以參考一下2022-03-03Struts2學(xué)習(xí)教程之入門(mén)小白的開(kāi)始基礎(chǔ)
struts2其實(shí)就是為我們封裝了servlet,簡(jiǎn)化了jsp跳轉(zhuǎn)的復(fù)雜操作,并且提供了易于編寫(xiě)的標(biāo)簽,可以快速開(kāi)發(fā)view層的代碼。下面這篇文章主要給各位想要學(xué)習(xí)Struts2的小白們?cè)敿?xì)介紹了關(guān)于Struts2入門(mén)的一些開(kāi)始基礎(chǔ),需要的朋友可以參考下2018-04-04詳解java代碼中init method和destroy method的三種使用方式
這篇文章主要介紹了詳解java代碼中init method和destroy method的三種使用方式,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03