源码阅读-HashMap

写在开头

扩容是一个特别耗性能的操作，因此建议使用HashMap时，尽量指定一定大小的初始容量
HashMap是线程不安全的，并发环境中建议使用ConcurrentHashMap
JDK8中引入的红黑树优化了大量hash碰撞时的性能
HashMap中的红黑树代码作者实在没力气看了，因此这篇文章不涉及内部红黑树分析

该篇文章纯粹是作者个人观点，并非官方权威，阅读请勿迷信

数据结构

hashmap使用数组+链表（红黑树）作为整体结构

节点数据结构

一般情况下，节点会使用如下代码构建结构,该结构为单链表

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

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

    ...
}

JDK8中增加特性：当链表长度超过8时（等于也会触发），会转换为红黑树结构。红黑树需要了解的小伙伴可以看下这篇文章：一步一步数据结构-红黑树

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}

整体结构

图片来源美团技术博客：Java 8系列之重新认识HashMap hashMap内存结构图

本质上，在一般情况下的HashMap就是一维数组+单链表，其中一维数组在这里的作用个人感觉更像是指针，当用户通过`get`获取值的时候，先通过hash找到对应数组位置，再通过数组找到对应的链表，再进行链表遍历找到完全符合的**键值节点**

数据操作

在初步了解HashMap长相之后，我们可以通过基本操作来了解它的工作过程。

hash与索引计算

HashMap通过Key的hash值找到数组的对应位置，因此我们需要先行了解hash的运算规则，因使用的是key对应对象的hashCode()函数，因此在使用自定义对象作为key时，需格外注意。
运算符相关介绍：
>>> 右移运算符
 ^ 按位异或运算符

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

索引计算通过(n - 1) & hash，引用美团技术博客中原文(n即length)：

这个方法非常巧妙，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

增

public V put(K key, V value) {
    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;
    // 此处是对HashMap容量判断，属于边界异常判断
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 需注意的是，上一小节是介绍hash的运算过程，转换为数组索引是`(n - 1) & hash`
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 索引位置链表为空，直接插入
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 此处判断的是对应索引位置单链表的头结点，需注意(k = p.key) == key || (key != null && key.equals(k)))
        // 因key可以为任意对象，因此==在某些时候不能作为判断相等
        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节点，直接尾插法插入新节点
                    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
            // 相同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;
}

删

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    // 避免数组为空（即HashMap为空），数组索引对应链表为空
    // (n - 1) & hash   已经计算索引位置
    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;
        // 添加if判断，避免边界问题（个人猜测主要是避免红黑树的情况）
        // 因为单链表的边界避免可以通过循环条件控制，此处使用的是do{}while循环，可以使用while改变条件判断时机
        // 此处都是个人猜测，极具争议性，非正规解释
        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);
            }
        }
        // 找到节点后进行删除操作，判断条件避免不存在节点情况和需要严格匹配值情况
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                // 红黑树交由内部处理
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                // 此处情况是，链表头结点就是所寻节点，因此node与p相等
                tab[index] = node.next;
            else
                // 单链表删除操作
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);// 意义不明
            return node;
        }
    }
    return null;
}

查

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) {
        // 链表头结点判断
        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;
}

小结

所有操作在需要对链表进行判断的情况下，在JDK8中，都是先判断头结点，再判断是否存在后续节点，然后红黑树交由红黑树内部方法处理，单链表遍历通过do{}while进行循环遍历。对比JDK1.7我们可以看出代码变化

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);

    return null == entry ? null : entry.getValue();
}

private V getForNullKey() {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

final Entry<K,V> getEntry(Object key) {
    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

JDK7中，因为没有引入红黑树优化，因此链表都为单链表，因此遍历都是通过for循环，后续节点非空判断也在for循环的判断条件中。因此，此处个人大胆总结，该变化由红黑树引起。可能由于instanceof存在一定程度的性能损耗，因此，先进行首节点判断以尽可能的避免首节点就是所寻节点从而不用使用instanceof可以提升一定程度的性能（存在争议）。

自动扩容

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

// 仅指定初始容量，使用默认的加载因子0.75
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

// 使用默认的加载因子初始化，未指定初始容量，将会使用默认初始容量16
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

// 根据已有map导入至新的hashmap中，使用默认加载因子0.75
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

以上创建HashMap的方式中，需要注意指定初始容量的函数，两者都会执行this.threshold = tableSizeFor(initialCapacity);这段代码将会将使用者指定的容量转化为2的整数次方数，举例说明tableSizeFor(11)将会返回16,tableSizeFor(17)将会返回32。其内部实现为

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

他人解释，根据该解释，再加上程序语言一般情况下int最大值为2147483647，转化为二进制是32位，而1+2+4+8+16=31，因此基本可以认定只要传入int不是非法，都会被该函数运算处理，此时需要注意static final int MAXIMUM_CAPACITY = 1 << 30;该函数限定了最大值。
一般情况下，我们使用HashMap并不会指定初始容量与加载因子，会使用默认的无参构造（即将会创建初始容量为16，加载因子为0.75的一个HashMap），那么很容易会碰到容量达到阈值（总容量*加载因子）从而触发自动扩容。因为底层就是创建新数组，然后数据内容从旧数组中转移至新的，因此我们先看下数据的新增定位过程。

HashMap的索引计算

之前查看put源码时，很容易看出索引位置由(n - 1) & hash算出，其中n为当前数组容量长度。&是按位与运算，我简易模拟下hash为48和1568时的运算：

  48-> 0000 0000 0000 0000 0000 0000 0011 0000
  15-> 0000 0000 0000 0000 0000 0000 0000 1111
&
       0000 0000 0000 0000 0000 0000 0000 0000 -> 0

1568-> 0000 0000 0000 0000 0000 0110 0010 0000
  15-> 0000 0000 0000 0000 0000 0000 0000 1111
&
       0000 0000 0000 0000 0000 0000 0000 0000 -> 0
Tips:48为字符串"0"的hash值，1568为字符串"11"的hash值
因为&运算的特性，仅有1&1的结果才为1，因此n-1的值限定了计算&的长度
当前例子中仅仅计算最后四位，因为前面的所有都是0，无需考虑

HashMap的扩容

扩容由++size > threshold触发，因此我使用如下代码进行简易的触发扩容，并且确保至少有一条单链表存在一个以上的节点。

HashMap<String, Integer> test = new HashMap<String, Integer>();
for (int i = 0; i < 13; i++) {
    // 0 与 11 索引位置相同，索引为0
    // 1 与 12 索引位置相同，索引为1
    test.put(String.valueOf(i), i);
}

从图中可以轻易看出数组已经存在11个数据，因此当前size为11，此时满足++size > threshold条件，触发扩容，容量会由newThr = oldThr << 1; // double threshold扩大一倍（即原来的两倍），因为容量的扩大，计算索引时的公式(n - 1) & hash，此时n-1的二进制肯定比之前多一位，因此节点的位置需要重新计算。而根据函数tableSizeFor我们可知，基本上所有的HashMap的容量都是2的整数次方数。因此可以看如下过程（以初始容量为16举例）

原始内容    hash值   hash值的二进制                               与15&结果  与31&结果
0           48      0000 0000 0000 0000 0000 0000 0011 0000     0           16
11          1568    0000 0000 0000 0000 0000 0110 0010 0000     0           0
-----------------------------------------------------------
n-1=15(非hash值!)   0000 0000 0000 0000 0000 0000 0000 1111
n^2-1=31            0000 0000 0000 0000 0000 0000 0001 1111
Tip：对不齐我也没办法，我也很难受，将就看吧

可以轻易看出，元素是否需要转移位置取决于新增的那一位是1还是0，因此和n进行&运算即可得知，为0即保留位置无需移动，为1则代表需要移动n个位置。
先看下源码

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    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
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    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) {
        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;
                        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.next == null)
    // 此处意味着当前索引的链表仅有头结点
    // 因此直接重新计算索引
    newTab[e.hash & (newCap - 1)] = e;

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

以上两段代码可以清晰看出无论当前索引位置的链表仅有一个节点还是多个，都会进行&计算，因此美团关于HashMap的文章中有这么一段

这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8不会倒置。有兴趣的同学可以研究下JDK1.8的resize源码，写的很赞，如下:

同时我们对比JDK7中扩容迁移的源码来看

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> 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;
        }
    }
}

此时，我们观察源码得知，的确省去重新计算hash值的时间，不过链表元素会产生倒置是因为JDK7中put使用的是头插法。因此，个人在此猜测，当链表超过一个节点时不直接使用newTab[e.hash & (newCap - 1)] = e;是为了避免索引一致时的尾插法的链表遍历（链表插入删除操作快，查询满；而数组查询快，删除插入操作稍慢），使用第二段代码明显可以减少一次单链表的遍历。