作者:banli | 来源:互联网 | 2023-02-10 19:42
1:在进行扩容时候,其他线程是否可以进行进行插入操作(多线程环境下可能会导致HashMap进入死循环,此处暂不考虑)?答:首先HashMap就不是一个线程安全的容器,所以在多线程环境下使用就是错误的。
1:在进行扩容时候,其他线程是否可以进行进行插入操作(多线程环境下可能会导致HashMap进入死循环,此处暂不考虑)?
答:首先HashMap就不是一个线程安全的容器,所以在多线程环境下使用就是错误的。其次在扩容时候可以进行插入的,但是不安全。例如:
当主线程在调用transfer方法进行复制元素:
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry e : table) {
while(null != e) {
Entry next = e.next;
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;
}
}
}
此时另一个线程在添加新元素是可以的,新元素添加到table中。如果子线程需要扩容的话可以进行扩容,然后将新容器赋给table。而此时主线程转移元素的工作就是将table中元素转移到newTable中。注意main线程的transfer方法:
如果main线程刚进入transfer方法时候newTable大小是32的话,由于子线程的添加操作导致table此时元素如果有128的话。则128个元素就会存储到大小为32的newTable中(此处不会扩容)。这就会导致HashMap性能下降!!!
可以使用多线程环境进行debug查看即可确定(推荐Idea的debug,的确强大,尤其是Evaluate Expression功能)。
2:进行扩容时候元素是否需要重新Hash?
这个需要具体情况判断,调用initHashSeedAsNeeded方法判断(判断逻辑这里先不介绍)。
/**
* Rehashes the contents of this map into a new array with a
* larger capacity. This method is called automatically when the
* number of keys in this map reaches its threshold.
*
* If current capacity is MAXIMUM_CAPACITY, this method does not
* resize the map, but sets threshold to Integer.MAX_VALUE.
* This has the effect of preventing future calls.
*
* @param newCapacity the new capacity, MUST be a power of two;
* must be greater than current capacity unless current
* capacity is MAXIMUM_CAPACITY (in which case value
* is irrelevant).
*/
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];
//initHashSeedAsNeeded 判断是否需要重新Hash
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
然后进行转移元素:
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//多线程环境下,如果其他线程导致table快速扩大。newTable在此处无法扩容会导致性能下降。但是如果后面有再次调用put方法的话可以再次触发resize。
for (Entry e : table) {
while(null != e) {
Entry next = e.next;
if (rehash) { //判断是否需要重新Hash
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
3:如何判断是否需要重新Hash?
/**
* Initialize the hashing mask value. We defer initialization until we
* really need it.
*/
final boolean initHashSeedAsNeeded(int capacity) {
// hashSeed降低hash碰撞的hash种子,初始值为0
boolean currentAltHashing = hashSeed != 0;
//ALTERNATIVE_HASHING_THRESHOLD: 当map的capacity容量大于这个值的时候并满足其他条件时候进行重新hash
boolean useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
//TODO 异或操作,二者满足一个条件即可rehash
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
// 更新hashseed的值
hashSeed = useAltHashing ? sun.misc.Hashing.randomHashSeed(this) : 0;
}
return switching;
}
4:HashMap在多线程环境下进行put操作如何导致的死循环?