前言：

• 這次寫幾篇 關(guān)于 HashMap，HashTable，ConcurrentHashMap，LinkedHashMap，LURLinkedHashMap 源碼分析。
• 如果直接將他們源碼，并不好理解，所以這里我會圍繞著HashMap，用對比的方式進(jìn)行介紹。
• 由于不同的jdk版本，都對他們做了不同的優(yōu)化，我這邊的jdk版本
  • jdk1.7.0_79
  • jdk1.8.0_40 -- 因為1.8里面HashMap做了很大的優(yōu)化

一、首先聊聊 HashMap 和 HashTable

1、出生時間：

以下內(nèi)容來自java.util.HashTable源碼注釋
@since JDK1.0

以下內(nèi)容來自java.util.HashMap源碼注釋
@since   1.2

可以看出，HashTable比HashMap要早一點(diǎn)出來（老一些）。

2、作者：

以下內(nèi)容來自java.util.HashTable源碼注釋

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

以下內(nèi)容來自java.util.HashMap源碼注釋

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

可以看到，HashMap比HashTable多一個 Doug Lea 的作者，想知道Doug Lea大神的信息，簡介如下：

--------------------來自百度百科
如果IT的歷史，是以人為主體串接起來的話，那么肯定少不了Doug Lea。這個鼻梁掛著眼鏡，留著德王威廉二世的胡子，臉上永遠(yuǎn)掛著謙遜靦腆笑容，服務(wù)于紐約州立大學(xué)Oswego分校計算機(jī)科學(xué)系的老大爺。
說他是這個世界上對Java影響力最大的個人，一點(diǎn)也不為過。因為兩次Java歷史上的大變革，他都間接或直接的扮演了舉足輕重的角色。2004年所推出的Tiger。Tiger廣納了15項JSRs(Java Specification Requests)的語法及標(biāo)準(zhǔn)，其中一項便是JSR-166。JSR-166是來自于Doug編寫的util.concurrent包。
值得一提的是: Doug Lea也是JCP (Java社區(qū)項目)中的一員。
Doug是一個無私的人，他深知分享知識和分享蘋果是不一樣的，蘋果會越分越少，而自己的知識并不會因為給了別人就減少了，知識的分享更能激蕩出不一樣的火花?！禘ffective JAVA》這本Java經(jīng)典之作的作者Joshua Bloch便在書中特別感謝Doug Lea是此書中許多構(gòu)想的共鳴板，感謝Doug Lea大方分享豐富而又寶貴的知識。

3、常規(guī)面試題：

首先，現(xiàn)在面試還在問：【HashMap和HashTable的區(qū)別】的情況比較少了，這是比較老的面試題，因為

以下內(nèi)容來自java.util.HashTable源碼注釋
 * Java Collections Framework</a>.  Unlike the new collection
 * implementations, {@code Hashtable} is synchronized.  If a
 * thread-safe implementation is not needed, it is recommended to use
 * {@link HashMap} in place of {@code Hashtable}.  If a thread-safe
 * highly-concurrent implementation is desired, then it is recommended
 * to use {@link java.util.concurrent.ConcurrentHashMap} in place of
 * {@code Hashtable}.

簡單翻譯就是說，就是 HashTable已經(jīng)淘汰了 ， 如果不需要線程安全，那么使用HashMap代替HashTable，如果你需要線程那么使用ConcurrentHashMap代替HashTable。

如果現(xiàn)在問到這塊，回答的應(yīng)該要更加全面，比如：
【版本】-->【作者】-->【繼承】-->【安全】-->【數(shù)據(jù)結(jié)構(gòu)】-->【算法】

• HashTable是jdk1.0時期出現(xiàn)的，HashMap是Jdk1.2時期出現(xiàn)的。
• HashMap比HashTable的作者多一個 DougLea大神。
• HashTable和HashMap的類繼承關(guān)系不一樣。(后續(xù)閱讀源碼分析)
• HashTable是線程安全的，HashMap是線程不安全的。（后續(xù)源碼分析）
• HashTable key和valeu都不支持Null， 而HashMap支持Null（后續(xù)分析源碼）
• HashTable和HashMap他們的哈希桶內(nèi)部實現(xiàn)，是一致的。
• HashTable和HashMap在算法上的區(qū)別是最大的：（后續(xù)源碼分析）
  • HashTable初始化大小是11，每次擴(kuò)容是原來的2n+1，如果用戶輸入大小，就會直接設(shè)定用戶輸入的大小。
  • HashMap的初始化大小是16，每次擴(kuò)容是原來的兩倍，如果用戶輸入大小，HashMap會默認(rèn)將其闊充到2的冪次。
  • HashTable的做法是盡量使用素數(shù)、奇數(shù)，這樣做，簡單的取模哈希的結(jié)果會更加平均。
  • HashMap的優(yōu)勢，在于取模計算是，如果模數(shù)是2的冪，那么我們可以直接使用位運(yùn)算來得到結(jié)果，效率要大大高于做除法。
  • 總結(jié)：HashTable取模平均更有優(yōu)勢，HashMap計算效率上更勝一籌。
• HashTable已經(jīng)淘汰了，源碼中的注釋寫到，如果不考慮線程安全的，可以使用HashMap，如果需要線程安全的，那么使用ConcurrentHashMap可以完美的替代。

這樣的回答，已經(jīng)很漂亮，當(dāng)然，還可以更好，HashTable安全是如何做到的的，HashMap為什么支持null，HashCode重復(fù)了怎么辦，這些，往后看。

4、針對上面的答復(fù)，進(jìn)行源碼分析：

4.1、HashTable和HashMap的類繼承關(guān)系不一樣

HashMap和HashTable 都是給予哈希來實現(xiàn)鍵值映射的工具類。下面是他們的繼承、實現(xiàn)的關(guān)系。

以下內(nèi)容來自java.util.HashTable源碼注釋
public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable{}

public abstract class Dictionary<K,V> {}

以下內(nèi)容來自java.util.HashMap源碼注釋
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable{}

public abstract class AbstractMap<K,V> implements Map<K,V> {}

從源碼中可以看出，他們繼承的體系又一些不同，雖然都是實現(xiàn)了Map、Cloneable、Serializable三個接口，但是HashMap繼承抽象類 AbstractMap，HashTable繼承抽象類Dictionary，這里提一下，Dictionary類是一個已經(jīng)被廢棄的類，這一點(diǎn)在注釋中有寫：

以下內(nèi)容來自java.util.Dictionary
 * <strong>NOTE: This class is obsolete.  New implementations should
 * implement the Map interface, rather than extending this class.</strong>

細(xì)節(jié)上還有一點(diǎn)，Dictionary這個類，多一個方法，elements，但是介于 Dictionary已經(jīng)廢棄了，我也就沒有在關(guān)注他了。

4.2、HashTable是線程安全的，HashMap是線程不安全的。

以下內(nèi)容來自java.util.HashTable源碼
 public synchronized V put(K key, V value) {
        // Make sure the value is not null
        .........
    }
public synchronized Enumeration<K> keys() {
        return this.<K>getEnumeration(KEYS);
    }

以下內(nèi)容來自java.util.HashMap源碼
public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

可見，HashTable 線程安全的做法，比較簡單，就是所有方法都是帶 synchronized 。

4.3、HashTable key和valeu都不支持Null， 而HashMap支持Null

以下內(nèi)容來自java.util.HashTable源碼注釋
public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) { // 這里會拋錯
            throw new NullPointerException();
        }
        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();//如果key為null，這里會報NullPointerException
        ........................
    }

以下內(nèi)容來自java.util.HashMap源碼， jdk1.7版本
  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;//Value 直接賦值，不會報錯，作為 Null 存入Map
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }
    /**
    * Offloaded version of put for null keys
    */
    private V putForNullKey(V value) {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {// 把null 作為 一個key 存在 table[0]的位子
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

通過源碼可以看出：

• HashTable valuse 為null ，直接拋 NullPointerException，如果key為null，那么后面那句，key.hashCode();會報NullPointerException。
• HashMap 當(dāng)key等于kull ，單獨(dú)包裝了一個方法，會調(diào)用putForNullKey方法，會把null作為key，放到Entry的table[0]的位置上。
• 通過這個源碼，還可以看出一點(diǎn)，如果value 為null ，并不會把key清除，而是把null存入進(jìn)去。初級程序員，會有這樣一個誤區(qū)，以為put（key,null) 進(jìn)去，就是把這條是數(shù)據(jù)清掉了，其實并沒有。

    Map map = new HashMap();
    System.out.println(map.size());
    System.out.println(map.put("a","a"));
    System.out.println(map.size());
    System.out.println(map.put("a",null));
    System.out.println(map.size());
    System.out.println(map.put("a","a"));
    System.out.println(map.size());

輸出結(jié)果：
    0
    null
    1 //size 是1 
    a
    1//size 還是1
    null
    1//size 還是1

從測試代碼可以看出，size，一直是1，map的大小并沒有發(fā)生改變。

在就是到了Jdk1.8，HashMap的變化還是有非常大的，如下：

以下內(nèi)容來自java.util.HashMap源碼 JDK1.8
   /**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
     * key.equals(k))}, then this method returns {@code v}; otherwise
     * it returns {@code null}.  (There can be at most one such mapping.)
     *
     * <p>A return value of {@code null} does not <i>necessarily</i>
     * indicate that the map contains no mapping for the key; it's also
     * possible that the map explicitly maps the key to {@code null}.
     * The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     *
     * @see #put(Object, Object)
     */
    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    /**
     * Implements Map.get and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @return the node, or null if none
     */
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }
   /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    /**
     * Implements Map.put and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

一眼看去，代碼復(fù)雜很多，簡單的說，JDK1.8對HashMap進(jìn)行了較大的優(yōu)化，底層實現(xiàn)由之前的“數(shù)組+鏈表”改為“數(shù)組+鏈表+紅黑樹”。我這里不詳細(xì)展開，有興趣的，可以看一下：https://blog.csdn.net/v123411739/article/details/78996181

4.4、HashTable和HashMap他們的哈希桶內(nèi)部實現(xiàn)，是一致的。

以下內(nèi)容來自java.util.HashTable源碼注釋
    /**
     * The hash table data.
     */
    private transient Entry<K,V>[] table; // 這個對象
    /**
     * Constructs a new, empty hashtable with the specified initial
     * capacity and the specified load factor.
     *
     * @param      initialCapacity   the initial capacity of the hashtable.
     * @param      loadFactor        the load factor of the hashtable.
     * @exception  IllegalArgumentException  if the initial capacity is less
     *             than zero, or if the load factor is nonpositive.
     */
    public Hashtable(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);

        if (initialCapacity==0)
            initialCapacity = 1;
        this.loadFactor = loadFactor;
        table = new Entry[initialCapacity];
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        initHashSeedAsNeeded(initialCapacity);
    }

以下內(nèi)容來自java.util.HashMap源碼注釋
    /**
     * An empty table instance to share when the table is not inflated.
     */
    static final Entry<?,?>[] EMPTY_TABLE = {};

    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;// 這個對象

HashMap和HashTable都是用哈希表來存儲鍵值對，在數(shù)據(jù)結(jié)構(gòu)上基本相同的，從源碼中可以看到，都是建立了一個 【transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;】，Map.Entry是一個私有內(nèi)部類，每一個Entry對象表示存儲在Hash表中的一個鍵值對。

private static class Entry<K,V> implements Map.Entry<K,V> {
      int hash;//hash鍵對象的hash值
      final K key;//key對象
      V value;//值對象
      Entry<K,V> next;//指鏈表中下一個Entry對象，可為null，表示當(dāng)前Entry對象在鏈表尾部。

可以說，有多少個鍵值對，就有多少個Entry對象，那么在HashMap和HashTable中是怎么存儲這些Entry對象，以方便我們快速查找和修改的呢？請看下圖。

image_1536219041.924343.jpg

上圖畫出的是一個桶數(shù)量為8，存有4個鍵值對的HashMap/HashTable的內(nèi)存布局情況?？梢钥吹紿ashMap/HashTable內(nèi)部創(chuàng)建有一個Entry類型的引用數(shù)組，用來表示哈希表，數(shù)組的長度，即是哈希桶的數(shù)量。而數(shù)組的每一個元素都是一個Entry引用，從Entry對象的屬性里，也可以看出其是鏈表的節(jié)點(diǎn)，每一個Entry對象內(nèi)部又含有另一個Entry對象的引用。

哈希碰撞就是上圖 【2】的位子，兩個 Entry的hash值計算出來，在同一個位子上。

這樣就可以得出結(jié)論，HashMap/HashTable內(nèi)部用Entry數(shù)組實現(xiàn)哈希表，而對于映射到同一個哈希桶（數(shù)組的同一個位置）的鍵值對，使用Entry鏈表來存儲(解決hash沖突)。

這里照顧一下新人：java 的transient關(guān)鍵字為我們提供了便利，你只需要實現(xiàn)Serilizable接口，將不需要序列化的屬性前添加關(guān)鍵字transient，序列化對象的時候，這個屬性就不會序列化到指定的目的地中。

4.5、接下來就是他們最大的區(qū)別了 ， 初始化，算法

以下內(nèi)容來自java.util.HashTable源碼注釋
 /**
     * Constructs a new, empty hashtable with a default initial capacity (11)
     * and load factor (0.75).
     */
     //初始化 11
    public Hashtable() {
        this(11, 0.75f);
    }
      /**
     * Increases the capacity of and internally reorganizes this
     * hashtable, in order to accommodate and access its entries more
     * efficiently.  This method is called automatically when the
     * number of keys in the hashtable exceeds this hashtable's capacity
     * and load factor.
     */
    protected void rehash() {
        int oldCapacity = table.length;
        Entry<K,V>[] oldMap = table;

        // overflow-conscious code 乘2+1
        int newCapacity = (oldCapacity << 1) + 1;
       。。。。。。。。。。。。。。
    }

以下內(nèi)容來自java.util.HashMap源碼注釋
    /**
     * The default initial capacity - MUST be a power of two.
     */
     //初始化1 左移4次， 2的四次方，16 
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
       /**
     * Adds a new entry with the specified key, value and hash code to
     * the specified bucket.  It is the responsibility of this
     * method to resize the table if appropriate.
     *
     * Subclass overrides this to alter the behavior of put method.
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);//每次擴(kuò)容，乘2
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

• HashTable初始化大小是11，每次擴(kuò)容是原來的2n+1，如果用戶輸入大小，就會直接設(shè)定用戶輸入的大小。

• HashMap的初始化大小是16，每次擴(kuò)容是原來的兩倍，如果用戶輸入大小，HashMap會默認(rèn)將其闊充到2的冪次。

• HashTable的做法是盡量使用素數(shù)、奇數(shù)，這樣做，簡單的取模哈希的結(jié)果會更加平均。

• HashMap的優(yōu)勢，在于取模計算是，如果模數(shù)是2的冪，那么我們可以直接使用位運(yùn)算來得到結(jié)果，效率要大大高于做除法。

以下內(nèi)容來自java.util.HashTable源碼注釋
/**
     * A randomizing value associated with this instance that is applied to
     * hash code of keys to make hash collisions harder to find.
     */
    transient int hashSeed;
    private int hash(Object k) {
        // hashSeed will be zero if alternative hashing is disabled.
        return hashSeed ^ k.hashCode();
    }

以下內(nèi)容來自java.util.HashMap源碼注釋
        int hash = hash(key);
        int i = indexFor(hash, table.length);

    // 在計算了key.hashCode()之后，做了一些位運(yùn)算來減少哈希沖突
    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);
    }
   /**
     * Returns index for hash code h.
     */
    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);
    }

正如我們所言，HashMap由于使用了2的冪次方，所以在取模運(yùn)算時不需要做除法，只需要位的與運(yùn)算就可以了。但是由于引入的hash沖突加劇問題，HashMap在調(diào)用了對象的hashCode方法之后，又做了一些位運(yùn)算在打散數(shù)據(jù)。關(guān)于這些位計算為什么可以打散數(shù)據(jù)的問題，本文不再展開了。

如果你有細(xì)心讀代碼，還可以發(fā)現(xiàn)一點(diǎn)，就是HashMap和HashTable在計算hash時都用到了一個叫hashSeed的變量。這是因為映射到同一個hash桶內(nèi)的Entry對象，是以鏈表的形式存在的，而鏈表的查詢效率比較低，所以HashMap/HashTable的效率對哈希沖突非常敏感，所以可以額外開啟一個可選hash（hashSeed），從而減少哈希沖突。因為這是兩個類相同的一點(diǎn)，所以本文不再展開了，感興趣的看這里。事實上，這個優(yōu)化在JDK 1.8中已經(jīng)去掉了，因為JDK 1.8中，映射到同一個哈希桶（數(shù)組位置）的Entry對象，使用了紅黑樹來存儲，從而大大加速了其查找效率。