简介

HashMap的基本解构是数组+链表，每个元素会被哈希到数组的一个节点，数组节点存放的是对应位置的链表的头节点，数据被哈希到对应位置后，插入到链表中（1.7是头插法，1.8是尾插法）。

若要插入元素a，哈希计算方法是(n-1) & a.key.hash

hashMap的常用方法有：

computeIfAbsent

computeIfAbsent方法有两个参数，1为要添加的key，2为如果该key没有，在hashMap中创建一个什么样的key-v。专门对map value是集合的时候好用。

computeIfAbsent方法的语法为：

hashmap.computeIfAbsent(K key, Function remappingFunction)

computeIfAbsent后面一般加addall和add等，添加内容一定会被添加到参数1对应的key对应的value中，但要求addAll和add传入内容与remapping方法一致。例如：

# 判断没有LaoMao的key，新建一个空list做value，并把hahah加入到LaoMao对应的list中
Map<String, List<String>> map = new HashMap;
map.computeIfAbsent(“LaoMao”, k -> Lists.newLinkedList()).add(“hahah”)

putIfAbsent

putIfAbsent方法会先判断指定的键（key）是否存在，不存在则将键/值对插入到 HashMap 中。

hashmap.putIfAbsent(K key, V value)

返回值:

如果所指定的 key 已经在 HashMap 中存在，返回和这个 key 值对应的 value, 如果所指定的 key 不在 HashMap 中存在，则返回 null。

注意：如果指定 key 之前已经和一个 null 值相关联了 ，则该方法也返回 null。

map.entrySet

获得一个entry对象，可以进行遍历，set中每一个元素都是Map.Entry<>类型

使用entry.getValue() 可以获取其中的值

Map<String, Response<String>> existedResourcesMap = redisClient.batchGet(redisKeyToOriginalObj.keySet());
for (Map.Entry<String, Response<String>> entry : existedResourcesMap.entrySet()) {
    if (StringUtils.isNotBlank(entry.getValue().get())) {
       continue;
    }
}

此处value是Response类型，想获取其中的response，使用.get()方法

.keySet()可以获取map中所有key组成的set

HashMap源码分析

成员变量

先观察HashMap中的核心成员变量，基本都是常量：

// 初始默认容量为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量为1*2^(31-1)
static final int MAXIMUM_CAPACITY = 1 << 30;
// resize的容量阈值因子，默认为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 默认Hmap默认是数组+链表，对链表进行树化和对树进行链表化的阈值
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
// HashMap中的数组载体
transient Node<K,V>[] table;
// HashMap中k-v对的数量
transient int size;
// hashMap结构的修改次数，可以标志这个hashmap被初始化的是否合理
// 因为每次resize都要做rehash，性能损耗很严重
transient int modCount;

再看Node自己的成员变量

final int hash;
final K key;
V value;
Node<K,V> next;

可见比较简单，记录该node位置的hash值，node上存储的键值对，以及node的后继节点。

再看HashMap的TreedNode节点：

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;
// 继承自LinkedHashMap.Entry的成员变量
Entry<K,V> before, after;

TreeNode节点的成员变量包括自己的父节点、左右孩子，前驱，除此之外，继承自LinkedHashMap.Entry还继承了其前驱和后继变量

putVal - 增加元素的底层方法

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

可以发现最常用的put方法底层调用的就是putVal方法

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

上来两个if是先做兜底，分别是当数组载体table为null，或table的size为0的情况下，做resize扩容操作；以及数组中对应的哈希位（计算哈希位的算法就是(n-1)&hash）没有node（null），做新建node操作。

下面一个else中就到了插入的地方，先不看，因为走进了这个else基本是可以return的，不会走到最后的逻辑，先看下如果走的是前面的兜底流程，最后走的内容：

++modCount;
if (++size > threshold)
    resize();
afterNodeInsertion(evict);

因为前面两个if兜底分别是兜table为null的场景和node为null的场景，都要为table做resize，或新建一个hashnode，都算作hashMap结构修改，因此这里先自增modCount，同时因为有存入新的kv，也自增size，如果自增后大于阈值了，也要做resize。

这里也就看出，每次结构变更都会记录modCount属性，这个属性也就意味着hashMap做resize或rehash的次数，通过这个属性就可以看出来如果次数太多，map就会有严重的性能损耗，可以适当优化。

再看无需兜底直接插入的else操作：

else {
    Node<K,V> e; K k;
    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);

这里p是刚刚算的哈希位找到的node。

第一个if这里做判断，满足以下条件：

• p的hash和传入的hash一样

• p的key和传入的key一样，或传入的key非空切满足equals，其实就是一样

这时就会把找到的p赋值给e

第二个if-else是判断当前节点p以及是个树了，需要调用putTreeVal把键值对存入树，这里就会涉及到更多红黑树平衡和旋转方面的逻辑。

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
                treeifyBin(tab, hash);
            break;
        }
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            break;
        p = e;
    }
}

最后一个else对应了既不是树，取出来的node的key又不相同的情况（虽然第一个if既判断hash又判断key，但走到这里一定是key不相同，因为hash相同才会分到这个坑位），那说明现在还是个链表，那就对链表做遍历。这里先利用for循环做了一个死循环，用来遍历里面的各个node，分为以下三种情况：

• 情况1：当前node对不上，且下一个node又是null，直接新建node存储这个k-v，但是如果存入时链表长度达到转化为树的阈值，就调用treeifyBin方法转为树，然后跳出循环

• 情况2：当前node对上了，跳出循环，但是这里因为循环中不断使e=p.next，所以实际跟第一个if一样，还是把key相同的node赋值给了e。

• 情况3：当前node对不上，下一个node不是null，本轮静默开始循环下一轮。

循环结束后最终取出了key相同的node，或新建node存储到e中，下面就该处理拿出来的node的了。

if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}

先把e的value存到oldValue，然后再把传入的value覆盖到e的value，这里也就说明了在hashMap中调用put，相同key就默认覆盖了。而如果是putIfAbsent这里传入的onlyIfAbsent是true，那就不会覆盖。

public V putIfAbsent(K key, V value) {
    return putVal(hash(key), key, value, true, true);
}

后面的afterNodeAccess是空实现，留给用户自行决定是否添加一个插入后处理操作。而基于HashMap实现的linkedHashMap是有该方法的对应实现。

而上面的return oldValue可以看出，基本上没走兜底走到else，就差不多都能return了，无需做modCount的自增，那就说明性能没有什么损耗。

resize - 扩容

如果容量已达上限是不能扩的。

正常情况下会扩容至2倍，新阈值也变成2倍。

else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
         oldCap >= DEFAULT_INITIAL_CAPACITY)
    newThr = oldThr << 1; // double threshold

如果map是还未初始化的状态，容量和阈值都取默认值

newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

其中默认容量是16，默认阈值是默认负载因子（不指定是0.75）*默认容量。

扩容后需要做内部元素的再哈希

这里再哈希的思路是遍历每个数组节点，看看存储的链表是红黑树还是链表，如果是链表，先算rehash结果，然后采用尾插法（1.8）存入对应位置的链表

代码如下：

do {
    next = e.next;
    if ((e.hash & oldCap) == 0) {
        ……
    }
    else {
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);
……
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}

有这样一段

if ((e.hash & oldCap) == 0) {
    ……
}

如果(e.hash & oldCap) == 0 说明位置没有发生变化，不需要处理，否则，走下面尾插流程

为什么这里等式成立就说明没有变化呢？

假设老map容量为16，有a、b存入map：

先用(n-1) & a.key.hash 这个完整公式算下

先计算在老表中的哈希位置：

再算新表的

再看下b的

由于老长度16变成32，扩容2倍，实际上就是(n-1)的二进制数在最高位多一个1

那么a和b的哈希结果，实际上就是，n-1新加的那个1位置与哈希值做比较，即a.hash & 0 0 0 1 0 0 0 0 这个值是1，即有变化，值是0，即没有变化

而0 0 0 1 0 0 0 0其实与0 0 0 0 1 1 1 1是相等的

即变成(e.hash & oldCap) == 0

然后再看尾插法的处理过程

hash和rehash结果不同的处理流程是类似的，以不一致处理流程为例遍历到数组第j个位置的链表时：

• next指向链表中当前节点e的next节点

• 如果e是本链表遍历的第一个节点，那么hiTail一定为null，使hiHeahd指向e，同时hiTail指向e；如果e不是第一个节点，那hiTail上一轮已经指向了e的上一个节点，此时使hiTail的下一个指向e，hiTail自己指向e

• 如果e的next不为空，使e=e.next并重复循环

这样重复下来直到e是最后一个节点，hiHead就指向了第一个节点，hiTail就指向了最后一个节点。然后如果hiTail非空，使hiTail.next指向null，把头节点hiHead存入数组的第j+oldCap位。完成尾插法rehash。

treeifyBin - HashMap转树

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);
break;

在putVal方法中，当长度达到了转树阈值就触发转为红黑树。

这里的binCount是数组位上的链表长度，因此判定触发树化流程是先通过单个位置上的元素判定的。然后下面到树化流程中：

首先判定node数组为空，或数组长度小于树化最小限制，可以先通过resize扩容去解决。这里就是单个位置上太长，但是数组总长度又不算太长，这种情况只需要做下resize，增加数组长度，可以先不用做树化。如果数组长度也超过树化下限了，再去做进一步的树化。

再看else-if

else if ((e = tab[index = (n - 1) & hash]) != null) {

这里传进来的hash是putVal时元素对应的hash值，通过(n-1)&hash是计算对应数组位的头节点。如果头节点非null：

TreeNode<K,V> hd = null, tl = null;
do {
    TreeNode<K,V> p = replacementTreeNode(e, null);

用TreeNode取代原本的Node节点e。创建的hd、tl分别代表头、尾节点。然后开始构造双向链表

// 如果还没有设置尾节点，让头节点指向当前节点
if (tl == null)
    hd = p;
// 如果已经有尾节点了，把当前节点p插入到最后，即p前驱指向尾节点，尾节点后继指向p
else {
    p.prev = tl;
    tl.next = p;
}
// 最后让尾节点指向p
tl = p;
// 最后是循环条件，即数组头节点e的位置上还有后继，那么就把后继赋值给e，继续循环
} while ((e = e.next) != null);

到这里构造好了一个双向链表，实际上还没有真正完成树化。然后判定头节点是存在的，树是存在的，进行真正的树化流程。

if ((tab[index] = hd) != null)
    hd.treeify(tab);

treeify - 真正的转树操作

for (TreeNode<K,V> x = this, next; x != null; x = next) {

这里是treeNode.treeify，因此this是node本身

next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {
    x.parent = null;
    x.red = false;
    root = x;
}

这里首先是做初始化工作，判定root没有，先指定root。红黑树上来新节点置黑，左右孩子置空。然后进入一个无限循环

for (TreeNode<K,V> p = root;;) {
    int dir, ph;
    K pk = p.key;
    if ((ph = p.hash) > h)
        dir = -1;
    else if (ph < h)
        dir = 1;
    else if ((…………
    ……
    TreeNode<K,V> xp = p; // 保存当前树节点

这里面dir代表位置，-1左，1右，因此这一段实际上是算根p的hash值ph，与当前传入的节点x的哈希值h对比，比根小放左边，比根大放右边，如果相同那么还要通过其他方式再进行比较。如果当前链表节点的key实现了comparable接口，并且当前树节点和链表节点是相同Class的实例，那么通过comparable的方式再比较两者。如果还是相等，最后再通过tieBreakOrder比较一次。

然后到设置左右孩子的流程：

if ((p = (dir <= 0) ? p.left : p.right) == null) {
    x.parent = xp;
    if (dir <= 0)
        xp.left = x;
    else
        xp.right = x;
    root = balanceInsertion(root, x);
    break;
}

就是判断dir的大小，决定设置左孩子还是有孩子。设置完了调用balanceInsertion方法再平衡树。

balanceInsertion - 再平衡树

先回顾插入规律：

默认插入时为红，因为红色不影响平衡

• L1-如果插入节点没有父节点，当前插入的就是根，根节点置黑

• L2-如果父节点为黑色或没有爷爷节点，不做任何处理

• L3 -如果父节点为红色

  • L3.1-如果有叔叔节点且为黑色，叔叔父亲置黑爷爷置红

  • L3.2-没有叔叔节点或叔叔为红色

    • L3.2.1-先转父亲，如果父亲在左自己在右，则父亲左旋，如果父亲在右自己在左，则右旋

    • L3.2.2-再转爷爷，爷爷必然要旋转，怎么旋转看父亲，父亲在左，爷爷右旋，父亲在右，爷爷左旋，同时父亲置黑爷爷置红

• L4-然后从爷爷节点继续调整，直到调整到根

for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
    if ((xp = x.parent) == null) {
        x.red = false;
        return x;
    }
    else if (!xp.red || (xpp = xp.parent) == null)
        return root;

可以看出这块是一个无限循环，只有两个出口，要么是根，要么是调整到不需要再调。符合上面的L1、L2步骤

如果父亲是红色，就走L3步骤，拿父亲是爷爷的左孩子做参考

if ((xppr = xpp.right) != null && xppr.red) {
    xppr.red = false;
    xp.red = false;
    xpp.red = true;
    x = xpp;
}

步骤L3.1，如果叔叔是黑色，那不用旋转，只需要把父亲叔叔置黑，爷爷置红

else {
    // L3.2.1 转父亲
    if (x == xp.right) {
        root = rotateLeft(root, x = xp);
        xpp = (xp = x.parent) == null ? null : xp.parent;
    }
    // L3.2.2转爷爷
    if (xp != null) {
        xp.red = false;
        if (xpp != null) {
            xpp.red = true;
            root = rotateRight(root, xpp);
        }
    }
}

否则叔叔就是红的或者空的，先转父亲，如果自己跟父亲异侧父亲才转，向自己在父亲的异侧转（父亲在左我在右，左转；父亲在右我在左，右转），然后再转爷爷，要把父亲置黑爷爷置红，再把爷爷向父亲方向相反的方向转，（父亲在左爷爷右旋，父亲在右爷爷左旋）

rotateLeft、rotateRight左旋、右旋

旋转就是同侧降级，对侧升级。

• 对侧的同侧孙子升级为自己的对侧孩子

• 对侧孩子占自己的位置

• 自己成为对侧孩子的同侧孩子

例如左旋，先让右孩子的左孩子变成自己的右孩子，然后自己的右孩子升级占据自己的位置，自己成为原先右孩子的左孩子。

// 右孩子存在的情况下
if (p != null && (r = p.right) != null) {
    // 右孩子有左孩子，则成为自己的右孩子
    if ((rl = p.right = r.left) != null)
        rl.parent = p;
    // 自己的父亲成为自己右孩子的父亲，如果自己父亲为空，右孩子就变成根，置黑
    if ((pp = r.parent = p.parent) == null)
        (root = r).red = false;
    // 如果自己有父亲，自己原本是左节点，右孩子就当父亲的左节点，反之右孩子成为右节点
    else if (pp.left == p)
        pp.left = r;
    else
        pp.right = r;	
    // 自己成为原先右孩子的左孩子
    r.left = p;
    p.parent = r;
}

最后把最终的root节点返回去