再上次看了hashMap的put方法，了解了大概的流程，今天再来搞搞put中的hash(key) 方法和具体计算下标的方法
1
源码是这样的
static final int hash(Object key) {
int h;
return (key ==null) ?0 : (h = key.hashCode()) ^ (h >>>16);
}
相当于 h^h>>>16
先来了解一下这几个运算符
1．与运算符
与运算符用符号“&”表示，其使用规律如下：
两个操作数中位都为1，结果才为1，否则结果为0，
例如 1111 & 1110 结果为 1110
此种运算中 得到0的概率是0.25 得到1的概率是0.75
2.非运算符
非运算符用符号“|”表示，其使用规律如下：
两个位只要有一个为1，那么结果就是1，否则就为0
例如 1111 & 1110 结果为 1111
此种运算中 得到0的概率是0.75 得到1的概率是0.25
3．异或运算符
异或运算符是用符号“^”表示的，其运算规律是：
两个操作数的位中，相同则结果为0，不同则结果为1。
例如 1111 & 1110 结果为 0001
此种运算中 得到0和1的概率都是0.5
接下来看h>>>16
源码中有这样一个常量
static final int DEFAULT_INITIAL_CAPACITY =1 <<4;// aka 16
1 <<4代表 1*2的4次方
>>> 则代表 无符号右移，忽略符号位，空位都以0补齐
h>>>16 则代表右移16位 即当key的hashCode值小于2的16次方时 h>>>16都为0
h^h>>>16 就是高16位和低16位的异或运算 保证hash散列的平均分布
2.计算下标
if ((p = tab[i = (n -1) & hash]) ==null)
tab[i] = newNode(hash, key, value,null);
tab[I =(n-1)&hash]
此处关注的重点在于为何hashMap的初始化长度是2的4次方 以及resize（）每次都是扩容为原来长度的2倍
（1）我们知道 偶数的二进制最后一位是0 奇数的二进制最后一位是1 ，当（n-1）和hash进行&运算的时候， hash的最后一位不确定， &运算只有当都为1 ，结果才为1，否则结果为0。那么，如果（n-1）是偶数 计算出来的值最后一位肯定为0 必然会导致我们只能使用数组长度的一半 导致资源的浪费，产生大量的hash冲突。而（n-1）为奇数 则会避免这个问题
（2）还有一种说法是 当length为偶数时 可以用&代替%运算 效率高
这点我还没想明白 后面有时间再补充吧
网友评论