HashMap源码详解

提醒你一下，用电脑或者平板看，手机屏幕小，图片会看不清楚，源码不方便看

基础前置

看该篇文章之前先看看这篇基础文章 HashMap底层原理-CSDN博客

先来看HashMap里面的一些参数。

1.DEFAULT_INITIAL_CAPACITY 默认的数组初始容量

2. DEFAULT_LOAD_FACTOR 默认的加载因子。（hashmap数组扩容机制：扩容阈值 = 数组容量 * 加载因子）

3. table 你知道的，hashmap底层是数组+链表+红黑树，不知道就先看上面说的基础文章，table就是这里面的数组。

4. size 集合中元素个数。

 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16static final float DEFAULT_LOAD_FACTOR = 0.75f;transient Node<K,V>[] table;transient int size;

这个是上面第三行代码里面的Node简化后的代码，源码还重写了equals和hashcode方法等，先不关注这些，看看简化后的就行。

构造方法

idea中ctrl+鼠标左键点进去看看源码。

查看下面源码可知：

1. HashMap是懒加载，也就是说，Hashmap在初始化的时候没有创建数组，只是初始化了加载因子

2. 无参构造函数里面，加载因子初始化为0.75

  public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}

put方法源码

　直接看代码可能不够直观，我们结合流程图来看，仔细耐心看完，顺着把每个流程走一下，待会儿看源码就会清楚很多。实在看不懂的话，看源码的时候再来结合图片看。

下图threshold就是上面提到的扩容阈值，扩容阈值 = 数组容量 * 加载因子。

而且你可能会迷惑为什么右下角转化为红黑树只需要判断链表长度，不应该还需要判断数组长度吗？这个你往下看，我会解答的。

并且，转化条件是链表长度>=8且数组长度>=64，下图是我网上找的，有点小错误，这里修正一下。

HashMap里面的put方法

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

第一个参数hash（key），其实就是计算key的哈希值，对应数组哪个下标位置。

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

现在看看上述的putVal方法。注释写了很久，各位爷给个三连，不懂的留言评论区，24小时内回复。

上述图片代码贴在下面了

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是懒加载，创建hashmap不会初始化，第一次插入值才初始化。    if ((tab = table) == null || (n = tab.length) == 0)//如果没有初始化，调用resize（）进行初始化，第一次初始化长度为16。resize方法源码后面也会带着大家看，现在先不着急。n = (tab = resize()).length;//(n - 1) & hash是与运算，算出了当前key、value插入到数组对应位置下标。if ((p = tab[i = (n - 1) & hash]) == null)//如果该下标为null，那么直接插入就行，进而转到58行代码tab[i] = newNode(hash, key, value, null);//如果不为null，就要进一步判断else {Node<K,V> e; K k;//判断该位置key和新传来的key是否一样if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))//如果一样，证明为修改操作，把该值赋值给p，直接转到48行代码e = p;//判断是不是红黑树else if (p instanceof TreeNode)//如果是红黑树，走红黑树的添加逻辑e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//既不是红黑树，key也不相同，证明是链表。else {//遍历链表for (int binCount = 0; ; ++binCount) {//找到next节点，如果为null，证明遍历到尾部了if ((e = p.next) == null) {//把新值放入链表尾部p.next = newNode(hash, key, value, null);//链表新插入节点，有转换成红黑树的可能，要判断链表长度是否大于等于8if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st//如果是，就转化成红黑树，这个转化操作就不带大家看了，感兴趣自己研究一下。treeifyBin(tab, hash);break;}//判断是否有key相同的值，如果有那就是修改操作，break后转到48行代码继续执行if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//e是修改操作中存放原数据的变量if (e != null) { // existing mapping for key//新值覆盖旧值V oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}//计数器，计算当前节点修改次数++modCount;//上面插入成功后执行++size，然后判断数据量是否大于阈值，大于的话数组就进行resize（）扩容   if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}

看到这，你应该大致明白了底层逻辑，但是有个坑我故意留给大家了，35行代码为什么只需要判断链表长度大于8就转成红黑树呢？不是说，要链表长度>=8且数组长度>=64吗。如果你对hashmap代码真的非常感兴趣，应该去看了第37行代码，方法内部的源码，treeifyBin(tab, hash);

现在我来带大家简单看看

下面的MIN_TREEIFY_CAPACITY=64，当数组长度小于64的时候执行扩容操作，否则才执行链表转化红黑树操作。至此，put的基本流程已经结束。

final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();else if ((e = tab[index = (n - 1) & hash]) != null) {TreeNode<K,V> hd = null, tl = null;do {TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)hd = p;else {p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);if ((tab[index] = hd) != null)hd.treeify(tab);}}

现在接着讲讲扩容机制吧