钉钉Android面经及参考答案

对比 HashMap、Hashtable、ConcurrentHashMap 的数据结构与线程安全机制，说明高并发下 HashMap 可能出现的问题及原因；详细描述 ConcurrentHashMap 在 JDK 1.7 和 JDK 1.8 中的实现差异HashMap 底层数据结构在 JDK1.7 为数组 + 单向链表，JDK1.8 优化为数组 + 单向链表 + 红黑树，当链表长度超过 8 且数组容量大于 64 时链表转换为红黑树，减少长链表遍历耗时。HashMap 没有任何同步锁机制，所有方法均非同步，天然不支持多线程并发。Hashtable 底层同样是数组 + 单向链表，不使用红黑树优化，它通过在所有 public 方法添加 synchronized 关键字实现线程安全，锁对象是当前 Hashtable 实例对象，意味着同一时刻只能有一个线程操作整个哈希表，并发效率极低。ConcurrentHashMap 是分段线程安全容器，专门用于替代 Hashtable，兼顾并发安全与执行效率。高并发场景下 HashMap 会产生两类典型问题。第一类是数据丢失，多线程同时执行 put 操作发生哈希碰撞时，多个线程同时修改同一个链表节点引用，部分线程写入的节点会直接被覆盖，最终数据丢失。第二类是循环死链，该问题主要存在于 JDK1.7，扩容操作 rehash 时采用头插法迁移链表节点，多线程并发扩容会造成单向链表形成环形链表。当调用 get 方法访问环形链表位置时，代码进入无限循环，CPU 占用率飙升至 100%。JDK1.8 改为尾插法迁移节点，规避了死链问题，但依旧存在数据覆盖、数据不一致问题，依旧不能在并发环境直接使用 HashMap。ConcurrentHashMap 两个版本核