admin管理员组文章数量:1612060
1.HashMap几个问题的提出
看过jdk8源码的小火把肯定在第一次看完后就会有疑问,主要疑问在一下几个问题:
2.为什么要用有hashCode()?
不管是在存数据,还是在取数据的时候,均会下调用hash(Object key)这个方法,hash(Object key)源码如下:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
2.1 存的时候
获得hash之后,简单的位运算后就可以直接在数组中定位所在下标的位置。直接定位数组的index存入效率O(1),(当然如果有hash冲突的情况,如果有hash冲突,同样是最快的,只需要另外调用equals()方法做后续比较即可):
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
2.2 取的时候
在取的时候,同样直接定位到数组index的位置获取元素,效率O(1),(当然如果有hash冲突的情况,如果有hash冲突,同样是最快的,只需要另外调用equals()方法做后续比较即可):
(first = tab[(n - 1) & hash]) != null) {
2.3 hashCode()总结
从存取两侧层面可以看使用hashCode()的方式是最快的。没有之一,如果使用遍历数组的方式去查找,黄花菜都凉了,O(n)了大哥。
3.为什么初始容量为16?或者说为什么在构造器中给了一个初始容量大小,它还是会把他修改为大于等于次数的最小2的n次幂的形式?
- 关于容量在哪里用到了?取的时候都会用到,即存取均用到了这行代码:
tab[i = (n - 1) & hash]
上面提到在获取hash之后会做一个简单的位运算。我们分析一下这个为运算:
i = (n - 1) & hash
先给出结论:
- 为了不让下标越界
- 为了hash分布的更均匀
3.1 为了不让下标越界
当capacity = n 为2的幂次的时候,n-1的二进制应该是这种情况,下面看一下二进制的情况:
n= 1000… //以1开头,后面为n个0的情况。
那么n-1= 0111…//以0开头,后面均为1的情况
如:
十进制 | n二进制 | n-1二进制 |
---|---|---|
2 | 10 | 01 |
4 | 100 | 011 |
8 | 1000 | 0111 |
16 | 10000 | 01111 |
32 | 100000 | 011111 |
64 | 1000000 | 0111111 |
128 | 10000000 | 01111111 |
256 | 100000000 | 011111111 |
… | … | … |
(n - 1) & hash :&意为且。均为1则为1,这样就保证这个&运算的结果,永远不可能大于(n - 1)的值,即永远不会大于等于capacity 。最大索引为capacity -1。
3.2 为了hash分布的更均匀
&:对应为之均为1结果才为1.
i = (n - 1) & hash的值,即i的值,怎么保证Node在table中是均匀存放的呢?
反例证明:如果n的值不是2的n次幂的形式,n-1就会出现二进制末尾为0的情况,即:n-1 = ***0(前面n为可以为0或者1),这回造成一个生命现象呢?
索引永远不会落在二进制下边为1结尾的索引上。会有一半的索引为空闲状态,进而会使结尾为0(二进制)的索引上发生hash冲突的概率为原来的2倍。会造成插入和查询的效率损失。
4.tableSizeFor()方法解析
源码:
/**
* 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;
}
先说结论:就是大于等于cap的最小2的n次幂:
cap | 返回值 |
---|---|
1 | 2 |
5 | 8 |
10 | 16 |
22 | 32 |
50 | 64 |
- 先说下为什么要cap - 1:
int n = cap - 1;
让cap-1再赋值给n的目的是另找到的目标值大于或等于原值。例如二进制1000,十进制数值为8。如果不对它减1而直接操作,将得到答案10000,即16。显然不是结果。减1后二进制为111,再进行操作则会得到原来的数值1000,即8。
再分析重头戏,下面的这几行代码:
n |= n >>> 1; 表示:n = (n | n >>> 1)
|或:对应为只要有1几位1
- 分析开始:
假设
- n的二进制为:01xxxxxxxxxxxxxx…
- 右移一位: 001xxxxxxxxxxxxxx…
- 与n求或n的值:011xxxxxxxxxxxxxx…
- 同理, n |= n >>> 2;行执行完后n = 01111xxxxxxxxxxxxxxxxxxxxxxxxxxxx
- 同理, n |= n >>> 4;行执行完后n = 011111111xxxxxxxxxxxxxxxxxxxxxxxx
- 同理, n |= n >>> 8;行执行完后n = 01111111111111111xxxxxxxxxxxxxxxx
- 同理, n |= n >>> 16;行执行完后n = 011111111111111111111111111111111
- 到这里是不是熟悉了,return的时候最后在加1,正好又回到了100000…,前面一个1后面全是0的状态,即此方法返回的就是2的n次幂。
4 乘子31的问题解释
一句话为了让hash的分布更为均匀,他是素数
源码:
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
具体为什么要选择31呢?请参考:【jvm】科普:为什么 String hashCode 方法选择数字31作为乘子https://blog.csdn/happydecai/article/details/80493237
到此分享完毕,有不正确的请多多指正。
本文标签: 帮你几个问题方法HashMaptableSizeFor
版权声明:本文标题:Jdk1.8 HashMap中的几个问题帮你一网打尽:hashCode()、为何初始capacity16扩容为2的幂次、乘子31、tableSizeFor()方法何解? 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1728622231a1166497.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论