#HashMap 线程不安全表现

// 两个线程同时 put，hash 冲突时
// 假设 key1 和 key2 的 hash 值相同，桶中已有 key1

// 线程1: e = table[i] (key1)
// 线程2: e = table[i] (key1)
// 线程1: table[i] = newNode(key2, value2)  // key2 覆盖了 key1 的位置
// 线程2: e.next = newNode(key3, value3)   // e.next 被修改，但 key2 丢了！

// 模拟数据丢失场景
public class HashMapDataLoss {
    public static void main(String[] args) throws InterruptedException {
        HashMap<Integer, Integer> map = new HashMap<>(16);

        // 100 个线程，每个 put 1000 次
        // 使用相同的 key range，大量 hash 冲突
        Thread[] threads = new Thread[100];
        for (int t = 0; t < 100; t++) {
            threads[t] = new Thread(() -> {
                for (int i = 0; i < 1000; i++) {
                    // hash 值固定，产生大量冲突
                    map.put(i, i);
                }
            });
            threads[t].start();
        }

        for (Thread t : threads) t.join();

        System.out.println("Expected: " + (100 * 1000)); // 100000
        System.out.println("Actual: " + map.size()); // 通常小于 100000
        // 实际结果通常在 90000-99000 之间，有数据丢失！
    }
}

// JDK 7：扩容时 transfer 使用头插法
// 多线程同时扩容时，链表节点顺序会反转
// 如果两个线程同时处理同一个桶中的链表，可能形成环形链表

void transfer(Entry[] newTable) {
    for (Entry<K, V> e = table[i]; e != null; ) {
        Entry<K, V> next = e.next;
        e.next = newTable[i]; // 头插：链表反转
        newTable[i] = e;
        e = next;
    }
}

// 两个线程同时执行：
// 原链表：A -> B -> C -> null
// 线程1: e=A, next=B, e.next=null, newTable[0]=A, e=B
// 线程2: e=A, next=B, e.next=A(被线程1修改！), newTable[0]=A, e=B
// 线程2: e=B, next=C, e.next=A, newTable[0]=B, e=C
// 线程2: e=C, next=null, e.next=B(被线程1修改！), newTable[0]=C, e=null
// 结果链表：C -> B -> A -> A（环形！）

// HashMap 的 size 字段不是 volatile
// 多线程 put 时，size++ 不是原子操作
transient int size;

// size++ 的字节码：
// getfield size      // 读取 size
// iconst_1          // 常量 1
// iadd              // 加法
// putfield size     // 写回
// 这三步之间可能被其他线程打断

// 两个线程同时 size++：
// 线程1: getfield size -> 0
// 线程2: getfield size -> 0
// 线程1: iadd -> 1
// 线程2: iadd -> 1
// 线程1: putfield size -> 1
// 线程2: putfield size -> 1
// 期望 size=2，实际 size=1

// ConcurrentHashMap 的改进：

// 1. size 用 CAS 更新，而不是直接++
private final LongAdder counter = new LongAdder();
public int size() {
    long sum = 0;
    for (LongAdder cell : counter.cells) {
        sum += cell.sum();
    }
    return (sum >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int) sum;
}

// 2. JDK 8 使用 synchronized + CAS 代替分段锁
// 3. JDK 8 扩容支持多线程并发 transfer

// ❌ 错误配置
@Bean
public CacheManager cacheManager() {
    // 静态 HashMap 作为缓存
    return new ConcurrentMapCacheManager("data",
        Collections.singletonMap("data",
            new ConcurrentMapCache<>("data", new HashMap<>())));
}

// ✅ 正确配置
@Bean
public CacheManager cacheManager() {
    // 使用 ConcurrentHashMap 作为缓存存储
    return new ConcurrentMapCacheManager(
        new ConcurrentHashMap<>());
}

// ❌ 错误：多线程使用 HashMap 统计
Map<String, Integer> counter = new HashMap<>();
for (DataItem item : data) {
    String key = item.getCategory();
    // ❌ 不是原子操作
    counter.put(key, counter.getOrDefault(key, 0) + 1);
}

// ✅ 正确：使用 ConcurrentHashMap
Map<String, LongAdder> counter = new ConcurrentHashMap<>();
for (DataItem item : data) {
    String key = item.getCategory();
    counter.computeIfAbsent(key, k -> new LongAdder()).increment();
}

// JDK 7：Segment 分段锁
// 将数据分成 16 个段，每段独立加锁
// 优点：并发度高（最多 16 线程并发写）
// 缺点：实现复杂，初始化时一次性分配所有内存

// JDK 8：CAS + synchronized
// 直接在 Node 级别加锁
// 优点：实现简单，内存利用率高
// 缺点：写并发度受限于单个桶（但红黑树查找快）