1驰怎、HashMap介紹

HashMap是基于哈希表實(shí)現(xiàn)的，每一個(gè)元素是一個(gè)key-value對(duì)二打，其內(nèi)部通過(guò)單鏈表解決沖突問(wèn)題县忌，容量不足（超過(guò)了閥值）時(shí)，同樣會(huì)自動(dòng)增長(zhǎng)继效。

HashMap是非線程安全的症杏，只是用于單線程環(huán)境下，多線程環(huán)境下可以采用concurrent并發(fā)包下的concurrentHashMap瑞信。

HashMap 實(shí)現(xiàn)了Serializable接口厉颤，因此它支持序列化，實(shí)現(xiàn)了Cloneable接口凡简，能被克隆逼友。

HashMap存數(shù)據(jù)的過(guò)程是：

HashMap內(nèi)部維護(hù)了一個(gè)存儲(chǔ)數(shù)據(jù)的Entry數(shù)組，HashMap采用鏈表解決沖突秤涩，每一個(gè)Entry本質(zhì)上是一個(gè)單向鏈表帜乞。當(dāng)準(zhǔn)備添加一個(gè)key-value對(duì)時(shí)，首先通過(guò)hash(key)方法計(jì)算hash值筐眷，然后通過(guò)indexFor(hash,length)求該key-value對(duì)的存儲(chǔ)位置黎烈，計(jì)算方法是先用hash&0x7FFFFFFF后，再對(duì)length取模匀谣，這就保證每一個(gè)key-value對(duì)都能存入HashMap中照棋，當(dāng)計(jì)算出的位置相同時(shí)，由于存入位置是一個(gè)鏈表武翎，則把這個(gè)key-value對(duì)插入鏈表頭必怜。

HashMap中key和value都允許為null。key為null的鍵值對(duì)永遠(yuǎn)都放在以table[0]為頭結(jié)點(diǎn)的鏈表中后频。

HashMap的存儲(chǔ)結(jié)構(gòu)

圖中梳庆，紫色部分即代表哈希表，也稱為哈希數(shù)組卑惜，數(shù)組的每個(gè)元素都是一個(gè)單鏈表的頭節(jié)點(diǎn)膏执，鏈表是用來(lái)解決沖突的，如果不同的key映射到了數(shù)組的同一位置處露久，就將其放入單鏈表中更米。

HashMap內(nèi)存儲(chǔ)數(shù)據(jù)的Entry數(shù)組默認(rèn)是16，如果沒(méi)有對(duì)Entry擴(kuò)容機(jī)制的話毫痕，當(dāng)存儲(chǔ)的數(shù)據(jù)一多征峦，Entry內(nèi)部的鏈表會(huì)很長(zhǎng)迟几，這就失去了HashMap的存儲(chǔ)意義了。所以HasnMap內(nèi)部有自己的擴(kuò)容機(jī)制栏笆。HashMap內(nèi)部有：

變量size类腮，它記錄HashMap的底層數(shù)組中已用槽的數(shù)量；

變量threshold蛉加，它是HashMap的閾值蚜枢，用于判斷是否需要調(diào)整HashMap的容量（threshold = 容量*加載因子）

變量DEFAULT_LOAD_FACTOR = 0.75f，默認(rèn)加載因子為0.75

HashMap擴(kuò)容的條件是：當(dāng)size大于threshold時(shí)针饥，對(duì)HashMap進(jìn)行擴(kuò)容

擴(kuò)容是是新建了一個(gè)HashMap的底層數(shù)組厂抽，而后調(diào)用transfer方法，將就HashMap的全部元素添加到新的HashMap中（要重新計(jì)算元素在新的數(shù)組中的索引位置）丁眼。 很明顯筷凤，擴(kuò)容是一個(gè)相當(dāng)耗時(shí)的操作，因?yàn)樗枰匦掠?jì)算這些元素在新的數(shù)組中的位置并進(jìn)行復(fù)制處理苞七。因此嵌施，我們?cè)谟肏ashMap的時(shí)，最好能提前預(yù)估下HashMap中元素的個(gè)數(shù)莽鸭，這樣有助于提高HashMap的性能吗伤。

HashMap共有四個(gè)構(gòu)造方法。構(gòu)造方法中提到了兩個(gè)很重要的參數(shù)：初始容量和加載因子硫眨。這兩個(gè)參數(shù)是影響HashMap性能的重要參數(shù)足淆，其中容量表示哈希表中槽的數(shù)量（即哈希數(shù)組的長(zhǎng)度），初始容量是創(chuàng)建哈希表時(shí)的容量（從構(gòu)造函數(shù)中可以看出礁阁，如果不指明巧号，則默認(rèn)為16），加載因子是哈希表在其容量自動(dòng)增加之前可以達(dá)到多滿的一種尺度姥闭，當(dāng)哈希表中的條目數(shù)超出了加載因子與當(dāng)前容量的乘積時(shí)丹鸿，則要對(duì)該哈希表進(jìn)行 resize 操作（即擴(kuò)容）。

下面說(shuō)下加載因子棚品，如果加載因子越大靠欢，對(duì)空間的利用更充分，但是查找效率會(huì)降低（鏈表長(zhǎng)度會(huì)越來(lái)越長(zhǎng)）铜跑；如果加載因子太小门怪，那么表中的數(shù)據(jù)將過(guò)于稀疏（很多空間還沒(méi)用，就開(kāi)始擴(kuò)容了）锅纺，對(duì)空間造成嚴(yán)重浪費(fèi)掷空。如果我們?cè)跇?gòu)造方法中不指定，則系統(tǒng)默認(rèn)加載因子為0.75，這是一個(gè)比較理想的值坦弟，一般情況下我們是無(wú)需修改的护锤。

另外，無(wú)論我們指定的容量為多少酿傍，構(gòu)造方法都會(huì)將實(shí)際容量設(shè)為不小于指定容量的2的次方的一個(gè)數(shù)烙懦，且最大值不能超過(guò)2的30次方。

HashMap源碼剖析：http://blog.csdn.net/ns_code/article/details/36034955

2拧粪、Hashtable簡(jiǎn)介

Hashtable同樣是基于哈希表實(shí)現(xiàn)的修陡，同樣每個(gè)元素是一個(gè)key-value對(duì)，其內(nèi)部也是通過(guò)單鏈表解決沖突問(wèn)題，容量不足（超過(guò)了閥值）時(shí)闰非，同樣會(huì)自動(dòng)增長(zhǎng)俭茧。

Hashtable也是JDK1.0引入的類，是線程安全的碌尔，能用于多線程環(huán)境中。

Hashtable同樣實(shí)現(xiàn)了Serializable接口，它支持序列化旷余，實(shí)現(xiàn)了Cloneable接口，能被克隆扁达。

Hashtable和HashMap比較相似

Hashtable源碼剖析:http://blog.csdn.net/ns_code/article/details/36191279

3正卧、HashTable和HashMap區(qū)別

• （1）繼承的父類不同

  Hashtable繼承自Dictionary類，而HashMap繼承自AbstractMap類跪解。但二者都實(shí)現(xiàn)了Map接口炉旷。

• （2）線程安全性不同

javadoc中關(guān)于hashmap的一段描述如下：此實(shí)現(xiàn)不是同步的。如果多個(gè)線程同時(shí)訪問(wèn)一個(gè)哈希映射叉讥，而其中至少一個(gè)線程從結(jié)構(gòu)上修改了該映射窘行，則它必須保持外部同步。

Hashtable 中的方法是Synchronize的图仓，而HashMap中的方法在缺省情況下是非Synchronize的罐盔。在多線程并發(fā)的環(huán)境下，可以直接使用Hashtable救崔，不需要自己為它的方法實(shí)現(xiàn)同步惶看，但使用HashMap時(shí)就必須要自己增加同步處理。（結(jié)構(gòu)上的修改是指添加或刪除一個(gè)或多個(gè)映射關(guān)系的任何操作六孵；僅改變與實(shí)例已經(jīng)包含的鍵關(guān)聯(lián)的值不是結(jié)構(gòu)上的修改碳竟。）這一般通過(guò)對(duì)自然封裝該映射的對(duì)象進(jìn)行同步操作來(lái)完成。如果不存在這樣的對(duì)象狸臣，則應(yīng)該使用 Collections.synchronizedMap 方法來(lái)“包裝”該映射莹桅。最好在創(chuàng)建時(shí)完成這一操作，以防止對(duì)映射進(jìn)行意外的非同步訪問(wèn)，如下所示：

Map m = Collections.synchronizedMap(new HashMap(...));

Hashtable 線程安全很好理解诈泼，因?yàn)樗總€(gè)方法中都加入了Synchronize懂拾。這里我們分析一下HashMap為什么是線程不安全的：

HashMap底層是一個(gè)Entry數(shù)組，當(dāng)發(fā)生hash沖突的時(shí)候铐达，hashmap是采用鏈表的方式來(lái)解決的岖赋，在對(duì)應(yīng)的數(shù)組位置存放鏈表的頭結(jié)點(diǎn)。對(duì)鏈表而言瓮孙，新加入的節(jié)點(diǎn)會(huì)從頭結(jié)點(diǎn)加入唐断。

• （3）是否提供contains方法

HashMap把Hashtable的contains方法去掉了，改成containsValue和containsKey杭抠，因?yàn)閏ontains方法容易讓人引起誤解脸甘。

Hashtable則保留了contains，containsValue和containsKey三個(gè)方法偏灿，其中contains和containsValue功能相同丹诀。

Hashtable的ContainsKey方法和ContainsValue的源碼：

public boolean containsValue(Object value) {      
     return contains(value);      
 } 

// 判斷Hashtable是否包含“值(value)”      
public synchronized boolean contains(Object value) {      
     //注意，Hashtable中的value不能是null翁垂，      
     // 若是null的話铆遭，拋出異常!      
     if (value == null) {      
         throw new NullPointerException();      
     }      
    
     // 從后向前遍歷table數(shù)組中的元素(Entry)      
     // 對(duì)于每個(gè)Entry(單向鏈表)，逐個(gè)遍歷沿猜，判斷節(jié)點(diǎn)的值是否等于value      
     Entry tab[] = table;      
     for (int i = tab.length ; i-- > 0 ;) {      
         for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {      
             if (e.value.equals(value)) {      
                 return true;      
             }      
         }      
     }      
     return false;      
 } 

// 判斷Hashtable是否包含key      
public synchronized boolean containsKey(Object key) {      
     Entry tab[] = table;      
     //計(jì)算hash值枚荣，直接用key的hashCode代替    
     int hash = key.hashCode();        
     // 計(jì)算在數(shù)組中的索引值     
     int index = (hash & 0x7FFFFFFF) % tab.length;      
     // 找到“key對(duì)應(yīng)的Entry(鏈表)”，然后在鏈表中找出“哈希值”和“鍵值”與key都相等的元素      
     for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {      
         if ((e.hash == hash) && e.key.equals(key)) {      
             return true;      
         }      
     }      
     return false;      
 }  

HashMap的ContainsKey方法和ContainsValue的源碼：

// HashMap是否包含key      
public boolean containsKey(Object key) {      
     return getEntry(key) != null;      
}  

// 返回“鍵為key”的鍵值對(duì)      
final Entry<K,V> getEntry(Object key) {      
     // 獲取哈希值      
     // HashMap將“key為null”的元素存儲(chǔ)在table[0]位置啼肩，“key不為null”的則調(diào)用hash()計(jì)算哈希值      
     int hash = (key == null) ? 0 : hash(key.hashCode());      
     // 在“該hash值對(duì)應(yīng)的鏈表”上查找“鍵值等于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;      
}  

// 是否包含“值為value”的元素      
public boolean containsValue(Object value) {      
    // 若“value為null”橄妆，則調(diào)用containsNullValue()查找      
    if (value == null)      
            return containsNullValue();      
     
    // 若“value不為null”，則查找HashMap中是否有值為value的節(jié)點(diǎn)疟游。      
    Entry[] tab = table;      
        for (int i = 0; i < tab.length ; i++)      
            for (Entry e = tab[i] ; e != null ; e = e.next)      
                if (value.equals(e.value))      
                    return true;      
    return false;      
}  

• （4）key和value是否允許null值

  其中key和value都是對(duì)象呼畸，并且不能包含重復(fù)key，但可以包含重復(fù)的value颁虐。

  通過(guò)上面的ContainsKey方法和ContainsValue的源碼我們可以很明顯的看出：

Hashtable中蛮原，key和value都不允許出現(xiàn)null值。但是如果在Hashtable中有類似put(null,null)的操作另绩，編譯同樣可以通過(guò)儒陨，因?yàn)閗ey和value都是Object類型，但運(yùn)行時(shí)會(huì)拋出NullPointerException異常笋籽，這是JDK的規(guī)范規(guī)定的蹦漠。
HashMap中，null可以作為鍵车海，這樣的鍵只有一個(gè)笛园；可以有一個(gè)或多個(gè)鍵所對(duì)應(yīng)的值為null。當(dāng)get()方法返回null值時(shí)，可能是 HashMap中沒(méi)有該鍵研铆，也可能使該鍵所對(duì)應(yīng)的值為null埋同。因此，在HashMap中不能由get()方法來(lái)判斷HashMap中是否存在某個(gè)鍵棵红， 而應(yīng)該用containsKey()方法來(lái)判斷凶赁。

• （5）兩個(gè)遍歷方式的內(nèi)部實(shí)現(xiàn)上不同

Hashtable、HashMap都使用了 Iterator逆甜。而由于歷史原因虱肄，Hashtable還使用了Enumeration的方式 。

• （6）hash值不同

哈希值的使用不同交煞，HashTable直接使用對(duì)象的hashCode咏窿。而HashMap重新計(jì)算hash值。

hashCode是jdk根據(jù)對(duì)象的地址或者字符串或者數(shù)字算出來(lái)的int類型的數(shù)值错敢。

Hashtable計(jì)算hash值翰灾，直接用key的hashCode()缕粹，而HashMap重新計(jì)算了key的hash值稚茅，Hashtable在求hash值對(duì)應(yīng)的位置索引時(shí)，用取模運(yùn)算平斩，而HashMap在求位置索引時(shí)亚享，則用與運(yùn)算，且這里一般先用hash&0x7FFFFFFF后绘面，再對(duì)length取模欺税，&0x7FFFFFFF的目的是為了將負(fù)的hash值轉(zhuǎn)化為正值，因?yàn)閔ash值有可能為負(fù)數(shù)揭璃，而&0x7FFFFFFF后晚凿，只有符號(hào)外改變，而后面的位都不變瘦馍。

• （7）內(nèi)部實(shí)現(xiàn)使用的數(shù)組初始化和擴(kuò)容方式不同

HashTable在不指定容量的情況下的默認(rèn)容量為11歼秽，而HashMap為16，Hashtable不要求底層數(shù)組的容量一定要為2的整數(shù)次冪情组，而HashMap則要求一定為2的整數(shù)次冪燥筷。

Hashtable擴(kuò)容時(shí)，將容量變?yōu)樵瓉?lái)的2倍加1院崇，而HashMap擴(kuò)容時(shí)肆氓，將容量變?yōu)樵瓉?lái)的2倍。

Hashtable和HashMap它們兩個(gè)內(nèi)部實(shí)現(xiàn)方式的數(shù)組的初始大小和擴(kuò)容的方式底瓣。HashTable中hash數(shù)組默認(rèn)大小是11谢揪，增加的方式是 old*2+1。