你真的懂Java8的HashMap么？

HashMap是一个由数组加链表（红黑树）组成的散列表，可以非常方便的存储KV数据，也可以插入K为null的信息，那么HashMap有哪些不足之处需要注意的呢？HashMap的扩容机制又是如何；常见的put、get方法工作细节又是如何，带着这一系列问题来学习一下JDK1.8里面的HashMap的源码，了解其工作原理。

HashMap 构造函数
HashMap get方法
HashMap put方法
HashMap resize方法
HashMap remove方法
HashMap 迭代器iterator
问题&总结
什么时候会创建table数组?
table数组长度可以为任意数字么？
为什么table数组长度必须为2^n?
为什么默认的负载因子0.75f？
有什么缺点么？

先了解下HashMap中的几个比较关键的成员变量，后续关于get和put的方法的细节都脱离不了这几个参数的配合

// 默认的HashMap table 数组大小 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 数组最大值，2^30 
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认的负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 链表转换为红黑树的节点最小个数（当链表长度大于等于8时会从链表转变为红黑树）
static final int TREEIFY_THRESHOLD = 8;

// 红黑树经过remove后节点个数小于等于该值时 从红黑树蜕变为链表
static final int UNTREEIFY_THRESHOLD = 6;

// HashMap的数组，是Node类型的，初始值为null
transient Node<K,V>[] table;

// 在迭代器中使用，可依次遍历Hashmap的节点
transient Set<Map.Entry<K,V>> entrySet;

// HashMap的节点个数
transient int size;

// HashMap的修改次数，主要用在fail-fast中
transient int modCount;

// HashMap阀值，当size超过阀值时进行扩容操作，一般情况下阀值 = 数组的长度 * 负载因子
int threshold;

// 负载因子，默认是0.75f，可以认为是限制HashMap的碰撞因子
final float loadFactor;

HashMap 构造函数

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);
    // 这里有个比较重要的方法tableSizeFor
}

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
    // 同样是传入了自定义的容量大小以及默认负载因子
}

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; 
    // 所有的信息都是默认的，加载因子设置为0.75f
}

这有个疑问，initialCapacity 参数一般是当做HashMap的初始化大小使用，可是细看代码得之并没有设置成table的初始长度，反而是通过tableSizeFor方法计算table默认的阀值threshold的值

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;
}

>>> 含义是无符号的右移，那么这整个函数的作用是什么呢？现在假设n对应的二进制是1XXX XXXX

右移动1位，则有01XX XXXX,进行一次异或运算 得到 11XX XXXX
再移动2位，则有0011 11XX,进行一次异或运算 得到 1111 11XX
再移动4位，则有0000 1111,进行一次异或运算 得到 1111 1111

现在看下经过了1，2，4三个运算，就相当于把当前已知最大的1右边的1 + 2 + 4位全部改成了1，变成了最大值
所以现在这几次异或运算就是把当前二进制位最大的1右边的0全部改成1(因为移动了1 + 2 + 4 + 8 + 16 = 31位)，现在计算出来的n就是0000 0000 0001 1111这种格式的数据，再进行加一操作也就成为了 0010 0000（是个偶数），现在假设传入了的cap=12，那么就是1100，经过异或运算就变成了1111，再+1处理就成为了 0001 0000，也就是16。所以现在知道了其实这个方法就是为了计算出比传入数据大且最接近的2^n的数组

那么还有一个问题，为什么一开始减1呢？其实是为了处理当cap=0的情况，当cap=0时，计算的数据为1，同样满足1 = 2^0且大于0的结论

所以如果传入了initialCapacity，threshold阀值一定会是2^n这种数据的
调用HashMap()方法，则阀值和容量都是0
调用HashMap(initialCapacity) 方法，则赋值阀值，容量为0
当然这里还是没有解释上面的一个疑问「table的长度到底是多少」，继续往下看

HashMap get方法

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    // 隐含了当key为null的时候返回0这种情况
    // 剩下的都是hash的高16位和低16位进行异或运算，其原因也是为了降低hash冲突
}

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

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) {
        // 如果tab不为null，而且长度>0，再甚至数组偏移量的节点first不为null
        // 偏移量是通过(tab.length - 1)&hash计算出来的
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            // 当前first节点如果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;
                    // 依次遍历，计算hash值一样，且Key一样的节点
            } while ((e = e.next) != null);
        }
    }
    return null;
}

需要关注一下，在定位数组的偏移量是采用了(tab.length - 1)&hash计算的,因为tab.length = 2^n，那么一定可以确保偏移量在数组之内

HashMap put方法

public V put(K key, V value) {
    // 先计算hash值，然后调用putVal方法
    return putVal(hash(key), key, value, false, true);
}

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)
        // 如果table为null或者table长度为0，需要进行重置table操作（后面再说resize方法）
        // 初始化时，table为null，也是一种Lazy的思想
        n = (tab = resize()).length;
        
    // 现在table是有一定长度的数组，而且长度为2^n
    // 定位数字的索引 (n-1) & hash 
    // 01111 1111 和hash值的和运算
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 数组上节点为null，表示没有数据，直接创建一个新节点设置好就可以了
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 此时节点p是数组有值的节点，也可以是链表(红黑树)的首节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // hash值一样，key值也一样，那就相当于发现了K一样的情况
            e = p;
        else if (p instanceof TreeNode)
            // p节点是树节点的类型，添加到红黑树中去
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                // 遍历链表的节点
                if ((e = p.next) == null) {
                    // 遍历到最后一个节点了，肯定为null
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 记住binCount是从0开始计数的，所以这里是TREEIFY_THRESHOLD - 1 = 7
                        //  当链表节点数目大于等于8，则会转变成红黑树
                        treeifyBin(tab, hash);
                    break;
                    // 链表执行完了肯定就退出循环
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 链表遍历中发现了同样的K值节点
                    break;
                p = e;
                // 否则继续遍历
            }
        }
        if (e != null) { 
            // 如果找到了同样的K的节点信息
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
               // 替换老的Value信息
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
            // 返回旧的Value信息
        }
    }
    // 到这里来的都算需要往Map中添加新节点的
    // 所以modCount + 1操作
    ++modCount;
    if (++size > threshold)
        // HashMap的节点大小个数超过了阀值，调用resize
        resize();
    afterNodeInsertion(evict);
    // 新增节点，肯定就没有旧节点信息，返回null完事
    return null;
}

整个流程只是需要注意resize()方法，当table还未初始化和当前的HashMap节点数超过阀值时就会调用resize进行扩容操作，那么现在就来看下resize方法

HashMap resize方法

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 在初次调用put时，table就是null，设定oldCap = 0，否则就是旧table的长度
    int oldThr = threshold;
    // 旧阀值oldThr
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // 如果老的table长度大于0
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 如果数组长度大于等于容量最大值，只会修改阀值大小，不进行扩容操作
            // 即使发生碰撞情况也不再考虑
            // 换句话说，在Map装入了如此多的数据也不太合理吧
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
                 // 新的table容量翻倍处理
                // 如果oldCap * 2 小于最大容量 而且 oldCap 超过默认16个容量大小，新的阀值也会翻倍
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
       // 调用了HashMap(int, float) 的构造方法的初始情况
        // 旧table的长度为0 且 旧阀值大于0（可以理解为初始情况）
        // 而且新阀值这个时候依旧等于0，无变化
        // 注意这点！新的table长度是旧的阀值，而之前已经说了阀值数据是2^n，直接赋值给了table
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // 调用了HashMap()的构造方法的初始情况
        newCap = DEFAULT_INITIAL_CAPACITY;
        // 新的默认table长度是16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        // 新的阀值 = 16 * 0.75，这里才是之前一直所说的阀值=0.75的容量情况
    }
    
    // 新的阀值为0，只有oldThr > 0 这一种情况下才有可能
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
        // 对阀值进行重新计算操作
    }
    threshold = newThr;
     // 所以才有了常说的 阀值 = 0.75 * table长度
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // 新创建了一个新容量的newTab，接下来就是开始拷贝搬迁旧table的数据了
    table = newTab;
    if (oldTab != null) {
        // 旧table有过值的情况下，依次开始遍历操作
        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
                    // 开始处理链表了，此时e节点还未处理
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            // 按照和运算 是否为0进行拆分
                            if (loTail == null)
                                // 当前e节点赋值给loHead
                                loHead = e;
                            else
                                loTail.next = e;
                            // loTail也赋值给了e节点
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 经过上面的while循环处理，就是相当于把节点hash是否为0拆分为2种情况
                    // 各自由一个链表负责，采用的尾插法
                    if (loTail != null) {
                        // 和运算为0的情况，直接挂载在原偏移量节点下
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                       // 否则，挂载在j + oldCap 的节点下
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                } 
            }
        }
    }
    return newTab;
}

resize方法整体而言还是比较复杂的，涉及到了的调用场景有无参构造、有参构造、正常扩容等三种情况，所以也就有了开头比较复杂的新容量大小以及新阀值的计算行为。

无参构造：新容量是默认容量值16，新阀值是默认容量值16 * 负载因子0.75 = 12
有参构造：新容量是由传入的initialCapacity数据计算出大且最近的2^n的值，新阀值是新容量 * 0.75（如果新容量值或者新阀值超过了 最大的容量值，修正新阀值为Integer.MAX_VALUE）
正常扩容：旧容量大于等于最大容量值，设置新阀值为Integer.MAX_VALUE，结束扩容；否则新容量double操作（有一些信息被忽略了）

再来细说一下e.hash & oldCap) == 0这个判断逻辑，我们知道table的数组偏移量的计算是通过hash & (oldCap-1)得到的，既然是在同一个链表中，则其结果是相同的，又因为oldCap = 2^n，所以意味着不同的节点Node1和Node2 的hash值必然存在着后几位为1的bit一定相等的情况（和此处逻辑无关紧要），例如如下结果做和运算

Node1 0101  1010
Node2 0001  1010
len-1 0000  1111
table 0001  0000

这两个节点后四位一定会相同的，所以也就是看table二进制为1的那1bit和节点相对应的那1bit的和运算是否为0进行拆分，这样可尽可能进行均等拆分，降低hash冲突，提高效率。

HashMap remove方法

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
    // 找到了待移除的节点e，返回其value，否则返回null
}

final Node<K,V> removeNode(int hash, Object key, Object value,
      boolean matchValue, boolean movable) {
    // matchValue 为true时会比对找到的节点和传入的Value 值
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 上面就不再细说了，就是找到待移除的节点node
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // 如果node节点不为null 而且
            // 1、无需匹配Value 值
            // 2、需要匹配且value值确实相同
            // 上述1 和 2 是或的关系
            if (node instanceof TreeNode)
               // 树节点的移除方法
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                // node和p相同就意味着node节点是table上的，直接把node的next赋值给table即可
                tab[index] = node.next;
            else
                // p节点是node节点的前节点
                // 直接把node的next赋值给p的next节点 
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            // hashmap的修改次数+1，size减一操作，然后返回node节点
            return node;
        }
    }
    return null;
}

这里有个小点需要注意到在链表的首节点(也是table上)和链表中的节点移除逻辑是不一样的，链表中需要知道其移除节点的上一个节点，而首节点则没有上一个节点这种说法，直接把下一个节点赋值给table就行了

HashMap 迭代器iterator

HashMap在遍历输出时，经常使用到迭代器Iterator，常见的代码如下

在JDK1.8中有一个forEach(BiConsumer<? super K, ? super V> action)也可以很方便的处理HashMap

Map<String, String> map = new HashMap<>();

map.put("1111", "2222");
map.put("2222", "44444");
map.put("3333", "66666");

Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry entry = iterator.next();
    System.out.print("key:" + entry.getKey() + ", value: " + entry.getValue());
}

获取EntrySet迭代器，然后利用hasNext以及next方法获取具体的值，代码很简单，看看HashMap如何实现其步骤的

public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
    // 没做什么只是直接创建了一个新的EntrySet对象
}

final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public final int size()                 { return size; }
    public final void clear()               { HashMap.this.clear(); }
    public final Iterator<Map.Entry<K,V>> iterator() {
        // 调用EntrySet的iterator也是啥都没做，返回了一个EntryIterator新对象，使用的是无参构造
        return new EntryIterator();
    }
    .....
}

那现在来看看EntryIterator类到底干了什么

// Hash迭代器抽象类
abstract class HashIterator {
    Node<K,V> next;        // next entry to return
    Node<K,V> current;     // current entry
    int expectedModCount;  // for fast-fail
    int index;             // current slot

    HashIterator() {
        expectedModCount = modCount;
        // 记录下了当前的修改次数，用于快速失败
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { 
            // 空转，从数组的第一个开始遍历，直到节点不为null为止，记录下index和next
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }

    public final boolean hasNext() {
        // 就是看下一个节点next是否为null
        return next != null;
    }

    final Node<K,V> nextNode() {
        Node<K,V>[] t;
        Node<K,V> e = next;
        if (modCount != expectedModCount)
            // 在迭代期间hashmap经历了修改操作，直接抛出异常
            throw new ConcurrentModificationException();
        if (e == null)
            // 意味着必须先调用hasNext，通过后才可调用nextNode
            throw new NoSuchElementException();
        if ((next = (current = e).next) == null && (t = table) != null) {
            // 把当前处理的节点赋值给current，开始遍历链表
            // 直到链表的下一个节点为null时（也就意味着链表遍历完成），需要进入到下一个table节点遍历
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }

    public final void remove() {
        Node<K,V> p = current;
        if (p == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        current = null;
        K key = p.key;
        removeNode(hash(key), key, null, false, false);
        // 移除节点信息，同时赋值新的修改次数给expectedModCount
        // 也就意味着如果想在迭代中移除节点，只能通过remove方法
        expectedModCount = modCount;
    }
}

final class EntryIterator extends HashIterator
    implements Iterator<Map.Entry<K,V>> {
    // 继承了HashIterator 实现了迭代器的接口
    public final Map.Entry<K,V> next() { return nextNode(); }
}

整个的迭代过程也是很清晰的，先预处理遍历table找到第一个不为null的节点，后面遍历该节点的next值，直到为null也就意味着该节点的链表(红黑树)遍历完成，继续遍历table下一个节点。

问题&总结

什么时候会创建table数组？

HashMap使用的Lazy模式，初始化时不会创建table，而是直到put数据时才会创建table数组

table数组长度可以为任意数字么？

不可以，通过tableSizeFor方法，一定会修正使得table的length为2^n，所以new HashMap(12) 和new HashMap(13)其实是一样的含义，最后length都会被修正为16
建议给新建的HashMap赋予一定的初始值，减少不必要的扩容操作，损耗性能

为什么默认的负载因子0.75f？

这个点在HashMap的源码描述中已经介绍了，hash的值是遵循泊松分布，当负载因子为0.75时，碰撞出现链表长度大于等于8个情况概率小于1/1kw，也恰好说明了为什么链表转为红黑树的节点个数为8，当真正出现红黑树也说明了hash碰撞比较严重，所以使用红黑树提高效率
至于为什么是泊松分布就涉及到概率统计学了，可以翻翻相关的paper，看看计算机理论知识大佬的说法吧，附上Stack Overflow的讨论帖子==>https://stackoverflow.com/questions/10901752/what-is-the-significance-of-load-factor-in-hashmap
这个0.75也无绝对，只是针对大部分场景比较适用，也是对空间和时间的一种妥协，如果你能严格证明0.8甚至0.9可以提高自身业务的效率，也是可以传入自定义的负载因子

为什么table数组长度必须为2^n?

进行数组偏移量计算时，采用的是(n-1) & hash，n-1又是0001111 类似尾部全部为1的情况，使得计算出来的值一定在table的长度范围之内
位运算 比 常见的取模速度快
(n-1) & hash也就说明了真正有作用的是hash值的后几位数字，而hash的值hashcode ^ (hashcode >> 16) 低16位和高16位做异或运算得到的，意味着hash后几位数字由hashcode高低位共同决定，这也进一步的降低hash碰撞

有什么缺点么？

在JDK1.7中在高并发场景下扩容机制会出现链表循环的情况（主要是头插法导致），使得CPU负载达到100%，不过在JDK1.8中已经不存在该问题了
线程不安全，无锁控制，也不能控制活跃性问题，也无法解决发布安全的问题，那么该如何解决呢？
扩容存在潜在的OOM的情况，例如当前1G的空间已经使用了800M，再经过扩容之后就会出现OOM的场景，这样进一步说明了必须预估业务场景的容量大小，并一次性赋值到位，减少无所谓的扩容操作

本人微信公众号（搜索jwfy）欢迎关注

微信公众号