【Java】HashMap源码分析——常用方法详解
程序员文章站
2022-06-27 14:31:54
上一篇介绍了HashMap的基本概念,这一篇着重介绍HasHMap中的一些常用方法:put()get()**resize()** 首先介绍resize()这个方法,在我看来这是HashMap中一个非常重要的方法,是用来调整HashMap中table的容量的,在很多操作中多需要重新计算容量。源码如下: ......
上一篇介绍了hashmap的基本概念,这一篇着重介绍hashmap中的一些常用方法:
put()
get()
**resize()**
首先介绍resize()这个方法,在我看来这是hashmap中一个非常重要的方法,是用来调整hashmap中table的容量的,在很多操作中多需要重新计算容量。
源码如下:
1 final node<k,v>[] resize() { 2 node<k,v>[] oldtab = table; 3 int oldcap = (oldtab == null) ? 0 : oldtab.length; 4 int oldthr = threshold; 5 int newcap, newthr = 0; 6 if (oldcap > 0) { 7 if (oldcap >= maximum_capacity) { 8 threshold = integer.max_value; 9 return oldtab; 10 } 11 else if ((newcap = oldcap << 1) < maximum_capacity && 12 oldcap >= default_initial_capacity) 13 newthr = oldthr << 1; // double threshold 14 } 15 else if (oldthr > 0) // initial capacity was placed in threshold 16 newcap = oldthr; 17 else { // zero initial threshold signifies using defaults 18 newcap = default_initial_capacity; 19 newthr = (int)(default_load_factor * default_initial_capacity); 20 } 21 if (newthr == 0) { 22 float ft = (float)newcap * loadfactor; 23 newthr = (newcap < maximum_capacity && ft < (float)maximum_capacity ? 24 (int)ft : integer.max_value); 25 } 26 threshold = newthr; 27 @suppresswarnings({"rawtypes","unchecked"}) 28 node<k,v>[] newtab = (node<k,v>[])new node[newcap]; 29 table = newtab; 30 if (oldtab != null) { 31 for (int j = 0; j < oldcap; ++j) { 32 node<k,v> e; 33 if ((e = oldtab[j]) != null) { 34 oldtab[j] = null; 35 if (e.next == null) 36 newtab[e.hash & (newcap - 1)] = e; 37 else if (e instanceof treenode) 38 ((treenode<k,v>)e).split(this, newtab, j, oldcap); 39 else { // preserve order 40 node<k,v> lohead = null, lotail = null; 41 node<k,v> hihead = null, hitail = null; 42 node<k,v> next; 43 do { 44 next = e.next; 45 if ((e.hash & oldcap) == 0) { 46 if (lotail == null) 47 lohead = e; 48 else 49 lotail.next = e; 50 lotail = e; 51 } 52 else { 53 if (hitail == null) 54 hihead = e; 55 else 56 hitail.next = e; 57 hitail = e; 58 } 59 } while ((e = next) != null); 60 if (lotail != null) { 61 lotail.next = null; 62 newtab[j] = lohead; 63 } 64 if (hitail != null) { 65 hitail.next = null; 66 newtab[j + oldcap] = hihead; 67 } 68 } 69 } 70 } 71 } 72 return newtab; 73 }
可以看到这段代码非常庞大,其内容可以分为两大部分:
第一部分计算并生成新的哈希表(空表):
1 // 记录原表 2 node<k,v>[] oldtab = table; 3 // 得到原来哈希表的总长度,及原来总容量 4 int oldcap = (oldtab == null) ? 0 : oldtab.length; 5 // 得到原来最佳容量 6 int oldthr = threshold; 7 // 存放新的总容量、新最佳容量的变量 8 int newcap, newthr = 0; 9 if (oldcap > 0) { 10 // 原来总容量达到或超过hashmap的最大容量,则最佳容量设置为int类型的最大值 11 // 且原来容量不变,直接返回,不做后需调整 12 if (oldcap >= maximum_capacity) { 13 threshold = integer.max_value; 14 return oldtab; 15 } 16 // 让新的总容量等于原来容量的二倍 17 else if ((newcap = oldcap << 1) < maximum_capacity && 18 oldcap >= default_initial_capacity) 19 // 新的最佳容量也变为原来的二倍 20 newthr = oldthr << 1; 21 } 22 // 原来总容量为0,将新的总容量设置为最佳容量,构造方法出入参数是一个派生的map的时候,就会使用派生的map计算出新的最佳容量 23 else if (oldthr > 0) 24 newcap = oldthr; 25 else { 26 // 原来总容量和原来最佳容量都没有定义 27 // 新的总容量设为默认值16 28 // 新的最佳容量=默认负载因子×默认容量=0.75×16=12 29 newcap = default_initial_capacity; 30 newthr = (int)(default_load_factor * default_initial_capacity); 31 } 32 // 判断上述操作后新的最佳容量是否计算,若没有,就利用负载因子和新的总容量计算 33 if (newthr == 0) { 34 float ft = (float)newcap * loadfactor; 35 newthr = (newcap < maximum_capacity && ft < (float)maximum_capacity ? 36 (int)ft : integer.max_value); 37 } 38 // 更新当前的最佳容量 39 threshold = newthr; 40 @suppresswarnings({"rawtypes","unchecked"}) 41 // 生成新的哈希表,即一维数组 42 node<k,v>[] newtab = (node<k,v>[])new node[newcap]; 43 // 更新哈希表 44 table = newtab;
可以看出上述操作仅仅是生成了一张大小合适的哈希表,但表还是空的,后面的操作就是把以前的表中的元素重新排列,移动到当前表中合适的位置!
第二部分将原表元素移动到新表合适的位置:
1 // 先判断原表是或否为空 2 if (oldtab != null) { 3 // 遍历原表(一维数组)中的所有元素, 4 for (int j = 0; j < oldcap; ++j) { 5 // 记录原来一维数组中下标为j的元素 6 node<k,v> e; 7 // 只对有效元素进行操作 8 if ((e = oldtab[j]) != null) { 9 //将原表中的元素置空 10 oldtab[j] = null; 11 if (e.next == null) 12 // 当前元素没有后继,那么直接把它放在新表中合适位置 13 // 其中e.hash & (newcap - 1)在我上一篇博客有介绍 14 // 就是以该节点的hash值和新表总容量取余,将余数作为下标 15 newtab[e.hash & (newcap - 1)] = e; 16 else if (e instanceof treenode) 17 // 当前元素有后继,且后继是红黑树 18 // 进行有关红黑树的相应操作 19 // 这里不详细介绍红黑树的操作 20 ((treenode<k,v>)e).split(this, newtab, j, oldcap); 21 else { 22 // 这里就进行有关链表的移动 23 // 这两组结点变量,分别代表两条不同链表的头和尾 24 // 低位的头和尾 25 node<k,v> lohead = null, lotail = null; 26 // 高位的头和尾 27 node<k,v> hihead = null, hitail = null; 28 // 下一节点 29 node<k,v> next; 30 do { 31 // 让next等于当前结点的后继结点 32 next = e.next; 33 // 这个位运算实际上判断的是该节点在新表中的位置是否发生改变 34 // 成立则说明没有改变,还是原来表中下标为j的位置 35 if ((e.hash & oldcap) == 0) { 36 // 若是首结点,则让低位的头等于当前结点 37 if (lotail == null) 38 lohead = e; 39 else 40 // 若不是首结点,则让低位的尾等于当前结点 41 lotail.next = e; 42 // 让低位的尾移动到当前 43 lotail = e; 44 } 45 // 这里就说明其在新表中的位置发生了改变,则要将其放入另一条链表 46 else { 47 // 若是首结点,则让高位的头等于当前结点 48 if (hitail == null) 49 hihead = e; 50 else 51 // 若不是首结点,则让高位的尾等于当前结点 52 hitail.next = e; 53 // 让高位的尾移动到当前 54 hitail = e; 55 } 56 } while ((e = next) != null); 57 // 原来位置的这条链表还存在 58 if (lotail != null) { 59 // 置空低位的尾的next 60 lotail.next = null; 61 // 将该链表的头结点放入新表下标为j的位置,即原表中的原位置 62 newtab[j] = lohead; 63 } 64 // 新位置上的链表存在 65 if (hitail != null) { 66 // 置空高位的尾的next 67 hitail.next = null; 68 // 将该链表的头结点放入新表中下标为j+原表长度的位置 69 newtab[j + oldcap] = hihead; 70 } 71 } 72 } 73 } 74 } 75 return newtab;
链表的移动如图:
可以看出,这个方法可以使得单个结点重新散列,链表可以拆分成两条,红黑树重新移动,这样使得新的哈希表分布比以前均匀!
下面来分析put方法:
源码如下:
1 public v put(k key, v value) { 2 return putval(hash(key), key, value, false, true); 3 }
这里我们可以知道其调用了内部的一个putval方法:
首先第一个参数是通过内部的hash方法(在前一篇博客有介绍过)计算出键对象的hash(int类型)值,再把key和value对象传过去,置于后面两个参数先不着急
先来看下putval方法是如何说明的:
1 /** 2 * implements map.put and related methods 3 * 4 * @param hash hash for key 5 * @param key the key 6 * @param value the value to put 7 * // 看以看出,put方法传入的onlyifabsent是false,那么就会改变原来已存在的值 8 * @param onlyifabsent if true, don't change existing value 9 * // 这个参数先不考虑,往后慢慢分析 10 * @param evict if false, the table is in creation mode. 11 * @return previous value, or null if none 12 */ 13 final v putval(int hash, k key, v value, boolean onlyifabsent, boolean evict)
该方法内容:
1 // 用于保存原表 2 node<k,v>[] tab; 3 // 保存下标为hash的结点 4 node<k,v> p; 5 // n用来记录表长 6 int n, i; 7 // 先检查原表是否存在,或者是空表 8 if ((tab = table) == null || (n = tab.length) == 0) 9 // 如果为空就生成一张大小为16的新表 10 n = (tab = resize()).length; 11 if ((p = tab[i = (n - 1) & hash]) == null) 12 // 如果以该方法形参hash对表长取余,令其作为下标的表中的元素为空,那么就产生一个新结点放在这个位置 13 tab[i] = newnode(hash, key, value, null); 14 else { 15 // 如果该结点不空,那么就会出现两种情况:链表和红黑树 16 node<k,v> e; k k; 17 if (p.hash == hash && 18 ((k = p.key) == key || (key != null && key.equals(k)))) 19 // 如果当前结点的hash并且key值(指针值和内容值)相等,由于onlyifabsent是false,那么就会改变这个结点的v值,先用e将其保存起来 20 e = p; 21 else if (p instanceof treenode) 22 // 如果当前结点是一棵红黑树,那么就进行红黑树的平衡,这里不讨论红黑树的问题 23 e = ((treenode<k,v>)p).puttreeval(this, tab, hash, key, value); 24 else { 25 // 这里就对链表进行操作 26 // 从头开始遍历这条链表 27 for (int bincount = 0; ; ++bincount) { 28 if ((e = p.next) == null) { 29 // 如果该节点的next为空 30 // 就需要新增一个结点追加其后 31 p.next = newnode(hash, key, value, null); 32 if (bincount >= treeify_threshold - 1) // -1 for 1st 33 // 这里进行红黑树阈值的判断,由于treeify_threshold默认值是8,bincount是从0开始,那么当链表长度大于等于8的时候,就将该链表转换成红黑树,并且结束循环 34 treeifybin(tab, hash); 35 break; 36 } 37 // 这里和之前的判断是一样的 38 if (e.hash == hash && 39 ((k = e.key) == key || (key != null && key.equals(k)))) 40 break; 41 // 让p = p->next 42 p = e; 43 } 44 } 45 // 若e非空,则就是说明原表中存在hash值相等,且key的值或内容相同的结点 46 if (e != null) { 47 // 将原来的v值保存 48 v oldvalue = e.value; 49 // 判断是否是需要进行覆盖原来v值的操作 50 if (!onlyifabsent || oldvalue == null) 51 // 覆盖原来的v值 52 e.value = value; 53 // 这个方法是一个空的方法,预留的一个操作,不用去管它 54 afternodeaccess(e); 55 // 由于在这里面的操作只是替换了原来的v值,并没有改变原来表的大小,直接返回oldvalue 56 return oldvalue; 57 } 58 } 59 // 操作数自增 60 ++modcount; 61 // 实际大小自增 62 // 若其大于最佳容量进行扩容的操作,使其分布均匀 63 if (++size > threshold) 64 resize(); 65 // 这也是一个空的方法,预留操作 66 afternodeinsertion(evict); 67 // 并没有替换原来的v值,返回null 68 return null;
下来是get方法,逻辑相对简单不难分析:
1 public v get(object key) { 2 node<k,v> e; 3 return (e = getnode(hash(key), key)) == null ? null : e.value; 4 }
同样也是通过hash方法计算出key对象的hash值,调用内部的getnode方法:
1 final node<k,v> getnode(int hash, object key) { 2 // 记录表对象 3 node<k,v>[] tab; 4 // 记录第一个结点和当前节点 5 node<k,v> first, e; 6 // 记录表长 7 int n; 8 // 记录k值 9 k k; 10 // 表非空或者长度大于0才对其操作 11 // 并且key的hash值对表长取余为下标,其所对应的哈希表中的结点存在 12 if ((tab = table) != null && (n = tab.length) > 0 && 13 (first = tab[(n - 1) & hash]) != null) { 14 // 当前结点满足情况,直接返回给该节点 15 if (first.hash == hash && 16 ((k = first.key) == key || (key != null && key.equals(k)))) 17 return first; 18 // 后面就分为两种情况:在红黑树或者链表中查找 19 if ((e = first.next) != null) { 20 // 当前结点是红黑树,进行红黑树的查找 21 if (first instanceof treenode) 22 return ((treenode<k,v>)first).gettreenode(hash, key); 23 // 进行链表的遍历 24 do { 25 if (e.hash == hash && 26 ((k = e.key) == key || (key != null && key.equals(k)))) 27 return e; 28 } while ((e = e.next) != null); 29 } 30 } 31 return null; 32 }
若有不足还请指出!
我在csdn也放了一篇【java】hashmap源码分析——常用方法详解
推荐阅读
-
iOS常用调试方法之静态分析详解
-
jQuery 源码分析(四) each函数 $.each和$.fn.each方法 详解
-
iOS常用调试方法之静态分析详解
-
【Java】NIO中Selector的select方法源码分析
-
Java基础之Collections框架Map接口实现类HashMap及其源码分析(1)
-
Java编程之HashMap底层源码方法原理(jdk1.8)
-
【Java】HashMap源码分析——基本概念
-
Java容器之HashMap源码分析(妈妈再也不用担心我不懂HashMap了)
-
互联网架构-Java8集合框架源码分析-041:纯手写Jdk7HashMap集合框架
-
Java集合系列[3]----HashMap源码分析