并发 -HashMap

发表于 更新于 分类于 ， 本文字数： 192 阅读时长 ≈ 1 分钟

1. HashMap

1.hash 冲突后用链表

  • hashMap 底层数据结构

    entry(key,value,hash 值,nextEntry)

  • 为什么链表由头插法改为尾插

    头插时，先插入 B 再插入 A，则 A 指向 B，当 hashmap 扩容时，需要重新赋值，此时链表先插入 A，再插入 B，则 B 指向
    A，而并发时两个线程分别拿取扩容前和扩容后的 A 和 B 时，就会导致 AB 互指，造成死锁。

    image-55555

  • 为什么要用红黑树

    链表查询效率太低，超过 8 变红黑树，等于 6 变链表

    image-20230202104822054

2. ConcurrentHashMap

  • 扩容用的 CAS，如果是链表或者红黑树，在 synchronized 上锁，只会锁链表头结点

  • hashMap 底层数据结构

    entry(key,value,hash 值,nextEntry,parentEntry)