HashMap详解之Put源码解析

>>16进行异或操作，高16bit补0，一个数和0异或不变，所以hash函数的一个作用是，高16位不变，低16位和高16位做一个异或，目的是减少碰撞，按照源码中的注释，因为bucket数据大小是2的幂，计算index=(table.length-1)&hash,如果不做hash处理，相当于散列生效的只有几个低bit位，为了减少散列的碰撞，所以使用高16bit和低16bit异或处理来减少碰撞。","marks":[]}]}],"state":{}},{"type":"block","id":"kzif-1670912039883","name":"paragraph","data":{"version":1},"nodes":[{"type":"text","id":"q6AR-1670912039876","leaves":[{"text":"put方法的执行流程图：","marks":[]}]}],"state":{}},{"type":"block","id":"6sfU-1670912071273","name":"paragraph","data":{"version":1},"nodes":[{"type":"text","id":"xi2c-1670912071272","leaves":[{"text":"","marks":[]}]}],"state":{}},{"type":"block","id":"yrnD-1670912072011","name":"image","data":{"version":1,"url":"https://note.youdao.com/yws/public/resource/6023374f5b6aa5f6a3fd19b96833b3b1/xmlnote/WEBRESOURCE6f1b28e8f7197e6036e6469f52ceb509/1785","width":1074,"height":647},"nodes":[],"state":{"renderSource":"https://note.youdao.com/yws/public/resource/6023374f5b6aa5f6a3fd19b96833b3b1/xmlnote/WEBRESOURCE6f1b28e8f7197e6036e6469f52ceb509/1785","initialSize":{"width":1074,"height":647},"loading":false}},{"type":"block","id":"vaJ1-1670912072014","name":"paragraph","data":{"version":1},"nodes":[{"type":"text","id":"aNyY-1670912072013","leaves":[{"text":"","marks":[]}]}],"state":{}},{"type":"block","id":"8eF9-1670912372854","name":"code","data":{"version":1,"language":"","theme":"default"},"nodes":[{"type":"block","id":"VKmw-1670912372741","name":"code-line","data":{},"nodes":[{"type":"text","id":"zs70-1670912372740","leaves":[{"text":"public V put(K key, V value) {","marks":[]}]}]},{"type":"block","id":"oPNs-1670912372743","name":"code-line","data":{},"nodes":[{"type":"text","id":"QSLO-1670912372742","leaves":[{"text":" return putVal(hash(key), key, value, false, true);","marks":[]}]}]},{"type":"block","id":"WQNs-1670912372745","name":"code-line","data":{},"nodes":[{"type":"text","id":"UjJw-1670912372744","leaves":[{"text":"}","marks":[]}]}]},{"type":"block","id":"KfbP-1670912372747","name":"code-line","data":{},"nodes":[{"type":"text","id":"MPqs-1670912372746","leaves":[{"text":"","marks":[]}]}]},{"type":"block","id":"yjkp-1670912372749","name":"code-line","data":{},"nodes":[{"type":"text","id":"Foxa-1670912372748","leaves":[{"text":"//实现map的put方法","marks":[]}]}]},{"type":"block","id":"Och5-1670912372770","name":"code-line","data":{},"nodes":[{"type":"text","id":"zdK1-1670912372769","leaves":[{"text":"final V putVal(int hash, K key, V value, boolean onlyIfAbsent,","marks":[]}]}]},{"type":"block","id":"b1Ey-1670912372772","name":"code-line","data":{},"nodes":[{"type":"text","id":"Z2lq-1670912372771","leaves":[{"text":" boolean evict) {","marks":[]}]}]},{"type":"block","id":"sC3d-1670912372774","name":"code-line","data":{},"nodes":[{"type":"text","id":"lq0b-1670912372773","leaves":[{"text":" Node[] tab; Node p; int n, i;","marks":[]}]}]},{"type":"block","id":"o2VO-1670912421739","name":"code-line","data":{},"nodes":[{"type":"text","id":"hKvO-1670912421737","leaves":[{"text":" //步骤1：tab为空则进行创建","marks":[]}]}]},{"type":"block","id":"dZEW-1670912436402","name":"code-line","data":{},"nodes":[{"type":"text","id":"huER-1670912436400","leaves":[{"text":" //table未初始化或者长度0，进行扩容","marks":[]}]}]},{"type":"block","id":"keSw-1670912372776","name":"code-line","data":{},"nodes":[{"type":"text","id":"vVJA-1670912372775","leaves":[{"text":" if ((tab = table) == null || (n = tab.length) == 0)","marks":[]}]}]},{"type":"block","id":"LiFu-1670912372778","name":"code-line","data":{},"nodes":[{"type":"text","id":"N7R0-1670912372777","leaves":[{"text":" n = (tab = resize()).length;","marks":[]}]}]},{"type":"block","id":"GjK6-1670912460989","name":"code-line","data":{},"nodes":[{"type":"text","id":"Ic8c-1670912460988","leaves":[{"text":" //步骤2，计算index,并对null进行处理","marks":[]}]}]},{"type":"block","id":"lt1W-1670912482415","name":"code-line","data":{},"nodes":[{"type":"text","id":"ZLPG-1670912482413","leaves":[{"text":" // (n ‐ 1) & hash 确定元素存放在哪个节点中，节点为空，新生成结点放入节点中(此时，这个结点是放在数组中)","marks":[]}]}]},{"type":"block","id":"dEVw-1670912372780","name":"code-line","data":{},"nodes":[{"type":"text","id":"d3CJ-1670912372779","leaves":[{"text":" if ((p = tab[i = (n - 1) & hash]) == null)","marks":[]}]}]},{"type":"block","id":"toJ5-1670912372782","name":"code-line","data":{},"nodes":[{"type":"text","id":"6YpN-1670912372781","leaves":[{"text":" tab[i] = newNode(hash, key, value, null);","marks":[]}]}]},{"type":"block","id":"JKfU-1670912504849","name":"code-line","data":{},"nodes":[{"type":"text","id":"ssR2-1670912504848","leaves":[{"text":" ","marks":[]}]}]},{"type":"block","id":"126p-1670912505075","name":"code-line","data":{},"nodes":[{"type":"text","id":"CxeP-1670912505074","leaves":[{"text":"//如果节点中已经存在元素，","marks":[]}]}]},{"type":"block","id":"FLl8-1670912372784","name":"code-line","data":{},"nodes":[{"type":"text","id":"sTkx-1670912372783","leaves":[{"text":" else {","marks":[]}]}]},{"type":"block","id":"KfMa-1670912372786","name":"code-line","data":{},"nodes":[{"type":"text","id":"VJgI-1670912372785","leaves":[{"text":" Node e; K k;","marks":[]}]}]},{"type":"block","id":"wM1W-1670912534367","name":"code-line","data":{},"nodes":[{"type":"text","id":"Vtgt-1670912534366","leaves":[{"text":" //步骤3：节点Key存在，直接覆盖value","marks":[]}]}]},{"type":"block","id":"qKuq-1670912548766","name":"code-line","data":{},"nodes":[{"type":"text","id":"0Zrg-1670912548765","leaves":[{"text":" // 比较节点中第一个元素(数组中的结点)的hash值相等，key相等","marks":[]}]}]},{"type":"block","id":"TDbv-1670912372788","name":"code-line","data":{},"nodes":[{"type":"text","id":"GJ74-1670912372787","leaves":[{"text":" if (p.hash == hash &&","marks":[]}]}]},{"type":"block","id":"8Lnu-1670912372790","name":"code-line","data":{},"nodes":[{"type":"text","id":"FIBm-1670912372789","leaves":[{"text":" ((k = p.key) == key || (key != null && key.equals(k))))","marks":[]}]}]},{"type":"block","id":"DfQ7-1670912578113","name":"code-line","data":{},"nodes":[{"type":"text","id":"1OXu-1670912578111","leaves":[{"text":" //将第一个元素赋值给e，用e来记录","marks":[]}]}]},{"type":"block","id":"dXix-1670912372792","name":"code-line","data":{},"nodes":[{"type":"text","id":"ihEs-1670912372791","leaves":[{"text":" e = p;","marks":[]}]}]},{"type":"block","id":"MUKL-1670912605659","name":"code-line","data":{},"nodes":[{"type":"text","id":"9fl7-1670912605658","leaves":[{"text":"//步骤4：判断是否是红黑树","marks":[]}]}]},{"type":"block","id":"xnAG-1670912649542","name":"code-line","data":{},"nodes":[{"type":"text","id":"OOyl-1670912649540","leaves":[{"text":"//如果当前元素类型位TreeNode，表示为红黑树，putTreeval返回待存放的node,e可能为null","marks":[]}]}]},{"type":"block","id":"1k6o-1670912372794","name":"code-line","data":{},"nodes":[{"type":"text","id":"0Isw-1670912372793","leaves":[{"text":" else if (p instanceof TreeNode)","marks":[]}]}]},{"type":"block","id":"408l-1670912715384","name":"code-line","data":{},"nodes":[{"type":"text","id":"tBmj-1670912715383","leaves":[{"text":" //放入树中","marks":[]}]}]},{"type":"block","id":"BL1k-1670912372796","name":"code-line","data":{},"nodes":[{"type":"text","id":"DqsL-1670912372795","leaves":[{"text":" e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);","marks":[]}]}]},{"type":"block","id":"7rvN-1670912726802","name":"code-line","data":{},"nodes":[{"type":"text","id":"KRxz-1670912726801","leaves":[{"text":" //步骤5：该链为链表","marks":[]}]}]},{"type":"block","id":"Cf7p-1670912372798","name":"code-line","data":{},"nodes":[{"type":"text","id":"XgmM-1670912372797","leaves":[{"text":" else {","marks":[]}]}]},{"type":"block","id":"7Nyx-1670912744373","name":"code-line","data":{},"nodes":[{"type":"text","id":"Ke1P-1670912744372","leaves":[{"text":" //再链表最末端插入节点","marks":[]}]}]},{"type":"block","id":"T1W7-1670912372800","name":"code-line","data":{},"nodes":[{"type":"text","id":"qCmM-1670912372799","leaves":[{"text":" for (int binCount = 0; ; ++binCount) {","marks":[]}]}]},{"type":"block","id":"4nLw-1670912759533","name":"code-line","data":{},"nodes":[{"type":"text","id":"IVea-1670912759531","leaves":[{"text":" //到达链表的尾部","marks":[]}]}]},{"type":"block","id":"IQPj-1670912769511","name":"code-line","data":{},"nodes":[{"type":"text","id":"z5zD-1670912769509","leaves":[{"text":" //判断该链表尾部指针是不是空的","marks":[]}]}]},{"type":"block","id":"YayL-1670912372802","name":"code-line","data":{},"nodes":[{"type":"text","id":"IVW1-1670912372801","leaves":[{"text":" if ((e = p.next) == null) {","marks":[]}]}]},{"type":"block","id":"XinM-1670912783211","name":"code-line","data":{},"nodes":[{"type":"text","id":"YFt3-1670912783210","leaves":[{"text":" //再尾部插入新节点","marks":[]}]}]},{"type":"block","id":"sJnM-1670912372804","name":"code-line","data":{},"nodes":[{"type":"text","id":"LpDB-1670912372803","leaves":[{"text":" p.next = newNode(hash, key, value, null);","marks":[]}]}]},{"type":"block","id":"cszc-1670912797548","name":"code-line","data":{},"nodes":[{"type":"text","id":"5emj-1670912797546","leaves":[{"text":" //判断链表的长度是否达到转化红黑树的临界值，临界值为8","marks":[]}]}]},{"type":"block","id":"Jo1s-1670912372806","name":"code-line","data":{},"nodes":[{"type":"text","id":"pWA0-1670912372805","leaves":[{"text":" if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st","marks":[]}]}]},{"type":"block","id":"L3Ur-1670912816965","name":"code-line","data":{},"nodes":[{"type":"text","id":"ru5d-1670912816964","leaves":[{"text":" //链表结构转红黑树结构","marks":[]}]}]},{"type":"block","id":"WaFP-1670912372808","name":"code-line","data":{},"nodes":[{"type":"text","id":"2j8R-1670912372807","leaves":[{"text":" treeifyBin(tab, hash);","marks":[]}]}]},{"type":"block","id":"DVxY-1670912831463","name":"code-line","data":{},"nodes":[{"type":"text","id":"GwIu-1670912831462","leaves":[{"text":" //跳出循环。","marks":[]}]}]},{"type":"block","id":"ATLS-1670912372810","name":"code-line","data":{},"nodes":[{"type":"text","id":"nelY-1670912372809","leaves":[{"text":" break;","marks":[]}]}]},{"type":"block","id":"BMy7-1670912372812","name":"code-line","data":{},"nodes":[{"type":"text","id":"voXo-1670912372811","leaves":[{"text":" }","marks":[]}]}]},{"type":"block","id":"IS21-1670912843257","name":"code-line","data":{},"nodes":[{"type":"text","id":"rLOh-1670912843256","leaves":[{"text":" //判断链表中的节点的key值和插入的元素的key值是否相等。","marks":[]}]}]},{"type":"block","id":"7thb-1670912372814","name":"code-line","data":{},"nodes":[{"type":"text","id":"4w2Z-1670912372813","leaves":[{"text":" if (e.hash == hash &&","marks":[]}]}]},{"type":"block","id":"Gprl-1670912372816","name":"code-line","data":{},"nodes":[{"type":"text","id":"gJUo-1670912372815","leaves":[{"text":" ((k = e.key) == key || (key != null && key.equals(k))))","marks":[]}]}]},{"type":"block","id":"BhEj-1670912869091","name":"code-line","data":{},"nodes":[{"type":"text","id":"DYVY-1670912869090","leaves":[{"text":" //相等，则跳出循环","marks":[]}]}]},{"type":"block","id":"1Fyd-1670912372818","name":"code-line","data":{},"nodes":[{"type":"text","id":"ntat-1670912372817","leaves":[{"text":" break;","marks":[]}]}]},{"type":"block","id":"wb8y-1670912887628","name":"code-line","data":{},"nodes":[{"type":"text","id":"4byR-1670912887627","leaves":[{"text":" //用于遍历节点中的链表","marks":[]}]}]},{"type":"block","id":"insG-1670912372820","name":"code-line","data":{},"nodes":[{"type":"text","id":"7u7M-1670912372819","leaves":[{"text":" p = e;","marks":[]}]}]},{"type":"block","id":"2fuF-1670912372822","name":"code-line","data":{},"nodes":[{"type":"text","id":"y424-1670912372821","leaves":[{"text":" }","marks":[]}]}]},{"type":"block","id":"sEkI-1670912372824","name":"code-line","data":{},"nodes":[{"type":"text","id":"Xqx6-1670912372823","leaves":[{"text":" }","marks":[]}]}]},{"type":"block","id":"xLh2-1670912934631","name":"code-line","data":{},"nodes":[{"type":"text","id":"xhWd-1670912934629","leaves":[{"text":" //判断当前的key已经存在的情况下，再来一个相同的hash值、key值时，返回新来的value这个值","marks":[]}]}]},{"type":"block","id":"vYvw-1670912372826","name":"code-line","data":{},"nodes":[{"type":"text","id":"cHMj-1670912372825","leaves":[{"text":" if (e != null) { // existing mapping for key","marks":[]}]}]},{"type":"block","id":"uy7F-1670912372828","name":"code-line","data":{},"nodes":[{"type":"text","id":"fCr6-1670912372827","leaves":[{"text":" V oldValue = e.value;","marks":[]}]}]},{"type":"block","id":"uoVU-1670912372830","name":"code-line","data":{},"nodes":[{"type":"text","id":"LAKy-1670912372829","leaves":[{"text":" if (!onlyIfAbsent || oldValue == null)","marks":[]}]}]},{"type":"block","id":"PyUg-1670912970601","name":"code-line","data":{},"nodes":[{"type":"text","id":"p8P3-1670912970599","leaves":[{"text":" //用新值替换旧值。","marks":[]}]}]},{"type":"block","id":"3Ofa-1670912372832","name":"code-line","data":{},"nodes":[{"type":"text","id":"wPvT-1670912372831","leaves":[{"text":" e.value = value;","marks":[]}]}]},{"type":"block","id":"V0uR-1670912943284","name":"code-line","data":{},"nodes":[{"type":"text","id":"Hc4n-1670912943283","leaves":[{"text":" //访问后回调 ","marks":[]}]}]},{"type":"block","id":"y5nZ-1670912372834","name":"code-line","data":{},"nodes":[{"type":"text","id":"vBB1-1670912372833","leaves":[{"text":" afterNodeAccess(e);","marks":[]}]}]},{"type":"block","id":"Lpfk-1670912959191","name":"code-line","data":{},"nodes":[{"type":"text","id":"Y5Xt-1670912959190","leaves":[{"text":" //返回旧值","marks":[]}]}]},{"type":"block","id":"gfEK-1670912372836","name":"code-line","data":{},"nodes":[{"type":"text","id":"aXVp-1670912372835","leaves":[{"text":" return oldValue;","marks":[]}]}]},{"type":"block","id":"Wdy0-1670912372838","name":"code-line","data":{},"nodes":[{"type":"text","id":"1fVe-1670912372837","leaves":[{"text":" }","marks":[]}]}]},{"type":"block","id":"rRPQ-1670912372840","name":"code-line","data":{},"nodes":[{"type":"text","id":"mMX3-1670912372839","leaves":[{"text":" }","marks":[]}]}]},{"type":"block","id":"WVLB-1670912372842","name":"code-line","data":{},"nodes":[{"type":"text","id":"x9BX-1670912372841","leaves":[{"text":" ++modCount;","marks":[]}]}]},{"type":"block","id":"26H9-1670912992585","name":"code-line","data":{},"nodes":[{"type":"text","id":"HbMo-1670912992583","leaves":[{"text":" //步骤6：超过最大容量就扩容","marks":[]}]}]},{"type":"block","id":"H6HJ-1670913005004","name":"code-line","data":{},"nodes":[{"type":"text","id":"VSLG-1670913005002","leaves":[{"text":" ","marks":[]}]}]},{"type":"block","id":"ieme-1670912372844","name":"code-line","data":{},"nodes":[{"type":"text","id":"IU0L-1670912372843","leaves":[{"text":" if (++size > threshold)","marks":[]}]}]},{"type":"block","id":"LXu1-1670912372846","name":"code-line","data":{},"nodes":[{"type":"text","id":"Htez-1670912372845","leaves":[{"text":" resize();","marks":[]}]}]},{"type":"block","id":"H4w2-1670913012247","name":"code-line","data":{},"nodes":[{"type":"text","id":"12Tg-1670913012246","leaves":[{"text":" //插入后回调","marks":[]}]}]},{"type":"block","id":"ygzv-1670912372849","name":"code-line","data":{},"nodes":[{"type":"text","id":"Z4CZ-1670912372848","leaves":[{"text":" afterNodeInsertion(evict);","marks":[]}]}]},{"type":"block","id":"JhWc-1670912372851","name":"code-line","data":{},"nodes":[{"type":"text","id":"WVDE-1670912372850","leaves":[{"text":" return null;","marks":[]}]}]},{"type":"block","id":"IiHa-1670912372853","name":"code-line","data":{},"nodes":[{"type":"text","id":"RHfy-1670912372852","leaves":[{"text":"}","marks":[]}]}]}],"state":{"language":"java"}},{"type":"block","id":"cJVq-1670912073011","name":"list-item","data":{"listId":"6ers-1670913063184","listType":"ordered","listLevel":1},"nodes":[{"type":"text","id":"9zCr-1670912073010","leaves":[{"text":".判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；","marks":[{"type":"color","value":"#4d4d4d"},{"type":"fontSize","value":16}]}]}],"state":{"index":1}},{"type":"block","id":"27yT-1670913065522","name":"list-item","data":{"listId":"6ers-1670913063184","listType":"ordered","listLevel":1},"nodes":[{"type":"text","id":"NXgV-1670913065521","leaves":[{"text":"根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向6，如果table[i]不为空，转向3","marks":[{"type":"color","value":"#4d4d4d"},{"type":"fontSize","value":16}]}]}],"state":{"index":2}},{"type":"block","id":"r8Wc-1670913080727","name":"list-item","data":{"listId":"6ers-1670913063184","listType":"ordered","listLevel":1},"nodes":[{"type":"text","id":"suxH-1670913080726","leaves":[{"text":"判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向4，这里的相同指的是hashCode以及equals；","marks":[{"type":"color","value":"#4d4d4d"},{"type":"fontSize","value":16}]}]}],"state":{"index":3}},{"type":"block","id":"N1V6-1670913097199","name":"list-item","data":{"listId":"6ers-1670913063184","listType":"ordered","listLevel":1},"nodes":[{"type":"text","id":"uj2a-1670913097198","leaves":[{"text":"判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向5；","marks":[{"type":"color","value":"#4d4d4d"},{"type":"fontSize","value":16}]}]}],"state":{"index":4}},{"type":"block","id":"uyhi-1670913123074","name":"list-item","data":{"listId":"6ers-1670913063184","listType":"ordered","listLevel":1},"nodes":[{"type":"text","id":"hXck-1670913123073","leaves":[{"text":"遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；","marks":[{"type":"color","value":"#4d4d4d"},{"type":"fontSize","value":16}]}]}],"state":{"index":5}},{"type":"block","id":"C9LA-1670913132796","name":"list-item","data":{"listId":"6ers-1670913063184","listType":"ordered","listLevel":1},"nodes":[{"type":"text","id":"iL27-1670913132795","leaves":[{"text":"插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容","marks":[{"type":"color","value":"#4d4d4d"},{"type":"fontSize","value":16}]}]}],"state":{}}]">

Put方法

当我们put的时候，首先计算Key的hash值，这里调用了hash方法，hash方法实际是让key.hashCode(）与key.hashCode()>>>16进行异或操作，高16bit补0，一个数和0异或不变，所以hash函数的一个作用是，高16位不变，低16位和高16位做一个异或，目的是减少碰撞，按照源码中的注释，因为bucket数据大小是2的幂，计算index=(table.length-1)&hash,如果不做hash处理，相当于散列生效的只有几个低bit位，为了减少散列的碰撞，所以使用高16bit和低16bit异或处理来减少碰撞。

put方法的执行流程图：

1. .判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；

2. 根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向6，如果table[i]不为空，转向3

3. 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向4，这里的相同指的是hashCode以及equals；

4. 判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向5；

5. 遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；

6. 插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容