-
HashMap JDK1.7与1.8的区别
结构
首先HashMap在1.7中是以数组+链表的形式存在的, 而HashMap在1.8中则是以数组+链表+红黑树构成的, 当一个节点的链表长度超过8并且数组长度超过64时会将链表转换为红黑树,
初始化
初始容量大小介绍
说到数组就不得不提HashMap里面的成员变量DEFAULT_INITIAL_CAPACITY也就是容量大小，如果不指定的话默认是16，如果通过有参构造指定容器大小的话也必须是2的平方数，当然了如果传入的参数并不是2的平方数的话（最好不要这样，实在不知道写多少容量我们直接写个默认的大小16），HashMap会通过方法将它变成比这个数大且离2的平方数最近的数例如传入11他会变成16，之所以要这么做的原因是，根据上述讲解我们已经知道，当向 HashMap 中添加一个元素的时候，需要根据 key 的 hash 值，去确定其在数组中的具体位置。HashMap 为了存取高效，减少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现的关键就在把数据存到哪个链表中的算法。这个算法实际就是取模，hash % length，计算机中直接求余效率不如位移运算。所以源码中做了优化，使用 hash & (length - 1)，而实际上 hash % length 等于 hash & ( length - 1) 的前提是 length 是 2 的 n 次幂。并且 length 是 2 的 n 次幂从位运算的角度，length - 1的二进制为全1，hash & ( length - 1)可以尽量减少的hash值的损失，可以做到更好的散列。
上面提到了如果传入的指定大小并不是2的n次幂，HashMap会将大小变成比指定大小大且是2的n次幂的数，我们看看JDK1.7和JDK1.8是如何做的。
JDK1.7*/ 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); // Find a power of 2 >= initialCapacity int capacity = 1; // 从1开始不停的左移也就是变大2的n次幂，直到不比指定容量小 // 1 2 4 8 16 32.。。。 while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); table = new Entry[capacity]; init(); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
jdk1.7的方式是从1开始不断进行位运算，一次右移一位，即成一次2直到，计算容量大于传入的initialCapacity
JDK1.8// 假设cap为13 static final int tableSizeFor(int cap) { // n=12 int类型在内存中占4个字节，，一个字节占8位 int n = cap - 1; /* * 00000000 00000000 00000000 00001100 12 * 00000000 00000000 00000000 00000110 右移1位 * ---------------------------------------------- 或运算 * 00000000 00000000 00000000 00001110 14 */ n |= n >>> 1; // n=14 /* * 00000000 00000000 00000000 00001110 12 * 00000000 00000000 00000000 00000111 右移2位 * ---------------------------------------------- 或运算 * 00000000 00000000 00000000 00001111 15 */ n |= n >>> 2;//计算完n=15 /* * 00000000 00000000 00000000 00001111 15 * 00000000 00000000 00000000 00000000 右移4位 * ---------------------------------------------- 或运算 * 00000000 00000000 00000000 00001111 15 */ n |= n >>> 4;// 计算完n=15 /* * 00000000 00000000 00000000 00001111 15 * 00000000 00000000 00000000 00000000 右移8位 * ---------------------------------------------- 或运算 * 00000000 00000000 00000000 00001111 15 */ n |= n >>> 8;// 计算完n=15 /* * 00000000 00000000 00000000 00001111 15 * 00000000 00000000 00000000 00000000 右移16位 * ---------------------------------------------- 或运算 * 00000000 00000000 00000000 00001111 15 */ n |= n >>> 16;// 计算完n=15 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }- 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
JDK1.8中的做法简单来说就是通过位运算将最高非0位后面全置为1**，由上面可以看出通过这五次的计算，最后的结果刚好可以填满32位的空间**，整体思路就是对与当前构造的cap，找到其二进制最高位，不断左移再进行或运算，通过最高位二进制，将最低为都设置为1，最终最高位到地位全为1，最后再加1就得到了一个2得n次方的数。并且比传进来的cap大
至于为什么要减1，因为如果传进来的cap恰好是一个2的n次方的数，那么会得到这个cap*2，因此要位运算前要减1负载因子和阈值
负载因子static final float DEFAULT_LOAD_FACTOR = 0.75f和阈值int threshold的话是用来给map扩容判断时用的，负载因子也能够在构造函数中进行指定（不推荐），每次进行put的时候都会进行判断是否需要扩容，当size超过了阈值=总容量*负载因子，则会扩容，默认情况下总容量是16，负载因子是0.75，至于为啥是0.75这是由于经过大量的实验证明该系数是最合适的，如果设置过小，HashMap每put少量的数据，都要进行一次扩容，而扩容操作会消耗大量的性能。如果设置过大的话，如果设成1，容量还是16，假设现在数组上已经占用的15个，再要put数据进来，计算数组index时，发生hash碰撞的概率将达到15/16，这违背的HashMap减少hash碰撞的原则。
HashMap构造方法
JDK1.7中的无参构造方法：
/** * Constructs an empty HashMap with the default initial capacity * (16) and the default load factor (0.75). */ public HashMap() { // 负载因子 this.loadFactor = DEFAULT_LOAD_FACTOR; // 阈值：总容量*负载因子 threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); // 存放键值对的entry table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
JDK1.8中的构造方法：
public HashMap() { // 将负载因子设置为默认的0.75f，并没有在构造方法中创建Entry的数组，而是放到put方法中了 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }- 1
- 2
- 3
- 4
- 5
public HashMap(int initialCapacity, float loadFactor) { // 给的初始大小是不是小于0 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); // 是否超过最大容量，是的话则直接赋值最大容量 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; // 给的加载因子是不是个大于0的数字 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
this.threshold = tableSizeFor(initialCapacity);判断指定的初始化容量是否是2的n次幂，如果不是那么会变为比指定初始化容量大的最小的2的n次幂。但是注意，在tableSizeFor方法体内部将计算后的数据返回给调用这里了，并且直接赋值给threshold边界值了。有些人会觉得这里是一个bug，应该这样书写：this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;这样才符合threshold的意思（当HashMap的size到达threshold这个阈值时会扩容）。但是请注意，在jdk8以后的构造方法中，并没有对table这个成员变量进行初始化，table的初始化被推迟到了put方法中，在put方法中会对threshold重新计算。
一个明显区别，jdk1.8在构造时没有初始化table，1.7在构造时就就初始化了
put方法
JDK1.8中的put方法
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 Node<K,V>[] tab; ....... }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
在put方法中又调用了putVal(hash(key), key, value, false, true);以及hash(key)方法，首先我们先来看下hash(key)方法
static final int hash(Object key) { int h; // 如果key是null则hash值为0 //(h = key.hashCode()) ^ (h >>> 16) // 先获取key的hashCode并赋值给h， 然后和h和h右移16位后做异或运算得到hash值 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
这里有个步骤(h = key.hashCode()) ^ (h >>> 16)，为什么要获取完hashCode()赋值给h后要和h右移16位做异或运算呢，直接让h=key.hashCode()不行吗？实际上这是在进行put操作时尽可能的避免hash冲突，前面说过存放元素的时候寻找数组下标实际上是hash值对数组长度取余，当数组长度为2的n次幂时，(n - 1) & hash和hash%n是等价的而且运算效率比取余高，简单来说之所以这么做就是，高 16bit 不变，低 16bit 和高 16bit 做了一个异或（得到的 hashCode 转化为 32 位二进制，前 16 位和后 16 位低 16bit 和高 16bit 做了一个异或）,
hashMap开始是从16开始的，只占了4位二进制，也就是说在32位二进制中，其高位均为0，那么其与hash进行与运算，hash值的高位完全浪费了，因此高16与低16位进行异或运算可以更好的散列hash值。
我们看到真正参与运算的实际上只有最后四位，也就是说其他高位并没有参与运算
那么会出现一种状况，就是调用hashCode()方法获取的值高位不停的在变动但是地位不变，这种状况就会造成(n-1)&hash结果会一致，造成hash冲突。
简单来说就是通过右移16位和异或操作让高位地位都参与了运算尽可能的减少hash冲突接着看putVal方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { /* Node- 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
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
转成红黑树的__treeifyBin()__方法
/** * 转成红黑树 * @param tab * @param hash */ final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; /* 数组tab不为空或者数组长度小于64则进行扩容操作 n = tab.length:数组长度赋值给n */ if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); /* 转成红黑树操作 e = tab[index = (n - 1) & hash])：获取索引位置元素 */ else if ((e = tab[index = (n - 1) & hash]) != null) { /* hd：存放树的头结点 tl：用来存放临时节点 */ TreeNode<K,V> hd = null, tl = null; do { // 将链表节点转成树节点 TreeNode<K,V> p = replacementTreeNode(e, null); /* tl：第一次临时节点必然为空 将p节点赋值给头结点 */ if (tl == null) hd = p; else { /* 临时tl节点不为空： p.prev = tl：将tl赋值给p的prev节点 tl.next = p：将p节点赋值给tl的next节点 */ p.prev = tl; tl.next = p; } // 将p节点赋值给tl节点 tl = p; } while ((e = e.next) != null); // 循环，直到Next节点不存在 /* (tab[index] = hd)：将树的头结点赋值给数组索引位置 */ if ((tab[index] = hd) != null) /* 转成红黑树的具体操作 */ hd.treeify(tab); } }- 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
说明
size表示HashMap中键值对的实时数量，这个不等于数组的长度
threshold（临界值）= capacity（容量）* loadFactor（负载因子）。这个值是当前已占用数组长度的最大值。size 超过这个值就重新 resize（扩容），扩容后的 HashMap 容量是之前容量的两倍。JDK1.7中的put方法
public V put(K key, V value) { /* 如果Key是null的话，则调用putForNullKey方法 putForNullKey：如果不存在null为key的Entry则新增，如果存在的话则替换原来的值并返回 */ if (key == null) return putForNullKey(value); /* key.hashCode()：调用key的hashCode()获取hashCode hash(key.hashCode()):通过调用hash方法获得hash值 这个操作实际上和JDK1.8的HashMap的hash(key)类似，也是通过该方法使得高低位都参与 hash计算从而避免hash冲突，大家可以参考一下上面JDK1.8的HashMap */ int hash = hash(key.hashCode()); /* 这一步是计算出数组的索引下标 计算方法和JDK8一样 */ int i = indexFor(hash, table.length); /* Entry- 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
void addEntry(int hash, K key, V value, int bucketIndex) { /* 获取索引位置的Entry */ Entry<K,V> e = table[bucketIndex]; /* 采用头插法将元素插入到链表中 新节点插入后将e赋值给next */ table[bucketIndex] = new Entry<>(hash, key, value, e); // 判断新增元素后数组大小是否超过阈值 if (size++ >= threshold) // 扩容方法，将扩大为原来数组大小的两倍 resize(2 * table.length); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
扩容resize
首先扩容的时机不同
在1.7中进行初始化或内部当size超过阈值时会触发扩容, 扩容之后的数组大小为之前的两倍, 并且之前该下标的元素只会继续保存在该下标或者两倍的下标位置.
在1.8中扩容触发条件有两个
当初始化或size超过阈值时会触发扩容
一条链表上节点数量超过8时会调用treeifyBin()方法, 方法内部如果数组长度小于64则会触发resize()扩容方法HashMap在进行扩容时，每次扩容后的大小都是原来数组的两倍，然后将原数组中的元素分配到新的数组中去，那么它是如何分配的呢？由于每次进行扩容都是原来大小的两倍，计算table下标的方法是hash&(newTable.length-1)，也就是hash&(oldTable.length*2-1)，于是我们有了这样的结论：这新旧两次计算下标的结果，要不然就相同，要不然就是新下标等于旧下标加上旧数组的长度
其实hash值的对应的新数组下标是不是需要加上旧数组的长度，只需要看看hash值&旧数组长度(hash&oldTable.length)是不是1就行了如果是1的话就是原数组中的位置+原数组长度，0的话就是原数组中的位置
JDK1.7中的扩容方法void resize(int newCapacity) { // 获取源数组 Entry[] oldTable = table; // 原数组容量大小 int oldCapacity = oldTable.length; // 判断原容量大小是否已经是最大值了 if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } // 新建数组大小为原数组大小的两倍 Entry[] newTable = new Entry[newCapacity]; /* 扩容方法的关键，重新计算索引分配位置 */ transfer(newTable); // 新数组替换原数组 table = newTable; // 新阈值 threshold = (int)(newCapacity * loadFactor); } void transfer(Entry[] newTable) { // 源数组 Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { // 将元素赋值给e Entry<K,V> e = src[j]; if (e != null) { // 将原来位置的元素置为null，方便GC src[j] = null; do { Entry<K,V> next = e.next; // 重新计算元素在新数组中的位置 int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } } static int indexFor(int h, int length) { return h & (length-1); }- 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
JDK1.8中的扩容方法
final Node<K, V>[] resize() { // 源数组 Node<K, V>[] oldTab = table; // 原来的数组容量 int oldCap = (oldTab == null) ? 0 : oldTab.length; // 原来数组的阈值 int oldThr = threshold; /* newCap：新数组的容量，初始值为0 newThr：新数组的阈值，初始值为0 */ int newCap, newThr = 0; // 判断原来的数组大小是否不为0 if (oldCap > 0) { /* 原数组的容量已经大于等于最大容量 将最大值赋值给原来的阈值并返回原数组 */ if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } /* (newCap = oldCap << 1)：将原数组左移一位，也就是扩大为原来的2倍并赋值给新容量newCap 新容量小于最大容量值且原数组容量要大于默认的初始容量16则将阈值扩大 */ else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // 阈值扩大一倍 newThr = oldThr << 1; // double threshold } /* 原阈值大于0则赋值给新容量 这里肯能有疑问为啥将原数组阈值大小赋值给新容量？ 看看前面的JDK1.8中的有参构造方法就明白了， 在tableSizeFor方法体内部将计算后的数据直接赋值给threshold边界值了 */ else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults /* 进入else则说明原来数组的容量和阈值都是0，则进行初始化默认值 newCap：赋值初始值16 newThr：新阈值=0.75*16=12 */ newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } /* 新阈值还是初始值0则计算新阈值 */ if (newThr == 0) { // ft = 新容量*负载因子 float ft = (float) newCap * loadFactor; // 新数组容量不超过最大值且ft小于最大值则取ft为新阈值 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE); } // 将新阈值赋值给成员变量threshold threshold = newThr; // 创建新长度的数组newTab @SuppressWarnings({"rawtypes", "unchecked"}) Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap]; // 将新数组赋值给成员变量table table = newTab; if (oldTab != null) { // 遍历原数组，将数据放到新的数组中去 for (int j = 0; j < oldCap; ++j) { // 用来保存遍历中的元素 Node<K, V> e; if ((e = oldTab[j]) != null) { /* 将原数组中索引位置的元素赋值给e后，将索引位置的元素置为null方便GC */ oldTab[j] = null; /* 判断数组是否有下一个引用，如果e.next为空则说明不是链表，直接将元素放到数组中即可 */ if (e.next == null) /* 将原数组中的原素放到新数组中 e.hash & (newCap - 1)：这一步是计算元素放到新数组的索引位置 */ newTab[e.hash & (newCap - 1)] = e; /* 判断是否是红黑树 */ else if (e instanceof TreeNode) // 说明是红黑树来，则调用相关方法处理 ((TreeNode<K, V>) e).split(this, newTab, j, oldCap); else { /* 到了else说明是链表 loHead：下标不变情况下的链表头 loTail：下标不变情况下的链表尾 hiHead：下标改变情况下的链表头 hiTail：下标改变情况下的链表尾 */ Node<K, V> loHead = null, loTail = null; Node<K, V> hiHead = null, hiTail = null; Node<K, V> next; do { // 将e的next节点赋值给next变量 next = e.next; // 这里来判断如果等于true e这个结点在resize之后不需要移动位置，也就是对应数组下标不变，这里也就是判断是不是新索引位置=原数组长度+原数组位置 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);// 将next赋值给e，继续循环直到next为空 // 原索引放到数组中 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } // 原索引+oldCap放到数组中 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
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
一个很重要的区别是，jdk1.7中逻辑，对于所有元素，重新rehash并放到对应的位置，进行头插法
1.8中对于一个hash槽上的链表。遍历table[i]上的链表，如果(e.hash & oldCap) == 0，放入链表中loHead 和loTail 否则放入hiTail和hiHead的链表中 ，lo链表直接位置不变放入新链表中，hi链表当前位置j+oldCap放入新链表中，旧数组的不同槽一定不会重新分到相同的的新槽中,不会冲突，因此可以直接复制头插与尾插
根据前面的代码可以看出来，1.8采用的尾插法，1.7采用的头插法，我们知道头插法性能是要优于尾插法的，那么jdk为什么要弃用头插，使用尾插法
- put元素时为了计算链表长度，判断是否要转为红黑树
JDK1.8 之前使用的是数组+链表，链表就是解决 hash 值冲突的，使用的是头插法。
JDK1.8 后使用的是数组+链表+红黑树，hashmap 的初始容量是 16，加载因子是 0.75,就是 16x0.75=12,就需要扩容，当数组扩容大于 64,且阈值大于 8，链表就会转成红黑树，查询较快，在链表小于阈值 8 时，使用的是尾插法
并且，红黑数的插入新节点，也是作为红节点查到根节点的，也是尾插法
因为当数组扩容大于 64,且阈值大于 8，链表就会转成红黑树，那么实际上尾插法对插入的性能影响时十分小的- rehash时，头插法会打乱节点顺序。容易造成死循环
那么如何产生死循环的，那么看看，回顾resize和transfer方法
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; ... Entry[] newTable = new Entry[newCapacity]; ... transfer(newTable, rehash); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
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; } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
创建一个新的newTable，进入transfer方法。
案例分析
假设HashMap初始化大小为4，插入个3节点，不巧的是，这3个节点都hash到同一个位置，如果按照默认的负载因子的话，插入第3个节点就会扩容，为了验证效果，假设负载因子是1.
以上是节点移动的相关逻辑。
插入第4个节点时，发生rehash，假设现在有两个线程同时进行，线程1和线程2，两个线程都会新建新的数组。
假设 线程2 在执行到Entry
线程1继续执行，很不巧，a、b、c节点rehash之后又是在同一个位置7，开始移动节点
第一步，移动节点a
第二步，移动节点b
注意，这里的顺序是反过来的，继续移动节点c
这个时候 线程1 的时间片用完，内部的table还没有设置成新的newTable， 线程2 开始执行，这时内部的引用关系如下：
可以发现经过扩容rehash之后会，节点顺序反过来了。
这时，在 线程2 中，变量e指向节点a，变量next指向节点b，开始执行循环体的剩余逻辑。Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next;- 1
- 2
- 3
- 4
- 5
执行之后的引用关系如下图
执行后，变量e指向节点b，因为e不是null，则继续执行循环体，执行后的引用关系
变量e又重新指回节点a，只能继续执行循环体，这里仔细分析下：
1、执行完Entry
2、e.next = newTable[i]; 其中 newTable[i] 指向节点b，那就是把a的next指向了节点b，这样a和b就相互引用了，形成了一个环；
3、newTable[i] = e 把节点a放到了数组i位置；
4、e = next; 把变量e赋值为null，因为第一步中变量next就是指向null；
所以最终的引用关系是这样的：
节点a和b互相引用，形成了一个环，当在数组该位置get寻找对应的key时，就发生了死循环。
另外，如果线程2把newTable设置成到内部的table，节点c的数据就丢了，看来还有数据遗失的问题。总结
所以在并发的情况，发生扩容时，可能会产生循环链表，在执行get的时候，会触发死循环，引起CPU的100%问题，所以一定要避免在并发环境下使用HashMap。
曾经有人把这个问题报给了Sun，不过Sun不认为这是一个bug，因为在HashMap本来就不支持多线程使用，要并发就用ConcurrentHashmap
1.8中在扩容时，采用了的尾插法的，头插法扩容不会改变节点顺序，因此无法成环。注意，采用头插法不会解决扩容的线程安全，仅仅是避免成环，在多线程环境下仍然可能会出现很多无法预料的情况！ -
相关阅读:
如何自定义代码生成器（下）
RabbitMQ总结
RabbitMQ的高可用和高可靠
uniapp uni.showToast 一闪而过的问题
在vscode运行java代码
13.计算机网络---应用层之HTTP协议
【mediasoup-sfu-cpp】5: SfuDemo：分发ok
C++ //练习 10.37 给定一个包含10个元素的vector，将位置3到7之间的元素按逆序拷贝到一个list中。
MySQL常用函数
16位ADC的积分非线性做到0.5LSB的难度有多大
- 原文地址：https://blog.csdn.net/qq_37436172/article/details/128163551
