HashMap原理(一) 概念和底层架构(2)

entrySet变量为EntrySet实体,定义为变量可保证不重复多次创建,是一个Map.Entry的集合,Map.Entry<K,V>是一个接口,Node类就实现了该接口,因此EntrySet中方法需要操作的数据就是HashMap的Node实体。

public Set<Map.Entry<K,V>> entrySet() { Set<Map.Entry<K,V>> es; return (es = entrySet) == null ? (entrySet = new EntrySet()) : es; } 3. capacity

capacity并不是一个成员变量,但HashMap中很多地方都会使用到这个概念,意思是容量,很好理解,在前面的文中提到了两个常量都与之相关

/** * The default initial capacity - MUST be a power of two(必须为2的幂次). * 默认容量16,举例:飞机上正常的座位所对应的人员数量, */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30(必须为2的幂次,且不能大于最大容量1,073,741,824). * 举例:紧急情况下,如救灾时尽可能快撤离人员,这个时候在保证安全的情况下(允许站立),能运输的人员数 */ static final int MAXIMUM_CAPACITY = 1 << 30;

同时HashMap还具有扩容机制,容量的规则为2的幂次,即capacity可以是1,2,4,8,16,32...,怎么实现这种容量规则呢?

/** * Returns a power of two size for the given target capacity. */ static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

用该方法即可找到传递进来的容量的最近的2的幂次,即

cap = 2, return 2;

cap = 3, return 4;

cap = 9, return 16;

...

大家可以传递值进去自己算一下,先cap-1操作,是因为当传递的cap本身就是2的幂次情况下,假如为4,不减去一最后得到的结果将是传递的cap的2倍。

我们来一行行计算一下:tableSizeFor(11),按规则最后得到的结果应该是16

//第一步:n = 10,转为二进制为00001010 int n = cap - 1; //第二步:n右移1位,高位补0(10进制:5,二进制:00000101),并与n做或运算(有1为1,同0为0),然后赋值给n(10进制:15,二进制:00001111) n |= n >>> 1; //第三步:n右移2位,高位补0(10进制:3,二进制:00000011),并与n做或运算(有1为1,同0为0),然后赋值给n(10进制:15,二进制:00001111) n |= n >>> 2; //第四步:n右移4位,高位补0(10进制:0,二进制:00000000),并与n做或运算(有1为1,同0为0),然后赋值给n(10进制:15,二进制:00001111) n |= n >>> 4; //第五步:n右移8位,高位补0(10进制:0,二进制:00000000),并与n做或运算(有1为1,同0为0),然后赋值给n(10进制:15,二进制:00001111) n |= n >>> 8; //第六步:n右移16位,高位补0(10进制:0,二进制:00000000),并与n做或运算(有1为1,同0为0),然后赋值给n(10进制:15,二进制:00001111) n |= n >>> 16; //第七步:return 15+1 = 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

最终的结果正如预期,算法很牛逼啊,ヽ(ー_ー)ノ,能看懂,但却设计不出来。

4. size变量

size变量记录了Map中的key-value对的数量,在调用putValue()方法以及removeNode()方法时,都会对其造成改变,和capacity区分一下即可。

5. threshold变量和loadFactor变量

threshold为临界值,顾名思义,当过了临界值就需要做一些操作了,在HashMap中临界值“threshold = capacity * loadFactor”,当超过临界值时,HashMap就该扩容了。

loadFactor为装载因子,就是用来衡量HashMap满的程度,默认值为DEFAULT_LOAD_FACTOR,即0.75f,可通过构造器传递参数调整(0.75f已经很合理了,基本没人会去调整它),很好理解,举个例子:

100分的试题,父母只需要你考75分,就给你买一台你喜欢的电脑,装载因子就是0.75,75分就是临界值;如果几年后,试题的分数变成200分了,这个时候就需要你考到150分才能得到你喜欢的电脑了。

总结

本文主要讲解了HashMap中的一些主要概念,同时对其底层数据结构从源码的角度进行了分析,table是一个数据和链表的复合结构,size记录了key-value对的数量,capacity为HashMap的容量,其容量规则为2的幂次,loadFactor为装载因此,衡量满的程度,而threshold为临界值,当超出临界值时就会扩容。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/9deea68828eb7bb0c7ed0c175f17d4f8.html