ref1: http://blog.csdn.net/fan2012huan/article/details/51097331
ref2: https://zhuanlan.zhihu.com/p/21673805
JDK1.8中,hashMap是以数组、链表和红黑树构成的。数组上的链表长度大于8时,会转换成红黑树。
if ((e.hash & oldCap) == 0) {
...
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
因为扩容时是让容量翻倍,所以原来的数组元素到了扩容后要么放在原位置j,要么放在j+oldCap。用
e.hash & oldCap) == 0
可以判断那一位为0还是1。那一位是0的话放在j, 1的话放在 j+oldCap。 详情见 https://zhuanlan.zhihu.com/p/21673805
通过让高16位于低16位异或,使得在散列的时候,即使数组长度较短(小于2^16),在取余时,hash的生成是与hashcode的高低16位都相关的,使得不同的hashcode不那么容易散列到同一个位置。
n = table.length;
index = (n-1) & hash;
hashtable的散列方式
可以看出,hashtable的散列方式简单暴力多了,就是先和0x7FFFFFFF(Integer中最大的正数,7的二进制是0111,F的二进制是1111,所以连起来就是0后面跟31个1)进行与运算,保证结果是个正数,再取余(否则可能会出现负数进行取余的情况)。这样更容易让不同的hashcode散列到同一个位置。
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 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且是最接近cap的。 javascript:void(null)
这段代码的意义在于让n(cap - 1)的最高位的1与它的右边的所有位都变为1。
比如n为0001xxxx时,通过转换可得到n为00011111。 如此,可以在n+1时使之变为00100000,刚好是
见引用的博客http://blog.csdn.net/fan2012huan/article/details/51097331
根据这段代码的作用,如果cap是2的幂,比如00010000,那么n就是00011111,那么最后得到的n是00011111,n+1便是00100000。正是2的幂。
如果不让cap-1的话,那么00010000经过转换会得到00111111,再+1后得到的是01000000,便是原来的两倍。
简单来说,