什么是HashMap腿短？

簡(jiǎn)單來(lái)說(shuō)HashMap是數(shù)組+鏈表的結(jié)合體，Jdk1.8后加入了紅黑樹(shù)称勋，數(shù)組是HashMap的主體胸哥，鏈表和紅黑樹(shù)的出現(xiàn)主要是為了解決哈希沖突。HashMap繼承于AbstractMap赡鲜，實(shí)現(xiàn)了Map空厌、Cloneable、java.io.Serializable接口银酬。

HashMap的存儲(chǔ)

HashMap是根據(jù)鍵值對(duì)來(lái)對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)嘲更，大多數(shù)情況下只需要一次定位即可，因此具有很快的訪問(wèn)速度揩瞪。HashMap中最多可以有一條記錄的鍵為null哮内，null鍵的hash值為0，允許多條記錄的值為null壮韭。
HashMap是線程不安全的北发，如果想要保證線程安全可以用Collections的synchronizedMap 方法使 HashMap 具有線程安全的能力，或者使用ConcurrentHashMap喷屋。

• 下面從源碼的角度看一下HashMap是怎么樣的存儲(chǔ)結(jié)構(gòu)

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;//當(dāng)前節(jié)點(diǎn)的hash值
        final K key;//保存節(jié)點(diǎn)的key值
        V value;//保存節(jié)點(diǎn)的value值
        Node<K,V> next;//指向下個(gè)節(jié)點(diǎn)

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }
//鏈表部分
 static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
        LinkedHashMapEntry<K,V> before, after;
        LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
//紅黑樹(shù)部分
static final class TreeNode<K,V> extends LinkedHashMap.LinkedHashMapEntry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links 存儲(chǔ)當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)
        TreeNode<K,V> left;//存儲(chǔ)當(dāng)前節(jié)點(diǎn)的做孩子節(jié)點(diǎn)
        TreeNode<K,V> right;//存儲(chǔ)當(dāng)前節(jié)點(diǎn)的右孩子節(jié)點(diǎn)
        TreeNode<K,V> prev;    // needed to unlink next upon deletion存儲(chǔ)當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
        boolean red;//存儲(chǔ)當(dāng)前節(jié)點(diǎn)的紅黑顏色
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

從以上可以很清晰地看出來(lái)HashMap是數(shù)組+鏈表+紅黑樹(shù)實(shí)現(xiàn)的琳拨。

從源碼真正的了解HashMap

• 我們先來(lái)看看HashMap提供的構(gòu)造方法有哪些？

public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

• 該方法指定初始容量以及裝載因子屯曹，常量MAXIMUM_CAPACITY = 1 << 30為HashMap的最大容量
• 這里注意到方法tableSizeFor(),這個(gè)方法返回的值是最接近initialCapacity值的2的冪狱庇，并且會(huì)把這個(gè)值存儲(chǔ)在threshold中。

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;//>>>代表無(wú)符號(hào)右移 
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

• 該方法只指定初始容量大小恶耽，DEFAULT_LOAD_FACTOR = 0.75f為HashMap默認(rèn)的裝載因子密任，當(dāng)HashMap中的元素?cái)?shù)量超過(guò)容量*0.75的時(shí)候，要進(jìn)行resize()操作偷俭，也就是HashMap的擴(kuò)容浪讳。

public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

• 該方法所有參數(shù)均用默認(rèn)值。

public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

• 該方法傳進(jìn)來(lái)一個(gè)Map來(lái)創(chuàng)建涌萤，在下面介紹淹遵。

HashMap 的put方法

在看put方法前口猜，先了解一下HashMap中定義的各種變量的作用

static final int TREEIFY_THRESHOLD = 8;

• hash 沖突的鏈表向紅黑樹(shù)轉(zhuǎn)變的臨界值

static final int UNTREEIFY_THRESHOLD = 6;

• hash 沖突的紅黑樹(shù)轉(zhuǎn)變?yōu)殒湵淼呐R界值

static final int MIN_TREEIFY_CAPACITY = 64;

• 當(dāng)需要將鏈表轉(zhuǎn)為紅黑樹(shù)時(shí)，需要判斷當(dāng)前數(shù)組的容量透揣，如果當(dāng)前的容量小于MIN_TREEIFY_CAPACITY济炎，則要進(jìn)行擴(kuò)容操作，不進(jìn)行轉(zhuǎn)變操作辐真。

transient Node<K,V>[] table;

• 保存節(jié)點(diǎn)的數(shù)組

transient Set<Map.Entry<K,V>> entrySet;

• 由Node<K,V>構(gòu)成的Set

transient int size;

• 存儲(chǔ)數(shù)據(jù)的數(shù)量

transient int modCount;

• hashMap 發(fā)生結(jié)構(gòu)性變化的次數(shù)（注意　value 的覆蓋不屬于結(jié)構(gòu)性變化）

int threshold;

• hreshold的值等于 table.length * loadFactor, size 超過(guò)這個(gè)值時(shí)進(jìn)行　resize()擴(kuò)容操作

final float loadFactor;

• 裝載因子

HashMap的put方法

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
public void putAll(Map<? extends K, ? extends V> m) {
        putMapEntries(m, true);
    }

• put實(shí)際調(diào)用為putVal()方法须尚，這里看到hash值的計(jì)算是通過(guò)hash(key)方法。如下：

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

• 可以看到hash值的計(jì)算是通過(guò)hashCode()的高16位異或低16位實(shí)現(xiàn)的侍咱。
• putAll方法實(shí)際調(diào)用為putMapEntries(m, true);恨闪，如下：

 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            //在構(gòu)造方法中調(diào)用時(shí)table一定為null
            if (table == null) { // pre-size
                //根據(jù)傳入的map的大小計(jì)算要?jiǎng)?chuàng)建的hashMap的大小。
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                    threshold = tableSizeFor(t);//把創(chuàng)建的hashmap 的大小存起來(lái)
            }
            else if (s > threshold)//如果傳進(jìn)來(lái)的map的大小大于當(dāng)前大小要先進(jìn)行擴(kuò)容
                resize();
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                //擴(kuò)容之后將數(shù)據(jù)進(jìn)行插入放坏。
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

• evict值為false代表在創(chuàng)建的時(shí)候調(diào)用了這個(gè)函數(shù)咙咽，也就是上面提到過(guò)得第四個(gè)構(gòu)造函數(shù)，為true表示HashMap已經(jīng)被創(chuàng)建好了之后才進(jìn)行調(diào)用淤年，也就是putAll方法的調(diào)用钧敞。
• 可以看到最終調(diào)用的也是putVal(hash(key), key, value, false, evict)

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;
        //確定在數(shù)組中的插入位置，位置計(jì)算通過(guò)(n - 1) & hash麸粮，也就是hash%n來(lái)得到溉苛，如果沒(méi)有元素則直接插入
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //如果存在元素則比較待插入元素的hash值和key值
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
              //如果元素是紅黑樹(shù)節(jié)點(diǎn)則通過(guò)putTreeVal插入
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
              //這里說(shuō)明是鏈表部分，找到合適的位置然后進(jìn)行插入
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                         //找到位置弄诲，插入
                        p.next = newNode(hash, key, value, null);
                        //插入后的節(jié)點(diǎn)數(shù)如果大于TREEIFY_THRESHOLD - 1則要轉(zhuǎn)變?yōu)榧t黑樹(shù)
                        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 該元素已經(jīng)存在愚战，覆蓋value
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;//記錄變化次數(shù)
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

• 接下來(lái)看putTreeVal(this, tab, hash, key, value);方法：

  final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                       int h, K k, V v) {
            Class<?> kc = null;
            boolean searched = false;
            TreeNode<K,V> root = (parent != null) ? root() : this;
            //從根節(jié)點(diǎn)開(kāi)始遍歷找到合適的位置
            for (TreeNode<K,V> p = root;;) {
                int dir, ph; K pk;
                if ((ph = p.hash) > h)
                    dir = -1;//dir小于０，接下來(lái)查找當(dāng)前節(jié)點(diǎn)左孩子
                else if (ph < h)
                    dir = 1;//dir大于０齐遵，接下來(lái)查找當(dāng)前節(jié)點(diǎn)右孩子
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))//hash值相同并且key相同
                    return p;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0) {
                      //至此代表當(dāng)前節(jié)點(diǎn)與待插入節(jié)點(diǎn)key不同寂玲，hash值相同
                      //k并未實(shí)現(xiàn)comparable<K>接口或者k的compareTo方法錯(cuò)誤
                    if (!searched) {
                    //在以當(dāng)前節(jié)點(diǎn)為根的整個(gè)樹(shù)進(jìn)行一次遍歷，看是否存在待插入節(jié)點(diǎn)
                        TreeNode<K,V> q, ch;
                        searched = true;
                        if (((ch = p.left) != null &&
                             (q = ch.find(h, k, kc)) != null) ||
                            ((ch = p.right) != null &&
                             (q = ch.find(h, k, kc)) != null))
                            return q;
                    }
                    //通過(guò)另一種方式比較k
                    dir = tieBreakOrder(k, pk);
                }

                TreeNode<K,V> xp = p;
              //插入節(jié)點(diǎn)
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    Node<K,V> xpn = xp.next;
                    TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    xp.next = x;
                    x.parent = x.prev = xp;
                    if (xpn != null)
                        ((TreeNode<K,V>)xpn).prev = x;
                    //平衡二叉樹(shù)
                    moveRootToFront(tab, balanceInsertion(root, x));
                    return null;
                }
            }
        }

static int tieBreakOrder(Object a, Object b) {
            int d;
            if (a == null || b == null ||
                (d = a.getClass().getName().
                 compareTo(b.getClass().getName())) == 0)
                d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
                     -1 : 1);
            return d;
        }

• 通過(guò)比較內(nèi)存地址去比較

HashMap 的get方法

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

• get方法比較簡(jiǎn)單梗摇，就是通過(guò)輸入節(jié)點(diǎn)的hash值和key值利用getNode方法去進(jìn)行查找拓哟。

 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)//若定位到的節(jié)點(diǎn)是　TreeNode 節(jié)點(diǎn)，則在樹(shù)中進(jìn)行查
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {//在鏈表中進(jìn)行查找
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

final TreeNode<K,V> getTreeNode(int h, Object k) {
            return ((parent != null) ? root() : this).find(h, k, null);
        }

• getTreeNode方法從根節(jié)點(diǎn)開(kāi)始調(diào)用find方法進(jìn)行查找伶授。

final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
            TreeNode<K,V> p = this;
            do {
                int ph, dir; K pk;
                TreeNode<K,V> pl = p.left, pr = p.right, q;
                if ((ph = p.hash) > h)
                    p = pl;
                else if (ph < h)
                    p = pr;
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;
                else if (pl == null)
                    p = pr;
                else if (pr == null)
                    p = pl;
                else if ((kc != null ||
                          (kc = comparableClassFor(k)) != null) &&
                         (dir = compareComparables(kc, k, pk)) != 0)
                    p = (dir < 0) ? pl : pr;
                else if ((q = pr.find(h, k, kc)) != null)
                    return q;
                else
                    p = pl;
            } while (p != null);
            return null;
        }

• 首先進(jìn)行hash值的比較断序，如果不同，讓當(dāng)前節(jié)點(diǎn)變?yōu)樽蠛⒆踊蛴液⒆?/li>
• 若hash相同糜烹，進(jìn)行key值的比較违诗。
• 若hash值相同，key值不同疮蹦，并且k是不可以比較的诸迟，則要在整棵樹(shù)中進(jìn)行查找，先找右子樹(shù)再找左子樹(shù)。

HashMap的擴(kuò)容

首先我們?cè)跀U(kuò)容的時(shí)候亮蒋，一般會(huì)把長(zhǎng)度擴(kuò)為原來(lái)的2倍，所以妆毕，元素有可能保持在原位慎玖，或者移動(dòng)2次冪的位置，也就是原來(lái)的hash值會(huì)新增一個(gè)bit笛粘，是0的話代表保持原位趁怔，1的話代表索引發(fā)生改變，這時(shí)的索引變?yōu)?code>元索引+oldCap薪前。

下面具體看一下源碼是什么樣的润努。

 final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        //oldCap為原table的大小
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //oldThr為oldCap*load_factor
        int oldThr = threshold;
        int newCap, newThr = 0;
        //resize()實(shí)在size>threshold的時(shí)候被調(diào)用。
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        //下面是在table為空的時(shí)候被調(diào)用示括，oldCap小于等于0并且oldThr大于0铺浇，
        //表示用戶使用的帶參構(gòu)造函數(shù)創(chuàng)建的hashMap，
        //導(dǎo)致oldTab為null垛膝，oldCap為0,oldThr不為0
        
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        //oldCap 小于等于 0 且 oldThr 等于0鳍侣，
        //用戶調(diào)用 HashMap()構(gòu)造函數(shù)創(chuàng)建的　HashMap，所有值均采用默認(rèn)值吼拥，
       　//oldTab（Table）表為空倚聚，oldCap為0，oldThr等于0凿可，
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
        //把　oldTab 中的節(jié)點(diǎn)　reHash 到　newTab 中去
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                    //若節(jié)點(diǎn)是單個(gè)節(jié)點(diǎn)惑折，直接在 newTab中進(jìn)行重定位
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                    //若節(jié)點(diǎn)是　TreeNode 節(jié)點(diǎn)，要進(jìn)行 紅黑樹(shù)的 rehash　操作
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                            //若是鏈表枯跑，進(jìn)行鏈表的 rehash操作
                            //loHead惨驶，下標(biāo)不變情況下的鏈表頭
                            //loTail，下標(biāo)不變情況下的鏈表尾
                            //hiHead敛助，下標(biāo)改變情況下的鏈表頭
                            //hiTail敞咧，下標(biāo)改變情況下的鏈表尾
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            //根據(jù)算法e.hash & oldCap判斷節(jié)點(diǎn)位置rehash后是否發(fā)生改變
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            // rehash后節(jié)點(diǎn)新的位置一定為原來(lái)基礎(chǔ)上加上　oldCap
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

• 可以看到紅黑樹(shù)的rehash操作是通過(guò)(TreeNode<K,V>)e).split(this, newTab, j, oldCap);這個(gè)方法進(jìn)行的.

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
            TreeNode<K,V> b = this;
            // Relink into lo and hi lists, preserving order
            TreeNode<K,V> loHead = null, loTail = null;
            TreeNode<K,V> hiHead = null, hiTail = null;
            int lc = 0, hc = 0;
            //由于TreeNode節(jié)點(diǎn)之間存在雙端鏈表的關(guān)系，可以利用鏈表關(guān)系進(jìn)行rehash
            for (TreeNode<K,V> e = b, next; e != null; e = next) {
                next = (TreeNode<K,V>)e.next;
                e.next = null;
                if ((e.hash & bit) == 0) {
                    if ((e.prev = loTail) == null)
                        loHead = e;
                    else
                        loTail.next = e;
                    loTail = e;
                    ++lc;
                }
                else {
                    if ((e.prev = hiTail) == null)
                        hiHead = e;
                    else
                        hiTail.next = e;
                    hiTail = e;
                    ++hc;
                }
            }
            //rehash 操作之后注意對(duì)根據(jù)鏈表長(zhǎng)度進(jìn)行untreeify或treeify操作
            if (loHead != null) {
                if (lc <= UNTREEIFY_THRESHOLD)
                    tab[index] = loHead.untreeify(map);
                else {
                    tab[index] = loHead;
                    if (hiHead != null) // (else is already treeified)
                        loHead.treeify(tab);
                }
            }
            if (hiHead != null) {
                if (hc <= UNTREEIFY_THRESHOLD)
                    tab[index + bit] = hiHead.untreeify(map);
                else {
                    tab[index + bit] = hiHead;
                    if (loHead != null)
                        hiHead.treeify(tab);
                }
            }
        }

HashMap辜腺，ConcurrentHashMap休建，HashTable的區(qū)別

• HashTable底層數(shù)組+鏈表實(shí)現(xiàn)，無(wú)論key還是value都不能為null评疗，線程安全测砂，實(shí)現(xiàn)線程安全的方式是在修改數(shù)據(jù)時(shí)鎖住整個(gè)HashTable，效率低百匆，ConcurrentHashMap做了相關(guān)優(yōu)化.HashTable初始size為11砌些，擴(kuò)容：newsize = olesize*2+1,計(jì)算index的方法：index = (hash & 0x7FFFFFFF) % tab.length
• ConcurrentHashMap線程安全，而hashMap是線程不安全的。
• ConcurrentHashMap在jdk1.7時(shí)通過(guò)把整個(gè)Map分為N個(gè)Segment存璃，可以提供相同的線程安全仑荐，但是效率提升N倍，默認(rèn)提升16倍纵东。(讀操作不加鎖粘招，由于HashEntry的value變量是 volatile的，也能保證讀取到最新的值偎球。)洒扎。jdk1.8中去掉了Segment這種數(shù)據(jù)結(jié)構(gòu)，使用synchronized來(lái)進(jìn)行同步鎖粒度降低衰絮，所以不需要分段鎖的概念袍冷，實(shí)現(xiàn)的復(fù)雜度也增加了
• Hashtable的synchronized是針對(duì)整張Hash表的，即每次鎖住整張表讓線程獨(dú)占猫牡，ConcurrentHashMap允許多個(gè)修改操作并發(fā)進(jìn)行.
• ConcurrentHashMap擴(kuò)容：段內(nèi)擴(kuò)容（段內(nèi)元素超過(guò)該段對(duì)應(yīng)Entry數(shù)組長(zhǎng)度的75%觸發(fā)擴(kuò)容胡诗，不會(huì)對(duì)整個(gè)Map進(jìn)行擴(kuò)容），插入前檢測(cè)需不需要擴(kuò)容淌友，有效避免無(wú)效擴(kuò)容乃戈。
• hashMap擴(kuò)容針對(duì)整個(gè)Map，每次擴(kuò)容時(shí)亩进，原來(lái)數(shù)組中的元素依次重新計(jì)算存放位置症虑，并重新插入插入元素后才判斷該不該擴(kuò)容，有可能無(wú)效擴(kuò)容（插入后如果擴(kuò)容归薛，如果沒(méi)有再次插入谍憔，就會(huì)產(chǎn)生無(wú)效擴(kuò)容）
• Hashtable和HashMap都實(shí)現(xiàn)了Map接口，但是Hashtable的實(shí)現(xiàn)是基于Dictionary抽象類的主籍。Java5提供了ConcurrentHashMap习贫，它是HashTable的替代，比HashTable的擴(kuò)展性更好千元。