HashMap源码分析1:添加元素
程序员文章站
2022-06-22 12:46:16
本文源码基于JDK1.8.0_45。 代码中涉及的resize方法、红黑树的实现、链表转换成红黑树的逻辑等将在系列其他文章介绍。 ......
本文源码基于jdk1.8.0_45。
1 final v putval(int hash, k key, v value, boolean onlyifabsent, boolean evict) { 2 node<k,v>[] tab; node<k,v> p; int n, i; 3 //延迟初始化数组,这是hashmap中最基础的数据结构 4 if ((tab = table) == null || (n = tab.length) == 0) 5 n = (tab = resize()).length; 6 //数组中hash对应位置没有元素,就把当前元素放入作为头节点,结束put的流程 7 //计算哈希值在数组中的位置时,使用了数组容量-1与哈希值做与运算的方式,保留了哈希值的低位数据作为数组下标 8 if ((p = tab[i = (n - 1) & hash]) == null) 9 tab[i] = newnode(hash, key, value, null); 10 else { 11 node<k,v> e; k k; 12 //如果头节点的key值相等,则头节点是目标元素 13 if (p.hash == hash && 14 ((k = p.key) == key || (key != null && key.equals(k)))) 15 e = p; 16 //如果头节点是一个树节点,表示该数据结构是红黑树,则调用红黑树的方法查找或添加目标元素 17 else if (p instanceof treenode) 18 e = ((treenode<k,v>)p).puttreeval(this, tab, hash, key, value); 19 //最后判断该数据结构为链表,并在链表中查找key相等的元素 20 else { 21 for (int bincount = 0; ; ++bincount) { 22 //链表中不存在该key值,将新值添加到链表末端,如果链表长度达到阈值需要转换为红黑树 23 //treeifybin方法中生成红黑树有一个条件,如果数组长度太小,只会先执行扩容操作,当数组长度达到生成树的阈值时才会执行生成红黑树的逻辑 24 if ((e = p.next) == null) { 25 p.next = newnode(hash, key, value, null); 26 if (bincount >= treeify_threshold - 1) // -1 for 1st 27 treeifybin(tab, hash); 28 break; 29 } 30 //如果在链表中找到目标节点,则中断循环 31 if (e.hash == hash && 32 ((k = e.key) == key || (key != null && key.equals(k)))) 33 break; 34 p = e; 35 } 36 } 37 //如果hashmap中不存在目标元素,前面的代码逻辑已经将元素添加进了map中 38 //如果hashmap中存在目标元素,则视情况选择是否更新旧的值 39 if (e != null) { // existing mapping for key 40 v oldvalue = e.value; 41 if (!onlyifabsent || oldvalue == null) 42 e.value = value; 43 afternodeaccess(e); 44 return oldvalue; 45 } 46 } 47 /** 48 * 如果新增了节点,最后还需要更新节点的数量,如果超过阈值则需要对hashmap进行数组扩容,并重新分配节点所在的数组 49 * 扩容的原因在于数组的长度一定,当元素的哈希值碰撞时,会以链表或红黑树的形式存储,元素的数量太多会影响hashmap的读写效率 50 * 因此需要对数组进行扩容,使元素更加分散,减少链表的长度或红黑树的高度。 51 */ 52 ++modcount; 53 if (++size > threshold) 54 resize(); 55 afternodeinsertion(evict); 56 return null; 57 }
代码中涉及的resize方法、红黑树的实现、链表转换成红黑树的逻辑等将在系列其他文章介绍。