IdentityHashMap为何会丢失已存入的Key？

问题描述 #

我知道IdentityHashMap并非线程安全的数据结构，测试用例失败并不意外，但原本以为非并发、非同步Map的线程不安全问题仅体现为put与get之间无happens-before关系，读取线程可能无法看到值的完整字段。但实际遇到的情况是提前存入的键值直接丢失：

在测试代码中，主线程先将mainKey存入IdentityHashMap，随后启动多线程并发执行put操作，等待所有线程结束后，部分场景下调用map.get(mainKey)会返回null。重复执行100次测试，平均10-20次失败；若初始化时设置较大的expectedMaxSize，所有测试都会通过，怀疑是扩容逻辑导致的问题。

测试代码 #

import org.junit.jupiter.api.RepeatedTest;

import java.util.IdentityHashMap;
import java.util.Map;
import java.util.Objects;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;

import static org.junit.jupiter.api.Assertions.assertNotNull;
import static org.junit.jupiter.api.Assertions.assertTrue;

class IdentityHashmapTest {

    static class Key {
        final String description;

        Key(String description) {
            this.description = description;
        }

        @Override
        public String toString() {
            return "Key{" +
                    "description='" + description + '\'' +
                    '}';
        }

        @Override
        public boolean equals(Object o) {
            return this == o;
        }

        @Override
        public int hashCode() {
            return Objects.hash(description);
        }
    }

    @RepeatedTest(100)
    void testConcurrency() throws InterruptedException {
        final Map<Key, Integer> map = new IdentityHashMap<>();
        Key mainKey = new Key("main");
        map.put(mainKey, 1);
        ExecutorService executor = Executors.newFixedThreadPool(4);
        assertNotNull(map.get(mainKey));
        for (int i = 0; i <= 5; i++) {
            executor.submit(() -> {
                for (int j = 1; j <= 5; j++) {
                    map.put(new Key("random"), ThreadLocalRandom.current().nextInt());
                }
            });
        }
        executor.shutdown();
        assertTrue(executor.awaitTermination(30, TimeUnit.SECONDS));
        assertNotNull(map.get(mainKey));
    }
}

根因分析 #

1. IdentityHashMap的特殊实现与扩容逻辑 #

IdentityHashMap和常规HashMap的底层实现差异很大：

• 它以对象的内存地址作为哈希判断依据（而非hashCode()返回值，即使你的Key类重写了hashCode()，IdentityHashMap也不会使用它）；
• 底层数组同时存储键和值：偶数索引位置存键，相邻的奇数索引存对应的值；
• 扩容触发阈值为当前容量的2/3，扩容时会将数组容量翻倍，并重新将所有键值对迁移到新数组中。

2. 并发扩容的竞态条件 #

当多个线程同时执行put操作时，极有可能同时触发扩容逻辑，此时会出现以下致命问题：

• 数组引用的竞态替换：线程A正在将旧数组的元素迁移到新数组时，线程B可能已经完成扩容并将IdentityHashMap的底层数组引用替换为自己的新数组，导致线程A迁移的元素全部丢失，包括提前存入的mainKey；
• 元素迁移的覆盖/遗漏：多个线程同时迁移元素时，可能在新数组的同一位置写入不同元素，或者某个线程的迁移操作被其他线程打断，导致部分元素（如mainKey）没有被写入新数组；
• 无同步的内存可见性：IdentityHashMap的数组引用和元素写入都没有volatile语义或锁保护，线程对数组的修改无法保证被其他线程及时看到，主线程最终读取到的可能是未完成迁移的数组版本，其中mainKey已经被错误清除。

3. 大初始容量测试通过的原因 #

当设置足够大的expectedMaxSize时，整个测试过程中IdentityHashMap不会触发扩容，所有put操作都是在原数组上进行。虽然仍然存在线程安全问题，但由于主线程等待所有线程终止后才读取（线程终止的happens-before规则保证主线程能看到线程的写入结果），因此mainKey不会丢失。

内容的提问来源于stack exchange，提问作者Adwait Kumar