HashMap(JDK1.8)增强扩展

2018-02-27 11:45:58来源:https://www.jianshu.com/p/9823e3b995a8作者:激情的狼王丶21人点击

分享


我们在这篇文章中HashMap源码解析(JDK1.8)对HashMap进行了学习,在此基础上,继续总结HashMap的扩展问题,加深理解。


1.为什么capacity总是2的幂次方?
/**
* HashMap 的table数组默认初始容量为 16,必须为 2 的 n 次方
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

capacity默认为2的4次方,当我们初始化时传入的capacity不是2的次方会发生什么呢?


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的最接近的2的次方值,比如


3—>4
20—>32
100—128

HashMap中存储数据table的index是由key的Hash值决定的.在HashMap存储数据时,我们期望数据能均匀分布,以防止哈希冲突.自然而然我们就会想到去用%取余的操作来实现我们这一构想,取余操作会存在于每次hash计算包括扩容时的重新hash。这里要了解到一个知识:



取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作.



再来看看table的index的计算规则:



index = e.hash & (newCap - 1)
等价于:
index = e.hash % newCap



采用二进制位操作&,相对于%,能够极大地提高运算效率,这就是cap的值被要求为2幂次的原因.


2.哈希碰撞和红黑树

上文中讲到,HashMap是通过计算key的hashCode来找到记录的存储位置的,由于hash函数不会太完美的原因,势必要造成多个记录的key的hashCode一样的情况,完美情况下,我们希望每一个数组位置上仅有一个记录,但是很多情况下一个数组位置上会落入多个记录,也就是哈希冲突。




2059840-8386849414328b14.png

哈希碰撞会对 hashMap 的性能带来灾难性的影响。如果多个 hashCode() 的值落到同一个桶内的时候,这些值是存储到一个链表中的。最坏的情况下,所有的 key 都映射到同一个桶中,这样 hashmap 就退化成了一个链表——查找时间从 O(1) 到 O(n)。
JDK1.8HashMap 的红黑树是这样解决的:HashMap在链表的长度大于8的时候就会将链表转换为红黑树这种数据结构,红黑树的查询效率高达O(lgN),也就是说,复杂度降了一个数量级。如果哈希值相等,HashMap 希望 key 值最好是实现了 Comparable 接口的,这样它可以按照顺序来进行插入。这对 HashMap 的 key 来说并不是必须的,不过如果实现了当然最好。如果没有实现这个接口,在出现严重的哈希碰撞的时候,性能也是很堪忧的。


3.RESIZE扩容优化

在JDK1.7中扩容时,会将所有的元素重新计算hash散列到新的table数组位置,如图




jdk1.7扩容例图.png

JDK1.8对此做了一些优化:



因为我们使用的是2次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。



怎么理解呢?例如我们从16扩展为32时,具体的变化如下所示:




ceb6e6ac-d93b-11e4-98e7-c5a5a07da8c4.png

因此元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色),因此新的index就会发生这样的变化:




519be432-d93c-11e4-85bb-dff0a03af9d3.png

因此,我们在扩充HashMap的时候,不需要重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 超过最大值就不再扩充了,就只好随你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 没超过最大值,就扩充为原来的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算新的resize上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 把每个bucket都移动到新的buckets中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
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;
// 原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}


这个设计确实非常的巧妙,既省去了重新计算hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。



4.hashCode()和equals()

hashCode() 是干嘛的?什么时候重写 equals() 方法啊?
总的来说,Java中的集合(Collection)有两类,一类是List,再有一类是Set。前者集合内的元素是有序的,元素可以重复;后者元素无序,但元素不可重复。要想保证元素不重复,可两个元素是否重复应该依据什么来判断呢?这就是Object.equals方法了。
但是,如果每增加一个元素就检查一 次,那么当元素很多时,后添加到集合中的元素比较的次数就非常多了。也就是说,如果集合中现在已经有1000个元素,那么第1001个元素加入集合时,它就要调用1000次equals方法。这显然会大大降低效率。
Java采用了哈希表的原理。哈希算法也称为散列算法,是将数据依特定算法直接指定到一个地址上。这样一来,当集合要添加新的元素时,先调用这个元素的hashCode方法,就一下子能定位到它应该放置的物理位置上。如果这个位置上没有元素,它就可以 直接存储在这个位置上,不用再进行任何比较了;如果这个位置上已经有元素了,就调用它的equals方法与新元素进行比较,相同的话就不存了;不相同,也就是发生了Hash key相同导致冲突的情况,那么就在这个Hash key的地方产生一个链表,将所有产生相同hashcode的对象放到这个单链表上去,串在一起。所以这里存在一个冲突解决的问题(很少出现)。这样一来实际调用equals方法的次数就大大降低了,几乎只需要一两次。


所以,Java对于eqauls方法和hashCode方法是这样规定的:



1、如果两个对象相等,那么它们的hashCode值一定要相等;
2、如果两个对象的hashCode相等,它们并不一定相等(在同一个链表上)。









最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台