剖析java中hashmap數(shù)據(jù)結(jié)構(gòu)的源碼及其性能優(yōu)化

《剖析java中hashmap數(shù)據(jù)結(jié)構(gòu)的源碼及其性能優(yōu)化》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、剖析Java中HashMap數(shù)據(jù)結(jié)構(gòu)的源碼及其性能優(yōu)化這篇文章主要介紹了Java中HashMap數(shù)據(jù)結(jié)構(gòu)的源碼及其性能優(yōu)化,文中以Java8后HashMap的性能提升來(lái)討論了HashMap的一些優(yōu)化點(diǎn)，需要的朋友可以參考下存儲(chǔ)結(jié)構(gòu)首先，HashMap是基于哈希表存儲(chǔ)的。它內(nèi)部有一個(gè)數(shù)組，當(dāng)元素要存儲(chǔ)的時(shí)候，先計(jì)算其key的哈希值，根據(jù)哈希值找到元素在數(shù)組中對(duì)應(yīng)的下標(biāo)。如杲這個(gè)位置沒(méi)有元素，就直接把當(dāng)前元素放進(jìn)去，如果有元素了（這里記為A）,就把當(dāng)前元素鏈接到元素A的前面，然后把當(dāng)前元素放入數(shù)組屮。所以在Hashmap數(shù)組其實(shí)保存的是鏈表的首節(jié)點(diǎn)。下面是百度百科的一張圖：EntryEn

2、tryEntryKeyKeyEntryValueValueEnttyEntryEntryEntryEnttyEntryEntry如上圖，每個(gè)元素是一個(gè)Entry對(duì)象，在其屮保存了元素的key和value,還有一個(gè)指針可用于指向下一個(gè)對(duì)象。所有哈希值相同的key（也就是沖突了）用鏈表把它們串起來(lái)，這是拉鏈法。內(nèi)部變量〃默認(rèn)初始容量staticfinalintDEFAULT_INITIAL_CAPACITY=16;〃最大容量staticfinalintMAXIMUM_CAPACITY=1?30;〃默認(rèn)裝載因子staticfinalfloatDEFAULT_LOAD_FACTOR=0.75

3、f;〃哈希表transientEntry[]table;〃鍵值對(duì)的數(shù)量transientintsize;〃擴(kuò)容的閾值intthreshold;〃哈希數(shù)組的裝載因子finalfloatloadFactor;在上面的變量中，capacity是指哈希表的長(zhǎng)度，也就是table的大小，默認(rèn)為16。裝載因子loadFactor是哈希表的“裝滿程度”，JDK的文檔是這樣說(shuō)的：Theloadfactorisameasureofhowfullthehashtableisallowedtogetbeforeitscapacityisautomaticallyincreased?Whenthe

4、numberofentriesinthehashtableexceedstheproductoftheloadfactorandthecurrentcapacity,thehashtableisrehashed(thatis,internaldatastructuresarerebuilt)sothatthehashtablehasapproximatelytwicethenumberofbuckets?大體意思是：裝載因子是哈希表在擴(kuò)容之前能裝多滿的度量值。當(dāng)哈希表中“鍵值對(duì)”的數(shù)量超過(guò)當(dāng)前容M(capacity)和裝載因子的乘積后，哈希表重新散列(也就是內(nèi)部的數(shù)據(jù)結(jié)構(gòu)重建了)，并

5、且哈希表的容量大約變?yōu)樵瓉?lái)的兩倍。從上面的變量定義可以看出，默認(rèn)的裝載因子DEFAULT_LOAD_FACTOR是0.75。這個(gè)值越大,空間利用率越高，但查詢速度(包括get和put)操作會(huì)變慢。明白了裝載因子之后，threshold也就能理解了，它其實(shí)等于容量*裝載因子。構(gòu)造器publicHashMap(intinitialCapacity,floatloadFactor){if(initialcapacity<0)thrownewHlegalArgumentException("lllegalinitialcapacity:"+initialcapacity);if(initia

6、lCapacity>MAXIMUM_CAPACITY)initialcapacity=MAXIMUM_CAPACITY;if(loadFactor<=011Float.isNaN(loadFactor))thrownewHlegalArgumentException("Illegalloadfactor:"+loadFactor);//Findapowerof2>=initialcapacityintcapacity=1;while(capacity

7、ctor;threshold=(int)Math.min(capacity*loadFactor,MAXIMUM_CAPACITY+1);table=newEntry[capacity];〃給哈希表分配空間useAltHashing=sun.misc.VM.isBooted()&&(capacity>=Holder.ALTERNATIVE_HASHING_THRESHOLD);init();}構(gòu)造器有好兒個(gè)，最終都會(huì)調(diào)用上面的這個(gè)。它接受兩個(gè)參數(shù)，一個(gè)是初