TL; DR
Согласно предложению Xaerxess , использует Maps # synchronizedBiMap в случае, если к карте обращаются несколько потоков. Никогда не знаешь, что может случиться, когда есть несколько потоков.
Для тех, кому интересно, что произошло
Будет ли какая-то причина, по которой HashBiMap.get будет go в цикл для поиска значения ключа, который никогда не возвращается.
Это интересный пример того, как несколько потоков создают «неожиданный» результат.
Давайте посмотрим на строку HashBiMap. java: 223 метода seekByKey
private BiEntry<K, V> seekByKey(@Nullable Object key, int keyHash) {
for (BiEntry<K, V> entry = hashTableKToV[keyHash & mask];
entry != null;
entry = entry.nextInKToVBucket) {
if (keyHash == entry.keyHash && Objects.equal(key, entry.key)) {
return entry;
}
}
return null;
}
И строка 223:
entry = entry.nextInKToVBucket) {
Блокировка в этой строке означает, что существует бесконечное l oop, что связано с циклическими ссылками entry и entry.nextInKToVBucket.
Один из возможных случаев: в методе put,
private V put(@Nullable K key, @Nullable V value, boolean force) {
...
BiEntry<K, V> newEntry = new BiEntry<>(key, keyHash, value, valueHash);
if (oldEntryForKey != null) {
...
} else {
insert(newEntry, null);
rehashIfNecessary();
return null;
}
}
предположим, к сожалению есть два вызова с одним и тем же ключом и значением из двух потоков одновременно, созданы две новые записи A и B. Затем в методе insert,
private void insert(BiEntry<K, V> entry, @Nullable BiEntry<K, V> oldEntryForKey) {
int keyBucket = entry.keyHash & mask; // 1
entry.nextInKToVBucket = hashTableKToV[keyBucket]; // Step 2
hashTableKToV[keyBucket] = entry; // 3
...
}
Предположим, что A завершается первым, hashTableKToV[keyBucket] = A, A.nextInKToVBucket = ноль. когда B приходит и завершает шаг 2, B.nextInKToVBucket = A. Предположим, перед выполнением шага 3 поток A выполняет rehashIfNecessary, и, к сожалению, требуется reha sh.
private void rehashIfNecessary() {
BiEntry<K, V>[] oldKToV = hashTableKToV;
if (Hashing.needsResizing(size, oldKToV.length, LOAD_FACTOR)) {
int newTableSize = oldKToV.length * 2;
this.hashTableKToV = createTable(newTableSize); // Step 4
...
for (BiEntry<K, V> entry = firstInKeyInsertionOrder;
entry != null;
entry = entry.nextInKeyInsertionOrder) {
insert(entry, entry); // step 5
}
...
}
}
По завершении шага 4 hashTableKToV удаляется. Не повезло, что поток B выполняет шаг 3 в этот момент и hashTableKToV[keyBucket] = B. Поток A продолжается с шага 5, который снова вставляет A, и A.nextInKToVBucket = A после шага 2, вызывая циклическую ссылку. И, следовательно, бесконечное l oop в seekByKey.
Вот пример того, как воспроизвести вышеуказанный случай (не 100%, возможно, придется попробовать несколько раз):
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import com.google.common.collect.BiMap;
import com.google.common.collect.HashBiMap;
public class HashBiMapConcurrentTest {
public static void main(String[] args) throws InterruptedException {
BiMap<String, String> biMap = HashBiMap.create();
ExecutorService executors = Executors.newFixedThreadPool(4);
Collection<Callable<Integer>> tasks = new ArrayList<>();
Callable<Integer> task = () -> {
for (int i = 0; i < 1000; i++) {
biMap.put("A" + i, "B" + i);
biMap.get("A" + i);
}
System.out.println("Done");
return 0;
};
tasks.add(task);
tasks.add(task);
List<Future<Integer>> futures = executors.invokeAll(tasks);
for (Future<Integer> future : futures) {
while (!future.isDone()) {
Thread.sleep(10);
}
}
executors.shutdown();
}
}