Map-HashMap源码解析：put源码解析-->如何放入红黑树->hash表和红黑树分别如何扩容

>>和>>>的区别：对于正数而言，>>和>>>没有区别>>:带符号右移。正数右移高位补0，负数右移高位补1。>>>：无符号右移。无论正数还是负数，高位通通补0。4>>1，结果为2；-4>>1，结果为-2.因为-4的补码是11111100，>>1是11111110，而1111110取反为0000001，再加1等于00000010。再加上符号最后结果就是-2 对于正数而言，>>和>>>没有区别。对于负数而言，-2>>>1，结果是2147483647（Integer.MAX_VALUE）-1>>>1，结果是2147483647（Integer.MAX_VALUE）

第一次put时，table字段还是null，因此会调用resize初始化

.....

该HashMap被结构修改的次数。此字段用于使HashMap的Collection-view上的迭代器快速失败。 结构修改是那些更改HashMap中的映射数或以其他方式修改其内部结构（例如rehash）的修改。 transient int                                       ;

初始化一个元素oldTab[j] = null;

B

判断放入新元素后是否需要扩容

n-1

e 为oldTab[j]

Node<E> node(int index) {       //二进制位运算，向右移除一位。比如size是4，0100位运算后是010也就是2.比如size是6，0110位运算后是011也就是3.        if (index < (size >> 1)) {            Node<E> x = first;            for (int i = 0; i < index; i++)                x = x.next;            return x;        } else {            Node<E> x = last;            for (int i = size - 1; i > index; i--)                x = x.prev;            return x;        }    }

判断map中是否有值oldCap > 0

threshold

if (e != null) { //将老值替换为新值//onlyIfAbsent:hashmap调用该方法时固定传的false       V oldValue = e.value;       if (!onlyIfAbsent || oldValue == null)        e.value = value;       afterNodeAccess(e);       return oldValue; }

1

该方法右边有详解

loHead = e;

索引不变的树节点：只有第一次进来时，没有设置lo树的头节点时，才会进这里：将对前节点设置为Head和Tail

加载因子static final float                                                  = 0.75f;

return newTab

loTail.next = e;

ArrayList：add和remove方法底层，在删除元素或插入元素的时候，都是通过直接copy数组来完成的。所以更消耗资源

在扩容时，e.hash & bit==0时，新索引=老索引e.hash & bit!=0时，新索引=老索引+老数组长度。原理见上面的详解

HashMap类解析

2、“|”按位或运算符：运算规则：参与运算的数字，低位对齐，高位不足的补零，对应的二进制位有一个为1则为1，否则为0，1和任何数或运算都是1。eg：9|3=1001|0011=1011=11

判断目标索引位的元素是否是树节点else if (p instanceof TreeNode)

链表：为了解决hash冲突。1.7是头插法，就是将位置上原来的元素移除，将新的放进去，再通过next指向原来的那个元素。1.8为了解决头插法在多线程的死循环，改用了尾部插入。

目标索引位的元素赋值给p

if ((p = tab[i = (n - 1) & hash]) == null)

Y

N

涉及到的基础运算符：

HashMap扩容源码图解

 //2的倍数向左偏移一位，就等于再乘以2，这个阈值都是2的倍数因此新的下次要调整大小的阈值等于 老的下次要调整大小的阈值乘以2 newThr = oldThr << 1;

数组是采用一段        的存储单元来存数据的。特点：查询快，增删慢。因为数组是连续存储的，每次查询直接根据索引查询即可，但是如果是增删数据时，比删除中间位置元素，就需要将根据索引找到然后将元素移除，而且中间元素后面的元素都要全部向前移动一位。新增一个元素到中间位置，还需要判断数组是否需要扩容，如果已经满了，还要将数组长度扩容，然后将新增元素放到中间，然后后面的元素都往后移动。

俩个逻辑是一样的，只是放到不同的树里，来区分索引是否要发生变化。

2n-1

table

(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)

哈希表的负载因子 默认为0.75final float                              ;

put方法

N代表目标索引位还没转成树

对的，比如hash值是7的元素，老数组长度为2，新数组长度为4，那么原索引就是7&（2-1）=1，计算新索引：e.hash & (新数组长度- 1)计算的结果是3，（原索引+老数组长度）结果也是3.

核心逻辑总结：如果hash表的元素小于64，就进行扩容，如果已经大于等于64了，就将hash表转成树，即所有元素转成树节点

                   loTail = e;                    记录放到低位树的节点个数，用于下面树转链表的判断依据++lc;

2

扩容后，红黑树的节点的索引为啥是原索引+老数组长度？难道是按e.hash & (新数组长度- 1)计算的结果和（原索引+老数组长度）算的一样，所以为了提高效率才直接用这种原索引+老数组长度的方式计算的？省去了求hash的过程。

MAXIMUM_CAPACITY

此映射中包含的键-值映射的数量。    transient int                ;

二进制正负数转化规则：负数的二进制=正数二进制取反再加1(逢二进一)。正数的二进制=负数二进制取反再加1(逢二进一)。比如4二进制是00000100，4进行取反结果11111011，再加1后结果为11111100，就是-4的二进制结果。首位是1就是负数，首位是0的就是正数。

将当前节点放入新表中newTab[e.hash & (newCap - 1)] = e;

最大容量，如果由具有参数。必须是2的幂<=1<<30。1的30次方是最大值。static final int                                         = 1 << 30;

半分查找法

TREEIFY_THRESHOLD

n

java.util.HashMap#resize()初始化和每次扩容都会调用的方法

next

modCount

第一次到这里，loTail肯定为null，这里就将这个节点作为低位树的首节点和尾节点，第二次循环取得这个节点的下一个节点传进来，每次都放到之前尾节点的next，并赋值低位树的尾部节点为传进来的当前节点。

②下个节点不为空，再判断当前节点是否是树节点，即链表是否已经升级为红黑树

e.hash & (newCap - 1)计算出当前节点索引如果e的下一个节点为null，就直接将e根据新表的索引来计算hash确定其位置放入新表中

oldThr > 0

索引不变的树节点：设置头节点后，会一直进到这里

使用新hash表容量创建新的hash表，并完成指向

oldTab != null

核心逻辑总结：首先进到这里的，肯定是与目标索引位元素p的key不一样，因此要判断目标索引位还有其他元素，有其他元素再跟其他元素比对key，只有在都不一样的情况下才是新元素，再往里面放，否则就是老元素替换Value值的。

链表：链表是一种物理存储单元上非连续、非顺序的存储结构。每个节点通过next来指向下一个节点。特点：查询慢(时间复杂度是O(n))。增删改快(时间复杂度是O(1))。链表的查询是从第一个节点一直next向下查找。删除，只需要将节点的前节点的next置空。插入就是直接获取last节点，并next指向创建的新节点即可。增删改快是通过指定索引的，如果是直接指定节点值，就需要先查询找到节点，再进行操作，这样就更慢了。

成功放置元素后计数器加1++modCount;

// 定义低位树lo和高位树hi的首尾节点

3

创建一个新节点指向目标索引位

//源码中判断其实是当链表长度大于等于7，且数组节点大于64就会转换成红黑树

4 * TREEIFY_THRESHOLD

afterNodeInsertion

初始化常量

LinkedList：add方法就是直接获取链表的last属性，然后将last的next指向创建的新节点。remove(index):先根据索引通过二分查找法找到指定节点，然后移除。remove(value):循环遍历依次比较，然后找到节点进行删除。

TreeNode

因为&运算的规则：二进制相同位值上的数都为1时，结果才是1，其他时候都是0

扩容进来的，老表才不为空，将老表的元素赋给新表

//源码中是当小于等于6时，就将树转换成链表。

区别就是2bit-1的倒数第n+1位是1，而bit-1的倒数第n+1位是0。其他位置都是一样的。前面的都是0，后面的都是1 。

如果老hash表是空，就直接返回新hash表，如果不是就将老的进行循环遍历放到新的hash表中，再返回

数组到hash的演变

if ((e.prev = loTail) == null)

hashMap

map新创建的，都没有进行初始化的，进行初始化  

UNTREEIFY_THRESHOLD

只赋值了偏离因子，初始化常量

DEFAULT_LOAD_FACTOR

只有LinkedHashMap才对这俩方法进行了实现，其他map该方法体是空，留作扩展点

③else重新规整红黑树，通过循环重新建一个树

扩容后，数组元素如果是红黑树的，e.hash & 新数组长度为0的红黑树的所有节点，索引还是原索引，索引不为0的红黑树的所有节点的索引=原索引+原数组长度n源码详见：java.util.HashMap#resizejava.util.HashMap.TreeNode#split如果不是红黑树，就按新表最大索引数来计算其应该放到索引位置：e.hash & (新数组长度- 1)

直接将目标索引位的元素指向新节点ee = p;

DEFAULT_INITIAL_CAPACITY

下一个要调整大小的大小值（容量*负载系数）如果尚未分配表数组，则此字段保留初始数组容量，或零表示DEFAULT_INITIAL_CAPACITY。）int                            ;

4、“~”按位非运算：按位非也叫做补，其实就是对二进制 先取反，再+1并添加上符号，就可以得到结果。运算规则：只操作一个数字，将该数字中1变成0，0变成1。eg:~3=-4的计算过程：    3的二进制形式为0000 0000 0000 0000 0000 0000 0000 0011      取反后：1111 1111 1111 1111 1111 1111 1111 1100      由于取反后得到的是一个负数的存贮形式，而负数时以补码的形式存贮，所以补码取反加1，转为十进制，再添加上符号就得到十进制形式的值。      即：          取反加1后的结果：1111 1111 1111 1111 1111 1111 1111 1100 + 1 =  0000 0000 0000 0000 0000 0000 0000 0100          转为成十进制并添加上符号，即最后的结果为：-4

loadFactor

如果是第一次进来初始化的，老表肯定是空，就可以直接将新表返回

①判断当前节点的下个节点是否为空

判断key对应的位置是否有值:(n - 1) & hash求得索引位

默认初始容量-必须是2的幂

if ((tab = table) == null || (n = tab.length) == 0)//初始化        n = (tab = resize()).length;

hash算法：就是把任意长度值(Key)通过散列算法变换成固定长度的key（地址），通过这个地址进行访问的数据结构，它通过把关键码值映射到表中一个。位置来访问记录，以加快查找的速度。任何值的hashCode是不会变的，数组扩容也只是改变了取模的底，改变的位置，不会是hash值。

oldTab[j] = null;

afterNodeAccess

超过了最大容量2的30次方oldCap >= MAXIMUM_CAPACITY

不为null

//判断低位区树是否需要转成链表，并进行转换if (loHead != null) {     if (lc <= UNTREEIFY_THRESHOLD)//小于等于6就通过for循环将树中的节点依次取出放到链表中，并返回放到链表的loHead节点，赋值给新表          tab[index] = loHead.untreeify(map);      else {            tab[index] = loHead;            if (hiHead != null)            loHead.treeify(tab);//形成从该节点链接的节点树。        }}

0

将老表的元素置为null便于gc回收

java.util.HashMap#split()红黑树扩容调用的方法

判断当前节点是否为null，如果为null直接跳过进行下一次循环

负数的二进制计算需要注意;负数计算时，注意不要直接用八位二进制码进行计算，要清楚二级制是32位比如上面的-4位11111100，只是为了写着方便，其实应该是1..........11111100。当计算-4>>>1时，错误计算：直接用11111100计算，右移一位结果是01111110【126】正确计算：用32位的1..........11111100计算，右移一位结果是01..........1111110【2的30次方+......+2的1次方=2的31次方-2】

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

获取hash值：

                                                       。1(0000 0001)向左偏移四位=0001 0000=16  // 1左偏移几位就是2的几次方  static final int                                                    = 1 << 4;

newThr == 0

e.next == null

一个单词，取得对应的ASCII码。然后取模，算出hash表的下标。比如499取10的模是9，那么数组长度就固定到10，就可以存下.而不会为了存下499而创建一个499长度的数组。但是取模结果相同的数据，会出现hash冲突。解决办法：在数组的每个元素都是一个链表，这样就可以解决。但是链表过长，链表是从头部遍历的，会导致查询效率变低。所以在jdk1.8引入了红黑树。当加载因子超过0.75，就将链表转成红黑树。

用于在调整大小操作期间取消树状化(拆分)仓位的仓位计数阈值。应小于                                     ，最多为6才能在移除时检测到收缩。static final int                                           = 6;

原理分析

字段

多线程并发put时的死循环：

5

Warehouse将树仓中的节点拆分为上树仓和下树仓，如果现在太小，则将节点拆分为非树仓。仅从resize调用

判断低位区树是否需要转成链表，并进行转换

threshold = newThr;

n+3

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

map是空的，但已设置下次扩容的阈值(就是下次需要扩容时的指定的hash容量大小)，就赋值给map的hash表容量。 newCap = oldThr;

e instanceof TreeNode

map源码中不是取模，而是拿hashCode进行是通过&运算的

判断是否目标索引位的元素p的hash与当前元素的hash一样且key也一样。

存储箱可以树化的最小表容量。(否则，如果存储箱中的节点太多，则调整表的大小。)应至少为                                                ，以避免调整大小和树化阈值之间的冲突。static final int                                                 = 64;

4

//需要扩容到最大->设置下次调整大小阈值为Integer.MAX_VALUE(2的31次方-1)threshold = Integer.MAX_VALUE;return oldTab;

在多线程put扩容时，会因为头插法导致链表节点倒置。A指向B，B又指回A。死循环。

因此在扩容时，e.hash & bit==0时，新索引=老索引e.hash & bit!=0时，新索引=老索引+老数组长度

为存储箱使用树而不是列表的存储箱计数阈值。将元素添加到至少有这么多节点的容器时，容器将转换为树。该值必须大于2，并且至少应为8，以符合树木移除中关于收缩后转换回普通垃圾箱的假设。static final int                                         = 8; 

if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))

MIN_TREEIFY_CAPACITY

for循环

无操作

C

对上面得出的新树进行

treeifyBin

n+2

3、“^”按位异或运算符：运算规则：参与运算的数字，低位对齐，高位不足的补零，对应的二进制位相同为零，不相同为1。eg：9^3=1001^0011=1010=10

entrySet

最终都要将新阈值newThr赋值给hashMap用来存储下次扩容时的扩容阈值全局变量threshold

已经不能扩了，直接将老表返回

1、“&”按位与运算符：运算规则：参与运算的数字，低位对齐，高位不足的补零，对应的二进制位都为1，则运算结果为1，否则为0，因为任何数与0都得0。   eg：9&3=1001(9的二进制值)&0011(3的二进制值)=0001(1的二进制值为0001)

size

获取当前节点的next节点，再将当前节点的next指向null

HashMap核心方法源码解析put是最复杂的，因此这里对put进行了全链路解析

this.loadFactor = DEFAULT_LOAD_FACTOR;当前map的属性字段还都是null

连续

节点是如何放入红黑树中的

Y代表已经转树节点了，放到树里

扩容后索引发生变化的：新索引=老索引+老数组长度

数组

循环取红黑树上的节点，判断要查分的红黑树的树节点是否变索引位置(e.hash & bit==0)，如果是就放到低位树，否则放到高位树

为null代表之前这个索引位上没有元素，直接放即可

其实还是到达8就扩容：如果超过7，算上节点p就是8个了，当同一个位置上链表中的元素达到8个的时候，就会再将这些元素构建成一个红黑树

afterNodeInsertion(evict);

 if (hiHead != null) {      if (hc <= UNTREEIFY_THRESHOLD)//小于等于6就通过for循环将树中的节点依次取出放到链表中，并返回放到链表的hiHead节点           tab[index + bit] = hiHead.untreeify(map);       else {            tab[index + bit] = hiHead;            if (loHead != null)                 hiHead.treeify(tab);//形成从该节点链接的节点树。            }       }}

扩容后索引不变的树节点

链表

判断高位区树是否需要转成链表，并进行转换

n+1

if ((e = oldTab[j]) != null)

resize方法比较复杂下面会有详解

resize()

if ((e.hash & bit) == 0)

(h = key.hashCode()) ^ (h >>> 16)这种算法是测出来hash碰撞最合适的算法，目的就是为了减少hash碰撞。先获取hashCode，和hashCode向右偏移16位的结果，然后两者进行按位异或运算。

A

相关基础

数组是0到n-1，长度为n

运算规则：参与运算的数字，低位对齐，高位不足的补零，对应的二进制位都为1，则运算结果为1，否则为0，因为任何数与0都得0。