1. HashMap

平时我们用 HashMap真的太常见了，那我们对 HashMap 的了解有多少呢，今天我们就一起来分析分析 HashMap。

1.1 HashMap 特点

• HashMap 底层是 哈希表 结构的。

• HashMap 依赖hashCode方法和equals方法保证 键 的唯一

• 如果键要存储的是自定义对象，需要重写hashCode和equals方法

• 如果键存储的是非自定义对象 ，则不需要重写hashCode和equals方法

1.2 HashMap 用法

Map<String, String> map = new HashMap<String, String>();
map.put("zhangsan", "23");
map.put("lisi", "24");
map.put("wangwu", "25");
map.put("zhangsan", "26");
map.forEach((k, v) -> System.out.println(k + "=" + v));

怎么说，打印的是什么？

靠，这还用说，那我们直接展示答案吧。

lisi=24
zhangsan=26
wangwu=25

有什么特殊的呢，好像... put 的是 4个数据，打印的是3个数据。其中 zhangsan 被替换了，变成 26了。

来了，正式进入主题吧...

我们map是怎么put数据的呢，zhangsan的value又是怎么被替换了呢，到底是整个替换呢，还是有不为人知的秘密呢...

1.3 HashMap 源码分析

下面我们就开始一层一层的去分析吧

直接点击put 跳转到方法入口：

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

那我们就去看下putVal方法。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
     //里面一堆逻辑，稍等分析
}

首先看第一个参数 hash。

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

到这里我们就知道第一个hash就是通过key去获取hashCode。

现在我们开始逐一拆解 putVal方法。里面一开始是这么写的：

Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

定义了一个tab局部变量数组，一个p节点，定义 int n i。

把 table 给到 tab。那我们先看看table是什么？

transient Node<K,V>[] table;

哦，原来是哈希表里面的数组 table， 里面存放对象是 Node对象。

一开始数组table肯定是null的。 所以会触发n = (tab = resize()).length;。

这里可以看出 n 就是 数组tab的长度。

下面我们来看下resize()方法是怎么调用的

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) 
        newCap = oldThr;
    else {
        //第一次数组为空，创建一个默认长度为16，加载因子为0.75的数组
        newCap = DEFAULT_INITIAL_CAPACITY;
        // 扩容长度为 16*0.75 = 12
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        // 新的扩容为 newCap *0.75
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    
    // 创建一个newTab数组，第一次newCap就对应上面的16
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
           //把数据全部转移到新的哈希表中
        }
    }
    return newTab;
}

resize()方法总结来说就是：

1. 如果当前是第一次添加数据，底层会创建一个默认长度为16，加载因子为0.75的数组
2. 如果不是第一次添加数据，会看数组中的元素是否达到了扩容的条件

• 如果没有达到扩容条件，底层不会做任何操作
• 如果达到了扩容条件，底层会把数组扩容为原先的两倍，并把数据全部转移到新的哈希表中

我们继续看后面的代码

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

这里的i 是 (n - 1) & hash, 就是根据数组的长度和哈希值来计算出当前数组存储的位置，就是数组的索引。

p = tab[i] 就是去 数组里面索引为i的 节点，第一次为null。 所以 tab[i]就会存放一个 newNode的节点，就是键值对对象。

Node(int hash, K key, V value, Node<K,V> next) {
    this.hash = hash;//键的哈希值
    this.key = key;//键
    this.value = value;//值
    this.next = next;//下一个节点的地址值
}

链表中的键值对对象包含这4个。

如果是红黑树：TreeNode，则多几个属性

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // //父节点的地址值
    TreeNode<K,V> left; //左子节点的地址值
    TreeNode<K,V> right; //右子节点的地址值
    TreeNode<K,V> prev; //上一个节点的地址值
    boolean red; // 节点的颜色,是否红色
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}

如果这时候p不为 null呢，tab[i]是已经有数据在那里了，当前索引下是有值了， p就是已有的数据。

else {
    Node<K,V> e; K k;
    // 判断旧值和新值键是否一样
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        //哈希值和键值一样，就把旧值存放到临时e中，一会直接替换。
        e = p;
    else if (p instanceof TreeNode)
        //如果数组中获取出来的键值对是红黑树中的节点
        //调用方法putTreeVal，把当前的节点新数据按照红黑树的规则添加到树当中。
        // 里面会根据哈希值大小来放到红黑树位置上
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
        //p不是红黑树，那就是链表，
        for (int binCount = 0; ; ++binCount) {
            if ((e = p.next) == null) {
                // 临时p的下一个节点是空，创建新的节点直接添加到p的next上
                p.next = newNode(hash, key, value, null);
                if (binCount >= TREEIFY_THRESHOLD - 1) 
                    // 链表长度是否超过8,转为红黑树
                    treeifyBin(tab, hash);
                break;
            }
            //如果哈希值一样，key一样，再调用equals方法比较内部的属性值是否相同
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                // 代表找到链表下的节点和当前键值是需要替换的，e就不为null了
                break;
            //链表下为e，赋值给p，继续循环链表下一个节点e = p.next
            p = e;
        }
    }
    //如果e为null，表示当前不需要覆盖任何元素
    //如果e不为null，表示当前的键是一样的，值会被覆盖
    if (e != null) { 
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            // 把当前value的值替换到链表e中，且返回旧值。
            e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
}

我们在看下最后的代码：

if (++size > threshold)
    resize();
return null;

threshold计算的就是数组的长度*0.75，第一次添加size就1，如果大于 threshold, 就是满足哈希表的扩容时机，就会走上面提到的resize()方法了。 return null就表示没有覆盖任何元素。

1.4 总结

糟糕，写的有点乱，初学者，所以还是简单总结一下：

• 哈希表数组位置为下索引为null，我们就直接添加到该索引下就行。
• 哈希表数组位置为下索引不为null，也就是意味着有旧的 Node 在该位置上。
• 这时候旧Node无非 是链表或者红黑树。
• 如果key不一样，挂在下面形成链表或者红黑树。
• 如果key一样，就直接替换 value。

到这么差不多了，那我们上面的答案，就显而易见了

zhangsan还是那个初始的zhangsan，地址值不变，value变了。