参考博文
JDK1.7的扩容原理及多线程环境下出现的死循环
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
// 扩容后长度将变为原来的2倍
resize(2 * table.length);
// 重新计算hash值
hash = (null != key) ? hash(key) : 0;
// 重新进行索引
bucketIndex = indexFor(hash, table.length);
}
...
}
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
table = newTable;
// 更新阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
注意,多线程环境下,转移元素的过程可能发生死循环,具体参见
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;
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;
}
}
}
多线程环境下Fail-fast机制
尽最大努力抛出异常,但是并不能依次保证程序的正确性
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}
解决方案
方案一:选用JUC包下的ConcurrentHashMap
方案二:选用Collections.synchronizedMap(…)
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) { return new SynchronizedMap<>(m); }