Java容器HashMap與HashTable詳解
1、HashMap
HashMap繼承抽象類AbstractMap,實(shí)現(xiàn)接口Map、Cloneable, Serializable接口。HashMap是一種以鍵值對(duì)存儲(chǔ)數(shù)據(jù)的容器,
由數(shù)組+鏈表組成,其中key和value
都可以為空,key的值唯一。HashMap
是非線程安全的, 對(duì)于鍵值對(duì)<Key,Value>,
HashMap內(nèi)部會(huì)將其封裝成一個(gè)對(duì)應(yīng)的Entry<Key,Value>
對(duì)象。HashMap的存儲(chǔ)空間大小是可以動(dòng)態(tài)改變的:
存儲(chǔ)過(guò)程
每個(gè)對(duì)象都有一個(gè)對(duì)應(yīng)的HashCode
值,根據(jù)HashCode值,調(diào)用hash函數(shù),計(jì)算出一個(gè)hash值,根據(jù)該hash值調(diào)用indexFor函數(shù),計(jì)算出在table中的存儲(chǔ)位置,如果該位置已經(jīng)有值,則存儲(chǔ)在該位置對(duì)應(yīng)的桶中。
public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) return putForNullKey(value); int hash = hash(key); int i = indexFor(hash, table.length); 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; } public final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } public final int hashCode() { return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue()) } static int indexFor(int h, int length) { // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; return h & (length-1); }
獲取值
首先根據(jù)key的HashCode碼計(jì)算出hash值,然后調(diào)用indexFor函數(shù)計(jì)算該entry對(duì)象在table中的存儲(chǔ)位置,遍歷該位置對(duì)應(yīng)桶中存儲(chǔ)的entry對(duì)象,如果存在對(duì)象的hash值和key與要查找的相同,則返回該對(duì)象。
public final Entry<K,V> getEntry(Object key) { if (size == 0) { return null; } 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; }
兩map相等的判斷
public final boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; Object k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2 || (k1 != null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } return false; }
自反性:對(duì)于任何非空引用值 x,x.equals(x) 都應(yīng)返回 true。
對(duì)稱性:對(duì)于任何非空引用值 x 和 y,當(dāng)且僅當(dāng) y.equals(x) 返回 true 時(shí),x.equals(y) 才應(yīng)返回 true。
傳遞性:對(duì)于任何非空引用值 x、y 和 z,如果 x.equals(y) 返回 true,并且 y.equals(z) 返回
true,那么 x.equals(z) 應(yīng)返回 true。
一致性:對(duì)于任何非空引用值 x 和 y,多次調(diào)用 x.equals(y) 始終返回 true 或始終返回 false,前提是對(duì)象上
equals 比較中所用的信息沒(méi)有被修改。
對(duì)于任何非空引用值 x,x.equals(null) 都應(yīng)返回 false。
存儲(chǔ)空間動(dòng)態(tài)分配
HashMap
的桶數(shù)目,即Entry[] table
數(shù)組的長(zhǎng)度,由于數(shù)組是內(nèi)存中連續(xù)的存儲(chǔ)單元,它的空間代價(jià)是很大的,但是它的隨機(jī)存取的速度是Java
集合中最快的。我們?cè)龃笸暗臄?shù)量,而減少Entry<Key,Value>
鏈表的長(zhǎng)度,來(lái)提高從HashMap中讀取數(shù)據(jù)的速度。這是典型的拿空間換時(shí)間的策略。
但是我們不能剛開(kāi)始就給HashMap
分配過(guò)多的桶(即Entry[] table
數(shù)組起始不能太大),這是因?yàn)閿?shù)組是連續(xù)的內(nèi)存空間,它的創(chuàng)建代價(jià)很大,況且我們不能確定給HashMap分配這么大的空間,它實(shí)際到底能夠用多少,為了解決這一個(gè)問(wèn)題,HashMap采用了根據(jù)實(shí)際的情況,動(dòng)態(tài)地分配桶的數(shù)量。
要?jiǎng)討B(tài)分配桶的數(shù)量,這就要求要有一個(gè)權(quán)衡的策略了,HashMap的權(quán)衡策略是這樣的:
如果 HashMap的大小 > HashMap的容量(即Entry[] table的大小)*加載因子(經(jīng)驗(yàn)值0.75) 則 HashMap中的Entry[] table 的容量擴(kuò)充為當(dāng)前的一倍;然后重新將以前桶中的`Entry<Key,Value>`鏈表重新分配到各個(gè)桶中
上述的 HashMap的容量(即Entry[] table的大小) * 加載因子(經(jīng)驗(yàn)值0.75)就是所謂的閥值(threshold)。
2、HashTable
HashTable繼承Dictionary類,實(shí)現(xiàn)Map, Cloneable,Serializable接口,不允許key為空,采用拉鏈法實(shí)現(xiàn)與HashMap類似。
HashTable是線程安全的(但是在Collections類中存在一個(gè)靜態(tài)方法:synchronizedMap(),該方法創(chuàng)建了一個(gè)線程安全的Map對(duì)象,通過(guò)該方法我們可以同步訪問(wèn)潛在的HashMap,對(duì)整個(gè)map對(duì)象加鎖。CurrentHashMap是線程安全的,并且只對(duì)桶加鎖,不會(huì)影響map對(duì)象上其它桶的操作)。
希望本文對(duì)各位朋友有所幫助
相關(guān)文章
Java?Maven構(gòu)建工具中mvnd和Gradle誰(shuí)更快
這篇文章主要介紹了Java?Maven構(gòu)建工具中mvnd和Gradle誰(shuí)更快,mvnd?是?Maven?Daemon?的縮寫?,翻譯成中文就是?Maven?守護(hù)進(jìn)程,下文更多相關(guān)資料,需要的小伙伴可以參考一下2022-05-05一文搞懂接口參數(shù)簽名與驗(yàn)簽(附含java python php版)
這篇文章主要為大家介紹了java python php不同版的接口參數(shù)簽名與驗(yàn)簽示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-06-06Java util.List如何實(shí)現(xiàn)列表分段處理
這篇文章主要介紹了Java util.List如何實(shí)現(xiàn)列表分段處理,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-09-09簡(jiǎn)單講解Java設(shè)計(jì)模式編程中的單一職責(zé)原則
這篇文章主要介紹了Java設(shè)計(jì)模式編程中的單一職責(zé)原則,這在團(tuán)隊(duì)開(kāi)發(fā)編寫接口時(shí)經(jīng)常使用這樣的約定,需要的朋友可以參考下2016-02-02idea的spring boot項(xiàng)目實(shí)現(xiàn)更改端口號(hào)操作
這篇文章主要介紹了idea的spring boot項(xiàng)目實(shí)現(xiàn)更改端口號(hào)操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-09-09java swing 實(shí)現(xiàn)加載自定義的字體
這篇文章主要介紹了java swing 實(shí)現(xiàn)加載自定義的字體,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-11-11java 中用split分割字符串,最后的空格等不被拆分的方法
下面小編就為大家?guī)?lái)一篇java 中用split分割字符串,最后的空格等不被拆分的方法。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-02-02SpringBoot實(shí)現(xiàn)動(dòng)態(tài)增刪啟停定時(shí)任務(wù)的方式
在spring?boot中,可以通過(guò)@EnableScheduling注解和@Scheduled注解實(shí)現(xiàn)定時(shí)任務(wù),也可以通過(guò)SchedulingConfigurer接口來(lái)實(shí)現(xiàn)定時(shí)任務(wù),但是這兩種方式不能動(dòng)態(tài)添加、刪除、啟動(dòng)、停止任務(wù),本文給大家介紹SpringBoot實(shí)現(xiàn)動(dòng)態(tài)增刪啟停定時(shí)任務(wù)的方式,感興趣的朋友一起看看吧2024-03-03