Map大家族的那点事儿(4) :HashMap – 动态扩容与添加元素

java admin 5800 0 评论

动态扩容


散列表以数组的形式组织bucket,问题在于数组是静态分配的,为了保证查找的性能,需要在Entry数量大于一个临界值时进行扩容,否则就算散列函数的效果再好,也难免产生碰撞。

所谓扩容,其实就是用一个容量更大(在原容量上乘以二)的数组来替换掉当前的数组,这个过程需要把旧数组中的数据重新hash到新数组,所以扩容也能在一定程度上减缓碰撞。

HashMap通过负载因子(Load Factor)乘以buckets数组的长度来计算出临界值,算法:threshold = load_factor * capacity。比如,HashMap的默认初始容量为16(capacity = 16),默认负载因子为0.75(load_factor = 0.75),那么临界值就为threshold = 0.75 * 16 = 12,只要Entry的数量大于12,就会触发扩容操作。

还可以通过下列的构造函数来自定义负载因子,负载因子越小查找的性能就会越高,但同时额外占用的内存就会越多,如果没有特殊需要不建议修改默认值。

/**
 * 可以发现构造函数中根本就没初始化buckets数组。
 * (之前说过buckets数组会推迟到第一次调用put()时进行初始化)
 */
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +





 initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +





 loadFactor);
this.loadFactor = loadFactor;
// tableSizeFor()确保initialCapacity必须为一个2的N次方
this.threshold = tableSizeFor(initialCapacity);
}

buckets数组的大小约束对于整个HashMap都至关重要,为了防止传入一个不是2次幂的整数,必须要有所防范。tableSizeFor()函数会尝试修正一个整数,并转换为离该整数最近的2次幂。

/**
 * 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;
}

还记得数组索引的计算方法吗?index = (table.length - 1) & hash,这其实是一种优化手段,由于数组的大小永远是一个2次幂,在扩容之后,一个元素的新索引要么是在原位置,要么就是在原位置加上扩容前的容量。这个方法的巧妙之处全在于&运算,之前提到过&运算只会关注n – 1(n = 数组长度)的有效位,当扩容之后,n的有效位相比之前会多增加一位(n会变成之前的二倍,所以确保数组长度永远是2次幂很重要),然后只需要判断hash在新增的有效位的位置是0还是1就可以算出新的索引位置,如果是0,那么索引没有发生变化,如果是1,索引就为原索引加上扩容前的容量。

这样在每次扩容时都不用重新计算hash,省去了不少时间,而且新增有效位是0还是1是带有随机性的,之前两个碰撞的Entry又有可能在扩容时再次均匀地散布开。下面是resize()的源码:

final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; // table就是buckets数组
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// oldCap大于0,进行扩容,设置阈值与新的容量
if (oldCap > 0) {
// 超过最大值不会进行扩容,并且把阈值设置成Interger.MAX_VALUE
if (oldCap >= MAXIMUM_CAPACITY) {


threshold = Integer.MAX_VALUE;


return oldTab;
}
// 没超过最大值,扩容为原来的2倍
// 向左移1位等价于乘2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

oldCap >= DEFAULT_INITIAL_CAPACITY)


newThr = oldThr << 1; // double threshold
}
// oldCap = 0,oldThr大于0,那么就把阈值做为新容量以进行初始化
// 这种情况发生在用户调用了带有参数的构造函数(会对threshold进行初始化)
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// oldCap与oldThr都为0,这种情况发生在用户调用了无参构造函数
// 采用默认值进行初始化
else {


 // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果newThr还没有被赋值,那么就根据newCap计算出阈值
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;
// 如果oldTab != null,代表这是扩容操作
// 需要将扩容前的数组数据迁移到新数组
if (oldTab != null) {
// 遍历oldTab的每一个bucket,然后移动到newTab
for (int j = 0; j < oldCap; ++j) {


Node<K,V> e;


if ((e = oldTab[j]) != null) {


oldTab[j] = null;


// 索引j的bucket只有一个Entry(未发生过碰撞)


// 直接移动到newTab


if (e.next == null)


newTab[e.hash & (newCap - 1)] = e;


// 如果是一个树节点(代表已经转换成红黑树了)


// 那么就将这个节点拆分为lower和upper两棵树


// 首先会对这个节点进行遍历


// 只要当前节点的hash & oldCap == 0就链接到lower树


// 注意这里是与oldCap进行与运算,而不是oldCap - 1(n - 1)


// oldCap就是扩容后新增有效位的掩码


// 比如oldCap=16,二进制10000,n-1 = 1111,扩容后的n-1 = 11111


// 只要hash & oldCap == 0,就代表hash的新增有效位为0


// 否则就链接到upper树(新增有效位为1)


// lower会被放入newTab[原索引j],upper树会被放到newTab[原索引j + oldCap]


// 如果lower或者upper树的节点少于阈值,会被退化成链表


else if (e instanceof TreeNode)


((TreeNode<K,V>)e).split(this, newTab, j, oldCap);


else { // preserve order


// 下面操作的逻辑与分裂树节点基本一致


// 只不过split()操作的是TreeNode


// 而且会将两条TreeNode链表组织成红黑树


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;


}


else {


if (hiTail == null)




hiHead = e;


else




hiTail.next = e;


hiTail = e;


}


} while ((e = next) != null);


if (loTail != null) {


loTail.next = null;


newTab[j] = loHead;


}


if (hiTail != null) {


hiTail.next = null;


newTab[j + oldCap] = hiHead;


}


}


}
}
}
return newTab;
}

使用HashMap时还需要注意一点,它不会动态地进行缩容,也就是说,你不应该保留一个已经删除过大量Entry的HashMap(如果不打算继续添加元素的话),此时它的buckets数组经过多次扩容已经变得非常大了,这会占用非常多的无用内存,这样做的好处是不用多次对数组进行扩容或缩容操作。不过一般也不会出现这种情况,如果遇见了,请毫不犹豫地丢掉它,或者把数据转移到一个新的HashMap。

添加元素


我们已经了解了HashMap的内部实现与工作原理,它在内部维护了一个数组,每一个key都会经过散列函数得出在数组的索引,如果两个key的索引相同,那么就使用分离链接法解决碰撞冲突,当Entry的数量大于临界值时,对数组进行扩容。

接下来以一个添加元素(put())的过程为例来梳理一下知识,下图是put()函数的流程图:

然后是源码:

public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

 boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// table == null or table.length == 0
// 第一次调用put(),初始化table
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 没有发生碰撞,直接放入到数组
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 发生碰撞(头节点就是目标节点)
if (p.hash == hash &&


((k = p.key) == key || (key != null && key.equals(k))))


e = p;
// 节点为红黑树
else if (p instanceof TreeNode)


e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 节点为链表
else {


for (int binCount = 0; ; ++binCount) {


// 未找到目标节点,在链表尾部链接新节点


if ((e = p.next) == null) {


p.next = newNode(hash, key, value, null);


if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st


// 链表过长,转换为红黑树


treeifyBin(tab, hash);


break;


}


// 找到目标节点,退出循环


if (e.hash == hash &&


((k = e.key) == key || (key != null && key.equals(k))))


break;


p = e;


}
}
// 节点已存在,替换value
if (e != null) { // existing mapping for key


V oldValue = e.value;


if (!onlyIfAbsent || oldValue == null)


e.value = value;


// afterNodeXXXXX是提供给LinkedHashMap重写的函数


// 在HashMap中没有意义


afterNodeAccess(e);


return oldValue;
}
}
++modCount;
// 超过临界值,进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

转载请注明: 飞嗨_分享互联网 » Map大家族的那点事儿(4) :HashMap – 动态扩容与添加元素

赞 (0) or 分享 (0)
游客 发表我的评论   换个身份
取消评论

表情
(0)个小伙伴在吐槽

高效,专业,符合SEO

联系我们