前面一篇文章中初步认识了HashMap ------>> 浅谈HashMap,文章中还有很多细节上的东西没说,包括文章结尾的疑问,本篇文章继续一起探讨HashMap.
本文对HashMap的学习是基于JDK1.8版本.
本文将探讨一下几个问题:
- 1、为什么HashMap的数组初始化长度总是2的整数次幂 : tableSizeFor(int cap)
- 2、哈希算法 : hash()
- 3、HashMap的扩容机制是怎么样的 : resize()
- 4、对于可变对象作为key对象,为什么要重写key对象的equals方法和hashCode方法?
tableSizeFor(int cap)
tableSizeFor(int cap)方法只在以下构造函数使用过,也就是在我们初始化容器的时候,构造器手动传入数组的初始化长度,才会调用此方法来保证数组的长度是2的整数次幂.
public HashMap(int initialCapacity, float loadFactor) {
// 初始化数组长度不能小于0 抛出异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 初始化取 MAXIMUM_CAPACITY (最大值)
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 负载因子不能 小于等于0 或者 不能为null
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// 保证了HashMap的数组长度总是2的整数次幂
this.threshold = tableSizeFor(initialCapacity);
}
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;
}
tableSizeFor(int cap) : 保证了HashMap的数组长度总是2的整数次幂,假如传入的参数 cap 不是2的整数次幂,而该方法可以帮我们转化为2的整数次幂,这么神奇?接下来我们来看看是如何实现的.
第一行代码为什么要cap - 1,这里如果不减1,那么如果cap是2的整数次幂的话,则会扩大到原来的2倍,例如 cap是8(已经满足2的幂了),如果不减1,位运算后则是16,所以要cap - 1的作用体现在这里.
后五行的位运算代码表示 : n 和 n右移(1位\2位\4位\8位\16位) 进行 或运算,下面画图举个例子比较清晰吧.
tableSizeFor(int cap)计算过程
最终保证了数组的初始化长度总是2的整数次幂,但是你发现没有,我们计算的是数组的长度,然而进行赋值的确是阈值 : this.threshold = tableSizeFor(initialCapacity); 这里是赋值给阈值,而不是计算tableSizeFor(initialCapacity) * this.loadFactor,因为数组的长度在第一次扩容的时候(resize),会根据这个阈值重新初始化数组的长度(详细可看下面的扩容方法).
哈希算法: hash()
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hash()计算的hash值是通过 key的hashCode值(h) 和 h右移(>>>)16位 去进行异或(^) 运算 得到, h 是key自带的hashCode()方法计算出来的,而hashCode()方法返回的是一个int类型的散列值,即返回的是32位带符号的int表值(范围从-2147483648到2147483648);也就是说hash值最终是通过 高位16位 和 低位16位 去进行异或运算出来的.
hashCode右移16位,正好是32bit的一半,并且与本身(低16位)进行异或运算;也就是说用key的hashcode值进行高位16位 和 低位16位进行异或运算;这样做的目的是为了混合哈希值的高位和低位,增加低位的随机性.
计算出来的 hash值 和 数组的长度减1 进行 与运算 : (n - 1) & hash 最终得到数组的索引值;
int h = "QRB".hashCode();// 获取key的hashcode值
System.out.println("高位 : " + h);// 打印结果 : 80449
System.out.println("低位 : " + (h >>> 16)); // 打印结果 : 1
int hash = h ^ (h >>> 16);// 计算hash值,高位和低位的异或运算
System.out.println("高低位异或运算(hash值) : " + hash);// 打印结果 : 80448
int index = (16-1) & hash;// 计算索引值,数组长度-1 和 hash值 与运算
System.out.println("数组的长度减少1与hash值(index值) : " + index);// 打印结果 : 0
哈希值计算过程
HashMap的扩容机制: resize()
为什么有扩容机制 : 当HashMap容器中的元素越来越多的时候,哈希冲突的几率也就越来越高(因为数组的长度是固定的),所以为了提高查询的效率,就要对HashMap容器的数组进行扩容.
扩容后原来存放在HashMap容器中的元素发生怎么样的变化 : 扩容的时候原数组中的元素则重新计算其在新数组中的位置.
HashMap中有7个地方用到 resize() 方法,本文中只讲3处: 分别是插入元素的方法: putVal() 该方法用到了2次、转化红黑树的方法 : treeifyBin() 该方法用到了1次,接下来直奔主题.
3次resize代表着不同的情况
3次扩容情况是基于无参构造器初始化,也就是说默认16个桶,阈值为12,负载因子为0.75
- 1.当初始化HashMap的时候(容器是没有元素的),此时还没真正resize,当第一个元素put进去才真正resize
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
- 2.非极端的情况下,容器中put进去的元素个数(size)大于阈值(threshold),则需要resize
if (++size > threshold)
resize();
- 3.极端的情况下,容器put进去的元素前12个(还没触发第二种情况),有8个元素发生哈希冲突形成一个链表,链表长度为8时将触发 treeifyBin() 转化红黑树,但是转化红黑树前如果数组的长度小于MIN_TREEIFY_CAPACITY(64),则暂时不转化红黑树了,而是resize.
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
前两种是正常情况下的resize,而第3种情况则是极端情况下的resize;为什么要数组的长度大于64才进行转红黑树呢 : 红黑树相对于链表还是比较占内存的,节点太少的时候没必要转换红黑树、不仅转换后的数据结构占空间而且转换也需要花费时间,就是说大部分情况下HashMap还是使用链表.
resize()
final Node<K,V>[] resize() {
1. // 局部变量oldTab : 把原先的table赋值给oldTab
Node<K,V>[] oldTab = table;
2. // 局部变量oldCap : 把原先table的长度赋值给oldCap
int oldCap = (oldTab == null) ? 0 : oldTab.length;
3. // 局部变量oldThr : 把原先的阈值(threshold)赋值给oldThr
int oldThr = threshold;
4. // 局部变量newCap, newThr : 初始化新的数组长度和阈值为0
int newCap, newThr = 0;
1、 // 判断原来数组长度oldCap大于0时,说明不是第一次扩容(之前有扩容过了)
if (oldCap > 0) {
2、 // 判断原来数组长度oldCap大于等于MAXIMUM_CAPACITY(1073741824)时,
则阈值取Integer的最大值,并且返回原先的数组,不扩容了,
也就是说当数组长度达到MAXIMUM_CAPACITY的时候,就不扩容了,
HashMap的"最大容量"是MAXIMUM_CAPACITY,阈值则是Integer.MAX_VALUE.
由于扩大容量是原来的两倍,如果MAXIMUM_CAPACITY扩大两倍则就是负数了
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// <<表示左移移，不分正负数，低位补0
3、 // oldCap左移1位,说明长度扩大到原来两倍,并且赋值给newCap,
// 如果满足
// newCap是否小于MAXIMUM_CAPACITY 且
// oldCap 大于等于DEFAULT_INITIAL_CAPACITY(16),
// 则计算 oldThr左移1位,说明阈值扩大到原来两倍,并且赋值给newThr;
// 否则此时的newThr还是0,下面第6步再计算;
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 这里会有疑问,上面的 if条件 oldCap大于0 不满足的情况下,
// 那么这里的 oldThr > 0 肯定也不满足,
// 也就是说先有数组长度大于0的话(走上面的代码块了),肯定会有阈值大于0;
// 但是别忘了还有个构造器它只初始化这个阈值,所以存在这种情况:
// 使用这种构造器初始化的时候,上面的 if条件 oldCap大于0 是不满足的,
// 而是满足这里else if条件 : oldThr > 0;
4、 // 判断旧的阈值oldThr大于0时,直接赋值newCap,此时的newThr还是0,下面第6步再计算;
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
5、// 如果是走到这里,则的第一次扩容,
newCap赋值DEFAULT_INITIAL_CAPACITY(16), newThr赋值 0.75*16 = 12
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
6、// 上面的第3、4步骤出现的情况下,需要计算下newThr
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
7、// 把newThr赋值给阈值(threshold)
threshold = newThr;
8、// 初始化一个新的数组 : newTab 并且把newTab赋值给table
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
9、 // 判断oldTab是否为null,如果不为null,则表示不是第一次扩容,需要把之前的元素重新计算后存进新的table中
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 当前桶(索引值j)存在元素
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
① 当前桶内(索引值j)只有一个元素(不是链表也不算红黑树)
// 直接插入到新桶中
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
② 当前桶内(索引值j)是一棵红黑树
// 则把红黑树中的元素重新定位新的位置
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
③ 当前桶内(索引值j)是一条链表
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// e.hash & oldCap 要么等于0 要么等于1 下面解释为什么
// e.hash & oldCap==0，这是索引不变的链表
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// e.hash & oldCap==1 （这是索引发生变更的链表）
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 高位==1的链表
if (loTail != null) {
// 链表最后得有个null
loTail.next = null;
// 链表头指针放在新桶的相同下标(索引值j)处
newTab[j] = loHead;
}
// 高位==0的链表
if (hiTail != null) {
// 链表最后得有个null
hiTail.next = null;
// 链表头指针放在新桶的(一定为原来基础上j加上oldCap,j+oldCap)处
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
上面的扩容方法中,假设第9步骤中条件成立,则说明table存在元素,不是第一次扩容,那么需要把每个桶里的元素哈希到新的数组中(此时数组已经扩容到原来的两倍了);
每个桶里的元素哈希到新数组中存在三种情况:
1、第一种情况(如代码中的①标记):只存在一个元素,那么这种情况很简单,直接插入到指定的桶内;
2、第二种情况(如代码中的②标记):是一棵红黑树,同样的把红黑树重新定位到新的桶内;
3、第三种情况(如代码中的③标记):是一条链表,也是把链表存到新的桶内 : 我们知道HashMap的tableSizeFor(int cap)方法保证了数组的长度总是2的幂,并且在扩容的时候是数组的长度扩大到原来的2倍,所以,元素的位置要么是在原位置,要么是在原位置上再加上数组的长度(扩容前的数组长度),理解下图你就懂了.
看完该图,其实就是根据判断高位就可以知道链表插入到的是原位置还是原位置加数组长度(原数组的长度).
对于可变对象作为key对象,为什么要重写key对象的equals方法和hashCode方法
浅谈HashMap文章中,我们已经知道HashMap是通过hash函数得到哈希值,然后通过 (n-1) & hash值 (n为数组长度)计算出数组的索引值,如果发生哈希冲突,则需要判断是否存在相同的key对象,而判断相同的key对象需要满足的条件为 : hash值相等 且 key值相等(==和equals),hash值是通过key值的hashCode值的高16位 和 key值的hashCode值的低16位 进行 异或运算得到的,所以当出现哈希冲突时,对于key对象是可变对象,必须重写key对象的equals方法和hashCode方法,不然就无法在HashMap中正常运作了.
其实对于key对象,选择String类是一个很好的选择,因为String类是一个final类,且Java已经帮String类重写了equals方法和hashCode方法,所以直接复用.
HashMap暂时就讲到这里了,文中有讲得不对的地方,希望大佬可以指出来,多谢.
结束语
- 原创不易
- 希望看完这篇文章的你有所收获!
相关参考资料
- JDK1.8