HashMap在JDK1.7和1.8的区别（附带ConcurrentHashMap，个人理解向）

前言：本文只是总结，具体实现需要结合源码理解（Talk is cheap,show me the code），本问题旨在探讨跟着JDK的迭代，理解设计者的思维模式，思考为什么这么设计

一、HashMap在JDK1.8里的优化

 先放一张大佬总结的图，根据源码去理解里面的区别

1.初始化操作集成在reSize里面（1.7中单独方法inflateTable）tips：不明觉厉，少一个方法会提高效率吗？

//JDK1.7
private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}
//DK1.8在后面resize方法可以找到

2.通过构造函数指定容量时计算capacity时使用五次|=运算、五次位运算、一次加法和一次减法，使自最高位起每一位都为1然后再加1得到不小于cap的2的幂数的效果（1.7调用Integer.highestOneBit()取最高位后再做一次左移，总计使用五次|=运算、七次位运算和两次减法）

tips：就是把原先直接调用Integer.highestOneBit()里多余的两次位运算省略了，其实没优化多少，加减运算和位运算效率相当，乘除运算比位运算慢几十倍

//JDK1.7

private static int roundUpToPowerOf2(int number) {
    // assert number >= 0 : "number must be non-negative";
    return number >= MAXIMUM_CAPACITY
            ? MAXIMUM_CAPACITY
            : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

public static int highestOneBit(int i) {
    // HD, Figure 3-1
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    return i - (i >>> 1);
}

//JDK1.8
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

3.扰动处理1次位运算，1次异或（1.7使用4次位运算，5次异或）tips：不明觉厉

//JDK1.7
final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }
    h ^= k.hashCode();
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

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

4.插入时采用尾插法，避免了并发扩容情况下罕见的循环链表，但不能避免并发扩容时数据覆盖（头插法效率高但是会倒置链表，尾插法按插入顺序维护但是效率低每次插入需要遍历）

tips：其实链表插入快的优点HashMap并没有发挥到，因为put时总要遍历一遍key，链表遍历又非常慢，但是扩容后转移数据时就有插入快慢的效率问题了，因为尾插法于是设计者在扩容转移数据做了第6点的优化

//JDK1.7

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {

    Entry e = table[bucketIndex];
　　//新建的Entry指向e，即头插法
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

Entry(int h, K k, V v, Entry n) {
    value = v;
    next = n;
    key = k;
    hash = h;
}

//DK1.8在后面putVal方法可以找到

5.先插入再扩容，扩容后进行统一transfer操作（1.7先扩容后插入）

tips：1.7只需要判断key是否相等，头插法效率高不需要遍历，可以在插入前判断是否需要扩容，1.8采用尾插法也需要遍历于是和key值判等写在一起，同时计算插入后节点数量达到树化个数（也可能扩容不树化）

//JDK1.7

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

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

//JDK1.8
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    ……
　　//头结点判空
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node e; K k;
　　　　　//key值判等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
　　　　　//是否为树节点
        else if (p instanceof TreeNode)
            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
        else {
　　　　　　　//结点不为空，key值和头结点key不相等，不为树节点则开始遍历
            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;
            }
        }
    ……
    }
    ++modCount;
    ……
    return null;
}

6.扩容transfer时，只考虑高位bit，高位为0则保持在原索引位置，为1则偏移+原capacity，巧用&运算，前提是capacity为2的幂数（1.7采用重新遍历，1.8如果采用遍历的话，哈希冲突时效率很低，尾插法需要遍历链表，头插法则不需要）

tips：高低位巧用&运算的前提是hash&(n-1)等价于对hash mod n，即n为2的幂数

//JDK1.7

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry e : table) {
        while(null != e) {
            Entry next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
　　　　　　　//头插法
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

//JDK1.8

final Node[] resize() {
    ……
　　
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node e;
　　　　　　　//头结点不为空
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
　　　　　　　　　　//尾部为空则插入尾部
                if (e.next == null) 
                    newTab[e.hash & (newCap - 1)] = e;
　　　　　　　　　　//如果是树结点则分裂为两个树，和链表的高低位分批插入
                else if (e instanceof TreeNode)
                    ((TreeNode)e).split(this, newTab, j, oldCap);
                else { // preserve order 尾插法保持顺序不变
　　　　　　　　　　　　//lo即LowBit低位，hi即HignBit高位，四个变量分别为高低位的头和尾

                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node next;
                    do {
                        next = e.next;
　　　　　　　　　　　　　　//定位到index的算法为hash&(capacity-1))，而capacity为2的幂数，以16为例，扩容后为32，那么任何数和01111(16-1)相&的结果和11111(32-1)只有最高位不同

　　　　　　　　　　　　　　//与10000（16）相&得0，则扩容后index不变，在这里用loHead和loTail表示这组链表
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
　　　　　　　　　　　　　　//与10000（16）相&得1，则扩容后index偏移16(capacity)，在这里用hiHead和hiTail表示这组链表

                        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;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

7.结构上加了红黑树，链表长度为8且数组长度大于等于64时树化，数组长度不足时扩容（红黑树查找效率高，但是占用空间多，结点为链表结点的2倍）

tips：不明觉厉

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node[] tab; Node 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 e; K k;
        //头结点key值相等，替换
　　　　 if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
　　　　 //树结点
        else if (p instanceof TreeNode)
            e = ((TreeNode)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
　　　　　　　　　　　　　　　//链表结点数大于8时，树化（treeifyBin里还要判断）

                        treeifyBin(tab, hash);
                    break;
                }
　　　　　　　　　　//遍历时发现key值相等，替换
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
 　　 ……
    return null;
}

final void treeifyBin(Node[] tab, int hash) {
    int n, index; Node e;
　　 //数组长度小于64时，选择扩容而不树化
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode hd = null, tl = null;
        do {
            TreeNode p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

二、ConcurrentHashMap

　　1.JDK1.7中的实现为Segment+HashEntry数组，Segment本身继承自ReentantLock，是ConcurrentHashMap线程安全的保证，锁的粒度为一个Segment。第一次hash定位到Segment，第二次hash定位到hashEntry的index。

重哈希时也只是对Segment里的HashEntry进行重哈希。

　　2.JDK1.8中的实现和HashMap相同为Node数组。线程安全方面则完全摒弃了1.7中的实现方案，新实现为Synchronized+CAS，锁的粒度为每个Node节点。