首先，今天主要說說hashMap和hashTable的使用和不同，至于還有個(gè)ConcurrentHashMap，明晚再說吧...|

大家總是對(duì)map來說比較熟一點(diǎn)，那就先說map再說table把

HashMap

基本使用

public class MyTest {

    public static void main(String[] args){

        HashMap<String, String> hashMap = new HashMap<String, String>();
        hashMap.put("cn", "中國");
        hashMap.put("jp", "日本");
        hashMap.put("fr", "法國");
        hashMap.put("cn", "中國2號(hào)");
        System.out.println(hashMap);
        System.out.println("****");
        System.out.println("cn:" + hashMap.get("cn"));
        System.out.println(hashMap.containsKey("cn"));

        System.out.println(hashMap.keySet());
        System.out.println(hashMap.isEmpty());

        hashMap.remove("cn");
        System.out.println(hashMap);
        //采用Iterator遍歷HashMa
        Iterator it = hashMap.keySet().iterator();
        while(it.hasNext()) {
            String key = (String)it.next();
            System.out.println("key:" + key);
            System.out.println("value:" + hashMap.get(key));
        }

        //遍歷HashMap的另一個(gè)方法
        Set<Map.Entry<String, String>> sets = hashMap.entrySet();
        for(Map.Entry<String, String> entry : sets) {
            System.out.print(entry.getKey() + ", ");
            System.out.println(entry.getValue());
        }
    }
}

運(yùn)行結(jié)果

{jp=日本, cn=中國2號(hào), fr=法國}
****
cn:中國2號(hào)
true
[jp, cn, fr]
false
{jp=日本, fr=法國}
key:jp
value:日本
key:fr
value:法國
jp, 日本
fr, 法國

hashMap 總結(jié)

• hashMap是以鍵值對(duì)存儲(chǔ)的（并不是里面有很短鍵值對(duì)），hashMap內(nèi)部維護(hù)一個(gè)entry數(shù)組，每一個(gè)entry是由key-value組成的單向鏈表構(gòu)成的（單向鏈表可解決沖突）；
• hashMap是非線程安全的，如果想多線程使用，請(qǐng)使用util.concurrenr包下的concurrentHashMap
• hashMap內(nèi)部維護(hù)一個(gè)entry數(shù)組，hashMap采用鏈表解決沖突，每個(gè)entry是一個(gè)鏈表，當(dāng)準(zhǔn)備添加一個(gè)key-value時(shí)，首先通過hash(key)計(jì)算出hash值，然后通過indexFor（hash,lenght）求出key-value的儲(chǔ)存位置，（計(jì)算方法是先用hash&0x7FFFFFFF后，再對(duì)length取模，這就保證每一個(gè)key-value對(duì)都能存入HashMap中，當(dāng)計(jì)算出的位置相同時(shí)，由于存入位置是一個(gè)鏈表，則把這個(gè)key-value對(duì)插入鏈表頭）
• hashMap內(nèi)部儲(chǔ)存數(shù)據(jù)的entry數(shù)組默認(rèn)是16（如果儲(chǔ)存的k-v多的話，鏈表就會(huì)很長，所以肯定會(huì)有自己的擴(kuò)容機(jī)制）
• 變量 size(hashMap底層數(shù)組中已用槽的個(gè)數(shù))
• 變量 threshold(hashMap的閥值 threshold = 容量*加載因子)
• 變量 DEFAULT_LOAD_FACTOR = 0.75f，默認(rèn)加載因子為0.75
• hashMap 的擴(kuò)容條件：當(dāng)size > threshold時(shí)，則hashMap開始擴(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的性能。
• 插入元素后才判斷該不該擴(kuò)容，有可能無效擴(kuò)容（插入后如果擴(kuò)容，如果沒有再次插入，就會(huì)產(chǎn)生無效擴(kuò)容）
• HashMap共有四個(gè)構(gòu)造方法。構(gòu)造方法中提到了兩個(gè)很重要的參數(shù)：初始容量和加載因子。這兩個(gè)參數(shù)是影響HashMap性能的重要參數(shù)，其中容量表示哈希表中槽的數(shù)量（即哈希數(shù)組的長度），初始容量是創(chuàng)建哈希表時(shí)的容量（從構(gòu)造函數(shù)中可以看出，如果不指明，則默認(rèn)為16），加載因子是哈希表在其容量自動(dòng)增加之前可以達(dá)到多滿的一種尺度，當(dāng)哈希表中的條目數(shù)超出了加載因子與當(dāng)前容量的乘積時(shí)，則要對(duì)該哈希表進(jìn)行 resize 操作（即擴(kuò)容）
• 如果加載因子越大，對(duì)空間的利用更充分，但是查找效率會(huì)降低（鏈表長度會(huì)越來越長）；如果加載因子太小，那么表中的數(shù)據(jù)將過于稀疏（很多空間還沒用，就開始擴(kuò)容了），對(duì)空間造成嚴(yán)重浪費(fèi)。如果我們?cè)跇?gòu)造方法中不指定，則系統(tǒng)默認(rèn)加載因子為0.75，這是一個(gè)比較理想的值，一般情況下我們是無需修改的
• 無論我們指定的容量為多少，構(gòu)造方法都會(huì)將實(shí)際容量設(shè)為不小于指定容量的2的次方的一個(gè)數(shù)，且最大值不能超過2的30次方

HashTable

基本使用

private static void initHashTable() {
        Hashtable<String, String> table = new Hashtable<String, String>();

        //[1]添加元素
        table.put("cn", "中國");
        table.put("jp", "日本");
        table.put("fr", "法國");
        table.put("cn", "中國2號(hào)");
        //[2]toString()方式打印
        System.out.println(table.toString());
        //都可以 
        System.out.println(table);
        //[3]Iterator遍歷方式1--鍵值對(duì)遍歷entrySet()
        Iterator<Map.Entry<String, String>> iter = table.entrySet().iterator();
        while(iter.hasNext()){
            Map.Entry<String, String> entry = (Map.Entry<String, String>)iter.next();
            String key = entry.getKey();
            String value = entry.getValue();
            System.out.println("entrySet:"+key+" "+value);
        }

        System.out.println("====================================");

        //[4]Iterator遍歷方式2--key鍵的遍歷
        Iterator<String> iterator = table.keySet().iterator();
        while(iterator.hasNext()){
            String key = (String)iterator.next();
            String value = table.get(key);
            System.out.println("keySet:"+key+" "+value);
        }

        System.out.println("====================================");

        //[5]通過Enumeration來遍歷Hashtable
        Enumeration<String> enu = table.keys();
        while(enu.hasMoreElements()) {
            System.out.println("Enumeration:"+table.keys()+" "+enu.nextElement());
        }
    }

運(yùn)行結(jié)構(gòu)

{jp=日本, fr=法國, cn=中國2號(hào)}
{jp=日本, fr=法國, cn=中國2號(hào)}
entrySet:jp 日本
entrySet:fr 法國
entrySet:cn 中國2號(hào)
====================================
keySet:jp 日本
keySet:fr 法國
keySet:cn 中國2號(hào)
====================================
Enumeration:java.util.Hashtable$Enumerator@4554617c jp
Enumeration:java.util.Hashtable$Enumerator@74a14482 fr
Enumeration:java.util.Hashtable$Enumerator@1540e19d cn

兩者的不同

1、作者不同

• hashmap:

* @author  Doug Lea
 * @author  Josh Bloch
 * @author  Arthur van Hoff
 * @author  Neal Gafter

• hashtbale

 * @author  Arthur van Hoff
 * @author  Josh Bloch
 * @author  Neal Gafter

總結(jié)：map比table多了一個(gè)人，而dl也是util.concurrent包的作者

2、產(chǎn)生時(shí)間

hashmap產(chǎn)生于jdk1.2
hashTable產(chǎn)生于jdk1.0

3、繼承的父類不同

• hashTable

public class Hashtable<K,V>
         extends Dictionary<K,V>
         implements Map<K,V>, Cloneable, java.io.Serializable {

備注：Dictionary類是一個(gè)已經(jīng)被廢棄的類（見其源碼中的注釋）。父類都被廢棄，自然而然也沒人用它的子類Hashtable了。

• NOTE: This class is obsolete. New implementations should
• implement the Map interface, rather than extending this class.
• hashMap

public class HashMap<K,V> 
          extends AbstractMap<K,V>
          implements Map<K,V>, Cloneable, Serializable {

4、對(duì)外接口不同

Hashtable比HashMap多提供了elments() 和contains() 兩個(gè)方法。
elments() 方法繼承自Hashtable的父類Dictionnary。elements() 方法用于返回此Hashtable中的value的枚舉。

   * @see     #keys()
     * @see     #values()
     * @see     Map
     */
    public synchronized Enumeration<V> elements() {
        return this.<V>getEnumeration(VALUES);
    }
    /**
     * Tests if some key maps into the specified value in this hashtable.
     * This operation is more expensive than the {@link #containsKey
     * containsKey} method.

contains()方法判斷該Hashtable是否包含傳入的value。它的作用與containsValue()一致。事實(shí)上，contansValue() 就只是調(diào)用了一下contains() 方法。

   * @param value value whose presence in this hashtable is to be tested
     * @return <tt>true</tt> if this map maps one or more keys to the
     *         specified value
     * @throws NullPointerException  if the value is <code>null</code>
     * @since 1.2
     */
    public boolean containsValue(Object value) {
        return contains(value);
    }
    /**
     * Tests if the specified object is a key in this hashtable.
     *
     * @param   key   possible key
     * @return  <code>true</code> if and only if the specified object

5、對(duì)null key 和 null value 的支持不同

hashTable:

//        table.put(null,"fsdfd");//會(huì)報(bào)空指針
//        table.put("cdcd",null);//也會(huì)報(bào)空指針

hashMap:

rivate static void initHashMap() {
        HashMap<String, String> hashMap = new HashMap<String, String>();
        hashMap.put("cn", "中國");
        hashMap.put("jp", "日本");
        hashMap.put("fr", "法國");
        hashMap.put("cn", "中國2號(hào)");
        hashMap.put(null,"空");
        hashMap.put("nu",null);
        System.out.println(hashMap);

運(yùn)行結(jié)構(gòu)

{null=空, jp=日本, nu=null, cn=中國2號(hào), fr=法國}

注意：HashMap中，null可以作為鍵，這樣的鍵只有一個(gè)；可以有一個(gè)或多個(gè)鍵所對(duì)應(yīng)的值為null。當(dāng)get()方法返回null值時(shí)，可能是 HashMap中沒有該鍵，也可能使該鍵所對(duì)應(yīng)的值為null。因此，在HashMap中不能由get()方法來判斷HashMap中是否存在某個(gè)鍵， 而應(yīng)該用containsKey()方法來判斷。

6、線程安全不同

• Hashtable是線程安全的，它的每個(gè)方法中都加入了Synchronize方法(鎖住了整個(gè)hashTable)。在多線程并發(fā)的環(huán)境下，可以直接使用Hashtable，不需要自己為它的方法實(shí)現(xiàn)同步,

• HashMap不是線程安全的，在多線程并發(fā)的環(huán)境下，可能會(huì)產(chǎn)生死鎖等問題。具體的原因在下一篇文章中會(huì)詳細(xì)進(jìn)行分析。使用HashMap時(shí)就必須要自己增加同步處理

• 雖然HashMap不是線程安全的，但是它的效率會(huì)比Hashtable要好很多。這樣設(shè)計(jì)是合理的。在我們的日常使用當(dāng)中，大部分時(shí)間是單線程操作的。HashMap把這部分操作解放出來了。當(dāng)需要多線程操作的時(shí)候可以使用線程安全的ConcurrentHashMap。ConcurrentHashMap雖然也是線程安全的，但是它的效率比Hashtable要高好多倍。因?yàn)镃oncurrentHashMap使用了分段鎖，并不對(duì)整個(gè)數(shù)據(jù)進(jìn)行鎖定。

7、遍歷實(shí)現(xiàn)的內(nèi)部方式不同

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

HashMap的Iterator是fail-fast迭代器。當(dāng)有其它線程改變了HashMap的結(jié)構(gòu)（增加，刪除，修改元素），將會(huì)拋出ConcurrentModificationException。不過，通過Iterator的remove()方法移除元素則不會(huì)拋出ConcurrentModificationException異常。但這并不是一個(gè)一定發(fā)生的行為，要看JVM。

JDK8之前的版本中，Hashtable是沒有fast-fail機(jī)制的。在JDK8及以后的版本中 ，HashTable也是使用fast-fail的， 源碼如下：
modCount的使用類似于并發(fā)編程中的CAS（Compare and Swap）技術(shù)。我們可以看到這個(gè)方法中，每次在發(fā)生增刪改的時(shí)候都會(huì)出現(xiàn)modCount++的動(dòng)作。而modcount可以理解為是當(dāng)前hashtable的狀態(tài)。每發(fā)生一次操作，狀態(tài)就向前走一步。設(shè)置這個(gè)狀態(tài)，主要是由于hashtable等容器類在迭代時(shí)，判斷數(shù)據(jù)是否過時(shí)時(shí)使用的。盡管hashtable采用了原生的同步鎖來保護(hù)數(shù)據(jù)安全。但是在出現(xiàn)迭代數(shù)據(jù)的時(shí)候，則無法保證邊迭代，邊正確操作。于是使用這個(gè)值來標(biāo)記狀態(tài)。一旦在迭代的過程中狀態(tài)發(fā)生了改變，則會(huì)快速拋出一個(gè)異常，終止迭代行為。

8、初始容量大小和每次擴(kuò)充容量大小的不同

Hashtable默認(rèn)的初始大小為11，之后每次擴(kuò)充，容量變?yōu)樵瓉淼?n+1。HashMap默認(rèn)的初始化大小為16。之后每次擴(kuò)充，容量變?yōu)樵瓉淼?倍。

創(chuàng)建時(shí)，如果給定了容量初始值，那么Hashtable會(huì)直接使用你給定的大小，而HashMap會(huì)將其擴(kuò)充為2的冪次方大小。也就是說Hashtable會(huì)盡量使用素?cái)?shù)、奇數(shù)。而HashMap則總是使用2的冪作為哈希表的大小。

之所以會(huì)有這樣的不同，是因?yàn)镠ashtable和HashMap設(shè)計(jì)時(shí)的側(cè)重點(diǎn)不同。Hashtable的側(cè)重點(diǎn)是哈希的結(jié)果更加均勻，使得哈希沖突減少。當(dāng)哈希表的大小為素?cái)?shù)時(shí)，簡單的取模哈希的結(jié)果會(huì)更加均勻。而HashMap則更加關(guān)注hash的計(jì)算效率問題。在取模計(jì)算時(shí)，如果模數(shù)是2的冪，那么我們可以直接使用位運(yùn)算來得到結(jié)果，效率要大大高于做除法。HashMap為了加快hash的速度，將哈希表的大小固定為了2的冪。當(dāng)然這引入了哈希分布不均勻的問題，所以HashMap為解決這問題，又對(duì)hash算法做了一些改動(dòng)。這從而導(dǎo)致了Hashtable和HashMap的計(jì)算hash值的方法不同

• hashMap為什么是2的n次冪？
  HashMap為了存取高效，要盡量較少碰撞，就是要盡量把數(shù)據(jù)分配均勻，每個(gè)鏈表長度大致相同，這個(gè)實(shí)現(xiàn)就在把數(shù)據(jù)存到哪個(gè)鏈表中的算法；
  這個(gè)算法實(shí)際就是取模，hash%length，計(jì)算機(jī)中直接求余效率不如位移運(yùn)算，源碼中做了優(yōu)化hash&(length-1)，
  hash%length==hash&(length-1)的前提是length是2的n次方；
  為什么這樣能均勻分布減少碰撞呢？2的n次方實(shí)際就是1后面n個(gè)0，2的n次方-1 實(shí)際就是n個(gè)1；
  例如長度為9時(shí)候，3&(9-1)=0 2&(9-1)=0 ，都在0上，碰撞了；
  例如長度為8時(shí)候，3&(8-1)=3 2&(8-1)=2 ，不同位置上，不碰撞；

• jdk1.8對(duì)hashMap做的優(yōu)化
  這里存在一個(gè)問題，即使負(fù)載因子和Hash算法設(shè)計(jì)的再合理，也免不了會(huì)出現(xiàn)拉鏈過長的情況，一旦出現(xiàn)拉鏈過長，則會(huì)嚴(yán)重影響HashMap的性能。于是，在JDK1.8版本中，對(duì)數(shù)據(jù)結(jié)構(gòu)做了進(jìn)一步的優(yōu)化，引入了紅黑樹。而當(dāng)鏈表長度太長（默認(rèn)超過8）時(shí)，鏈表就轉(zhuǎn)換為紅黑樹，利用紅黑樹快速增刪改查的特點(diǎn)提高HashMap的性能，其中會(huì)用到紅黑樹的插入、刪除、查找等算法。
  當(dāng)插入新元素時(shí)，對(duì)于紅黑樹的判斷如下：
  判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對(duì)，否則轉(zhuǎn)向下面；
  遍歷table[i]，判斷鏈表長度是否大于8，大于8的話把鏈表轉(zhuǎn)換為紅黑樹，在紅黑樹中執(zhí)行插入操作，否則進(jìn)行鏈表的插入操作；遍歷過程中若發(fā)現(xiàn)key已經(jīng)存在直接覆蓋value即可；

9、計(jì)算hash值的方法不同

為了得到元素的位置，首先需要根據(jù)元素的 KEY計(jì)算出一個(gè)hash值，然后再用這個(gè)hash值來計(jì)算得到最終的位置。

Hashtable直接使用對(duì)象的hashCode。hashCode是JDK根據(jù)對(duì)象的地址或者字符串或者數(shù)字算出來的int類型的數(shù)值。然后再使用除留余數(shù)發(fā)來獲得最終的位置。

Hashtable在計(jì)算元素的位置時(shí)需要進(jìn)行一次除法運(yùn)算，而除法運(yùn)算是比較耗時(shí)的。
HashMap為了提高計(jì)算效率，將哈希表的大小固定為了2的冪，這樣在取模預(yù)算時(shí)，不需要做除法，只需要做位運(yùn)算。位運(yùn)算比除法的效率要高很多。

HashMap的效率雖然提高了，但是hash沖突卻也增加了。因?yàn)樗贸龅膆ash值的低位相同的概率比較高，而計(jì)算位運(yùn)算

為了解決這個(gè)問題，HashMap重新根據(jù)hashcode計(jì)算hash值后，又對(duì)hash值做了一些運(yùn)算來打散數(shù)據(jù)。使得取得的位置更加分散，從而減少了hash沖突。當(dāng)然了，為了高效，HashMap只做了一些簡單的位處理。從而不至于把使用2 的冪次方帶來的效率提升給抵消掉。