关于HashMap的部分创建流程
前言：最近学习了HashMap有关的一些方法与理念，所以萌生了写一篇有关HashMap的文章，仅是个人理解，欢迎理性探讨。
下面是个人对于HashMap的一些理解。
Map接口
首先我们要了解HashMap的父接口Map，关于Map接口，我们可以翻看官方的API，里面有它的实现类以及定义。
All Known Implementing Classes:
, HashMap, Hashtable, IdentityHashMap, LinkedHashMap, RenderingHints, TreeMap,
这里我仅截取了部分内容，大致意思是HashMap是Map的实现类，这里要提一句，Map接口不属于collection接口的系列。
Map是由键值对组成的容器，Map中的键是key，Map中的值是value。Map中的集合不能包含重复的键，值可以重复，每个键只能对应一个值。key-value称之为键值对。这个就类似于前端的创建对象，一对一原则。
将每一个键值对看作一个对象，抽取出一个代表键值对的接口—Map.Entry。一个映射是由多个Entry对象组成的。
HashMap类的介绍
HashMap是Map的实现类，其存储的为键值对，有一个类叫做HashSet，是对Set接口的一个实现，它的底层是基于HashMap，不同的是一个存储的为数据，一个存储的是键值对。
关于HashMap，我们首先要知道它的存储结构是什么，才能去进一步了解它的底层原理。
下面是关于HashMap的结构图：
我们可以将它理解为一个数组，每个数组对象上面对应着一个链表的头（红黑树），这个对象我们称之为桶（bucket），就好像你提着一根绳子，绳子上面挂满了桶。
关于HashMap，我们还要了解关于它的两个个变量：
- INITIAL_CAPACITY 初始容量
这个是HashMap的初始容量，初始值为16，就是在不给定初始容量时的容量值，即这个数组的长度，为什么不说是在无参构造时给定的值呢？这个我们在后面会提到。 - LOAD_FACTOR 加载因子
当HashMap的内部使用达到一定比例的时候，就会有可能进行扩容，防止内部存储过长，影响效率，但并不是防止内部存满，至于原因会在HashMap的存储结构中讲到。加载因子的默认值为0.75.
这个扩容的临界点是 实际键值对的数量/桶的总数量>=加载因子，但严格来说并不是达到这个点就会扩容，因为它的底层还有其他的判断。
我们在了解这些以后就对HashMap有了一个初步了解，那就和我一起来手撕源码吧。
HashMap的创建
HashMap的创建分为无参构造和有参构造，在有参构造中又分为了默认加载因子和给定初始加载因子的情况，我们打开源码来看一下。
- 无参构造
//无参构造
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } /** * Constructs an empty <tt>HashMap</tt> with the default initial capacity * (16) and the default load factor (0.75).
- 1
- 2
- 3
- 4
- 5
- 6
- 7
在无参构造中，我们并未看到给定initialCapacity（初始值），它仅是给定了加载因子（loadFactor），将默认加载因子赋给对象，而默认加载因子可以在源码中查到，那么初始值在哪呢？我们可以在后续源码中找到。
/** * The load factor used when none specified in constructor. */ //加载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认初始值
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
也就是我们上面提到的0.75。
- 有参构造
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }
- 1
- 2
- 3
- 4
这个是源码中关于有参构造的第一种方法，仅设置初始值，不设置加载因子，使用默认的加载因子0.75.
/** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ 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); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
这是有参构造的第二种方法，自己设定初始值和默认因子，他会先对初始值进行一个判断，如果小于0会抛出异常，如果大于他的最大限度，就会等于最大限度，最大限度是 1<<30,在源码中也有声明
/**
//初始值的最大值 * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */ //最大长度 static final int MAXIMUM_CAPACITY = 1 << 30;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
注意：初始默认值必须是2的次方，如果设置的不是，那么它会自己提升到离他最近的2的次方。
在源码中是进行无符号右移来完成，如下：
//初始值提升
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; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
HashMap的put方法执行逻辑
在JDK1.7的某个版本中，当你new这个HashMap对象的时候，就已经在底层构造了数组,但在之后的版本，也就是1.8版本中，当你new对象的时候并未进行数组的创建，而是在进行put方法的时候创建数组，将初始值赋给数组。
//put方法
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
- 1
- 2
- 3
- 4
put方法调用先计算出key的hashcode值，并对其进行二次处理，获得hash值，然后调用putVal方法，下面是对这个方法的个人理解。
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) //这里是调用resize创建了一个长度为16的数组 //扩容也是这个函数 n = (tab = resize()).length; /*(n - 1) & hash保证了下标能够分配在数组内 按与计算，在为2的次方时后几位都是1，前几位都是0，这样就可以保证绝对分布在 下标之内 p现在为添加到的桶的下标*/ if ((p = tab[i = (n - 1) & hash]) == null) //如果现在这个桶里为null，那么就可以直接放进去 tab[i] = newNode(hash, key, value, null); else { //如果不是空就开始对着桶里的元素对比 Node<K,V> e; K k; /*先比较hash值，如果hash值不一样，短路原理直接往下走, 如果一样比较两个的地址，如果地址不一样再用equals进行比较。 如果都满足了，那就直接覆盖掉*/ 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) { p.next = newNode(hash, key, value, null); //如果大于TREEIFY_THRESHOLD，也就是转红黑树的阈值，那就转成树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } //和每一个对象进行比较，如果找到相同的，直接break退出for循环，进入下面的，如果到结尾没找到相同的，那么把e给p,就是插到它的后面 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //e不为null说明有相同的key存在 if (e != null) { // existing mapping for key V oldValue = e.value; // 如果为true则不修改已经存在的map的值除非oldValue为nul if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } //用于fast-fail机制（据说，具体是啥我也不知道） ++modCount; //如果数量大于阙值，就进行扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
上面就是对put方法的个人理解，除了这个HashMap还有一个比较重要的方法，resize（）也就是扩容方法。
resize方法
它是计算扩容
final Node<K,V>[] resize() {
//将扩容前的数组给oldTab,老数组的长度给oldCap,老阈值给oldThr Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; //创建新的长度和阈值，目前为0 int newCap, newThr = 0; /* 对老数组的长度进行判断，如果长度是最大的，那么将最大阈值给threshold， 也就是老阈值扩大到最大，这个时候，如果实在是放多了，每放一次进行一次扩容， 但啥都最大了，树底下慢慢放吧，没救了。*/ if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } /*如果不是最大，新长度为老长度的两倍，即进行位运算，左移一位，保证是2的次方 ，这样在进行put方法里的(n - 1) & hash时，能保证分配到下标里，有一点是如果老 长度不大于16，不会进行阈值扩大两倍这个操作*/ else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } /*如果进入这句，说明table里面是空，也就是第一次执行put，把 默认阈值或者设定的阈值给newCap*/ else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; /*当无参构造第一次执行put方法的时候，阈值并未赋值， 所以oldThr是0，所以进入下面的构造，将默认值赋给长度和阈值*/ 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 //下面是进行rehash，将每个元素的hash值重新计算，在新的数组里进行排列 //组合，最后返回新的数组和链表（红黑树） 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; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
总结
关于JDK1.7和JDK1.8的HashMap的区别：
- jdk7底层的数组是Entry[],jdk8底层数组是Node[]。
- jdk8首次调用put方法时，才在底层创建长度为16的数组。
注：某些JDK7的版本也是在put方法后建立数组，但在面试中基本都是说在new方法的时候就进行了创建。 - jdk7底层结构只有数组加链表。jdk8底层结构是数组加链表加红黑树。
- jdk7添加数据是加到原来数据的前面，jdk8添加数据是加到原来数据的后面(next)。
影响rehash的原因：
- 初始容量过小；
- 加载因子过小；
注：rehash是将所有的元素都进行重新排列，这个过程是非常消耗资源的，所以在能不进行rehash就别rehash,初始值提前设置为较为合适的数量。
关于扩容的不同：
在JDK1.7中，他会判断键值对数量是否大于等于阈值并且当你这次放的元素所在的桶不为空时，才会进行扩容，也就是同时满足两个条件才会扩容，在JDK1.8中，去除了判断桶是否为空的条件，当数量大于等于阈值时就会进行扩容。
我们当时老师讲的是使用桶的数量大于等于阈值时会扩容，但自己翻看源码时发现有点不对劲，它每放一个元素size就进行自加,然后用size和阈值进行比较。
关于链表转红黑树
当某一个位置的链表长度>=8并且元素数量>=64，会将链表扭转成红黑树，另外还有个阈值是6，当rehash之后，如果这个桶之前是红黑树，那么它还是红黑树，但是如果里面键值对的数量低于了6，就会重新转为链表。
文章来源: blog.csdn.net，作者：我叫宋大宗，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/qq_42649356/article/details/115011769