第Java集合框架之Set和Map詳解Vget(Objectkey);//返回指定鍵對應(yīng)的值

Vremove(Objectkey);//從映射中刪除指定鍵對應(yīng)的元素。

Java為映射提供了倆個通用的實現(xiàn)：HashMap和TreeMap

HashMap

publicclassHashMapK,VextendsAbstractMapK,V

implementsMapK,V,Cloneable,Serializable{

實現(xiàn)了Map接口，存儲的內(nèi)容是鍵值對(key-value)映射，將鍵進(jìn)行散列，散列或比較函數(shù)只應(yīng)用于鍵，與鍵相關(guān)的值不進(jìn)行散列或比較。

HashMap底層的結(jié)構(gòu)是，散列表（數(shù)組和鏈表）和紅黑樹

我用反射的方式輸出了這個map的容量，可以看到如果使用無參的構(gòu)造方法，那么map的容量默認(rèn)為16。我們也可以通過傳參的方式，來指定它的容量，值的一提的是，你指定的容量，一定要為2的冪次方，且要小于int范圍內(nèi)最大的2的冪次方數(shù)（1073741824）。

//指定容量

HashMapString,Stringmap=newHashMapString,String

這個構(gòu)造方法還是調(diào)用了下面的這個構(gòu)造方法，只是把默認(rèn)的負(fù)載因子值傳進(jìn)去了：

put方法，直接看源碼：

publicVput(Kkey,Vvalue){

returnputVal(hash(key),key,value,false,true);

調(diào)用put方法后，會根據(jù)鍵值來計算一個值（位置），然后調(diào)用putVal來存放元素。

finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,

booleanevict){

NodeK,V[]tab;NodeK,Vintn,i;

//hash表為空或者長度為0的話，創(chuàng)建hash表

if((tab=table)==null||(n=tab.length)==0)

n=(tab=resize()).length;//resize()HashMap擴(kuò)容的方法

if((p=tab[i=(n-1)hash])==null)

//如果位置上沒有元素，就加進(jìn)去，成為鏈表的頭結(jié)點(diǎn)

tab[i]=newNode(hash,key,value,null);

else{

NodeK,VKk;

if(p.hash==hash

((k=p.key)==key||(key!=nullkey.equals(k))))

e=p;

//如果這個值的類型為樹結(jié)構(gòu)的話，就直接添加到樹中，不會判斷是否超過8

elseif(pinstanceofTreeNode)

e=((TreeNodeK,V)p).putTreeVal(this,tab,hash,key,value);

else{

//binCount鏈表的長度

for(intbinCount=0;;++binCount){

if((e=p.next)==null){

//如果鏈表不為空，就往下一個節(jié)點(diǎn)添加

p.next=newNode(hash,key,value,null);

//如果這個鏈表的長度大于8，就會轉(zhuǎn)為紅黑樹存儲

if(binCount=TREEIFY_THRESHOLD-1)

treeifyBin(tab,hash);

break;

if(e.hash==hash

((k=e.key)==key||(key!=nullkey.equals(k))))

break;

p=e;

//如果該鍵已經(jīng)有映射關(guān)系的話，用這次的值覆蓋掉之前的值

if(e!=null){//existingmappingforkey

VoldValue=e.value;

if(!onlyIfAbsent||oldValue==null)

e.value=value;

afterNodeAccess(e);

returnoldValue;

++modCount;

//如果里面的元素超過threshold的話就擴(kuò)容

if(++sizethreshold)

resize();

afterNodeInsertion(evict);

returnnull;

通過代碼中的注釋，相信你已經(jīng)初步了解了put方法，總的來說就是添加時首先是用k通過哈希函數(shù)計算位置，位置上如果沒有元素添加在鏈表的頭結(jié)點(diǎn)，如果有插入到鏈表的下一個節(jié)點(diǎn)，當(dāng)鏈表的長度為大于等于8時，轉(zhuǎn)為紅黑樹存儲，如果該鍵已經(jīng)有映射關(guān)系的話，用這次的值覆蓋掉之前的值，最后判斷要不要擴(kuò)容。如果要擴(kuò)容，會擴(kuò)容為原來容量的2倍。這樣效率會高一些，也可以減少哈希沖突。

負(fù)載因子

上文中我們提到了負(fù)載因子，那么負(fù)載因子是什么呢？

負(fù)載因子也叫裝填因子，是一個0.0~1.0之間的數(shù)，確定散列表填充的百分比，當(dāng)大于這個百分比時，散列表進(jìn)行再散列。在map中，也就是說，當(dāng)put的元素數(shù)量超過一定值的時候，就會擴(kuò)容，這個值就是負(fù)載因子*容量。

HashMap中的負(fù)載因子默認(rèn)是0.75：

staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;

就是說如果map中的元素超過容量的3/4就要進(jìn)行擴(kuò)容。

那么為什么這里要默認(rèn)為0.75呢？這了也是規(guī)定了一個相對合理的值，如果為1的話效率太低，滿了之后才擴(kuò)容；如果為0.5的話，浪費(fèi)空間。所以選了一個居中的值。

TreeMap

publicclassTreeMapK,V

extendsAbstractMapK,V

implementsNavigableMapK,V,Cloneable,java.io.Serializable{

它沒有實現(xiàn)Map接口是因為AbstractMap實現(xiàn)了Map接口，TreeM