HashMap JDK7 扩容机制 和 ConcurrentmodificationException 异常
JDK7扩容机制
HashMap扩容的目的:让链表缩短
在往hashmap里面 put 数据时,hashmap会根据自己内部的逻辑进行扩容
当map中元素的个数 size 大于他的阈值( capacity * LoadFacter => 数组大小 * 负载系数 ),并且当前索引所在位置不为null 才进行扩容 ,扩容是成二倍扩容
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
Hashmap resize方法
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
从代码中可以看到,如果原有的 table 达到了上限,就不能在继续扩容
如果还未达到上限就会调用 transfer 方法
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
// 如果生成了hashseed 就重新进行hash
// 基本上默认 false
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
transfer 方法就是把原本 table中的元素 转移到 扩容后的 table 中,使用头插法,也就是说,新table中链表的顺序和旧列表中是相反的,在HashMap线程不安全的情况下,这种头插法可能会导致环状节点
在转移table,原有 table 的每个元素所对应的索引,在扩容后的 newTable 中可能会发生改变,因为在 table 扩容后,根据hashcode计算索引的 indexFor方法 中的 h 也会发生改变,二进制位高位会增加一位,但是即便发生改变,该索引也是有规律的,原有的索引上的元素,只会在 原索引 或 愿索引+扩容大小 所对应的索引上。
indexFor方法
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
注意:这种逆序的扩容方式在多线程时有可能出现环形链表,出现环形链表的原因大概是这样的:线程1准备处理节点,线程二把HashMap扩容成功,链表已经逆向排序,那么线程1在处理节点时就可能出现环形链表
HashMap resize方法里的 initHashSeedAsNeeded(newCapacity)方法
/**
* Initialize the hashing mask value. We defer initialization until we
* really need it.
*/
final boolean initHashSeedAsNeeded(int capacity) {
boolean currentAltHashing = hashSeed != 0;
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
这个方法,判断 capacity的这个值,根据我所获取到的值来判断需不需要生成hashseed,
当 capacity的值大于某个值时,就生成一个hashseed,让hash算法的散列性,更高一点,如果不知道,则hashseed为默认值 Integer.MAX_VALUE
hashseed 的作用,让hash算法更加的复杂,让所得到的hash值更加散列
ConcurrentmodificationException异常
本文地址:https://blog.csdn.net/qq_41965731/article/details/109565811
上一篇: js实现倒计时效果
下一篇: Vue—强制刷新子组件