转载

JDK1.8 hashMap优化

hashMap是程序员最常使用的一种数据结构，广泛用于各种需要键值对处理的场景：分组、缓存等等。hashMap的api使用非常简单，但是在使用的时候我们还是会有一些疑惑：

为什么阿里的编码规范建议在初始化hashMap时尽量传入预估需要存储的数据的数量（其实基本所有的容器初始化时都建议这么做）
为什么jdk1.8之前的hashMap在多线程环境下会死循环。当然有人会说，hashMap不是线程安全的，不能在多线程下使用，偏要用出现死循环了怪谁。但是带着这些问题，能让我们多思考，源码为什么要这么设计
在扩容的时候还需要再计算元素的hash位置吗
当然还有最基本的为什么key要复写hashCode和equals方法就不再赘述了

为什么我会强调jdk1.8，就是因为jdk1.8里面的hashMap做了一些优化，本文也会从jdk1.7和jdk1.8的区别来分析下hashMap的实现原理。

参数

hashMap采用的是数组+链表+红黑数（jdk1.8增加）的方式来存储数据。

Node<K,V>[] table;
int threshold;
float loadFactor;
int modCount;  
int size;  //map中键值对个数
复制代码

Node[]table就是最重要的存储数据的结构，很明显是一个数组链表，也叫哈希桶。很明显这个数组的大小非常关键，如何在减少hash冲突的同时，减少map所占用的内存，还要减少resize()发生。

table初始大小设定

在初始化时指定map大小，可以有效降低map扩容带来的性能损耗，查看指定map大小的代码，发现会将你指定的大小转换为一个最接近你指定的cap的2的n次方的值。为什么要这样在后面解析put源码时解释。

/**
     * Returns a power of two size for the given target capacity.
     */
    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;
    }
复制代码

threshold与loadFactor

loadFactor为负载因子，thresHold = table.length * loadFactor，也就是当size > thresHold时候，要对map进行扩容。默认值负载因子取0.75。

确定桶位置

在put和get时都要查找key值应该落在哪个hash桶里面。因为数组长度n都是2的m次方，那么与n-1进行&运算就相当于取哈希值的低m位，也就是哈希值对n取模（%），效率更高。这也就是为什么数组的长度必须为2的整数次方。

n= table.length(); //数组长度
table[h&(n-1)]     //获取首节点
复制代码

get put流程

这个相信大家已经非常熟悉

V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //初始化tab
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //如果桶位置为空，直接生成node放入即可
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //桶的链表首节点与key相同，先暂存在变量e中
            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) {
                    //没有相同的key，生成node放在链表尾部
                        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))))
                    //存在相同key的节点，还是暂存在e中
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                //!onlyIfAbsent将旧value值覆盖
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //如果size超过了负载阈值，则要扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
复制代码

扩容优化

jdk1.7之所以在多线程环境下可能导致死循环，就是在扩容的时候可能会让链表形成环路。原因是会重新计算元素在新的table里面桶的位置，而且还会将链表翻转过来。这里有很多文章详细分析了，如果产生链表环路从而造成死循环的，我也不再赘述。直接看jdk1.8是如何避免了死循环问题的。

Node<K,V>[] resize() {
        //这儿是计算newCap（变为之前两倍）和threshold的地方，有一些边界值的判断，其实很简单
        //但是占用篇幅比较大，忽略掉
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> 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<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            //只需要计算一个bit的值就能确定桶的位置
                            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;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
复制代码

if ((e.hash & oldCap) == 0)，只需要判断一个位是否为0就能确定元素在新桶的位置。