Java Map2

41. HashMap 中为什么需要扩容？

回答：
扩容是为了控制哈希冲突数量，提升查找效率。随着元素增多，桶中的链表或红黑树可能增长，导致查询性能下降，因此需要定期扩容以均衡分布。

分析：
HashMap 的本质是"数组 + 链表/红黑树"的结构。当元素数量增加、哈希冲突增多时，多个键可能落入同一个桶内，形成链表结构。此时查询效率将从 O(1) 降为 O(n)，如果是红黑树则为 O(log n)，依然存在性能下降问题。扩容通过将底层数组容量翻倍，并重新映射已有元素，降低每个桶的负载，从而提升平均访问速度。Java 8 中的优化更进一步，在扩容时并不重新计算元素的 hash 值，而是通过新增的一位 hash bit 来判断元素是留在原索引还是转移到"原索引 + oldCap"位置，实现高效迁移。可见，扩容不仅避免结构退化，也是一种防止热点集中、均衡分布的手段。

42. Java 8 中 HashMap 的扩容机制？

回答：
Java 8 中 HashMap 采用懒初始化策略，扩容时容量翻倍，元素根据高位 hash bit 判断新位置，从而高效地将旧数据迁移至新表。

分析：
HashMap 的扩容分为两步：一是扩展数组容量（通常是翻倍），二是将原数组中的元素重新分配到新数组。扩容触发条件为：当前 size 超过了 threshold（即容量 × 负载因子）。在 Java 8 中，resize 的关键点在于：不再重新计算 hash 值，而是观察旧 hash 的某个高位（新增的一位）是 0 还是 1。若为 0，则元素在新表中的索引与旧表一致；若为 1，则位置变为"原索引 + oldCap"。这种做法既节省了计算成本，也能较为均匀地将元素分布到新表，提升整体访问效率。与此同时，这种机制在不改变 hash 函数的前提下，有效避免了全表重算的高开销，是一次非常巧妙的底层优化。

43. HashMap 可以实现同步吗？

回答：
HashMap 本身是线程不安全的，但可以通过工具类实现同步包裹，或直接使用 ConcurrentHashMap 替代。

分析：
默认的 HashMap 并不支持并发访问，多个线程同时修改时可能导致数据覆盖、死循环甚至结构破坏。为了支持多线程安全访问，有两种常见方案：第一，使用 Collections.synchronizedMap(map) 方法将其包裹为线程安全的 Map，但该方式在每次操作都加锁，性能较低，适合读写比例均衡或同步要求较高的场景。第二，推荐使用 JDK 提供的 ConcurrentHashMap，它采用分段锁或 CAS + synchronized 组合机制，在保证线程安全的同时拥有更高的并发性能。ConcurrentHashMap 是 HashMap 的并发版本，支持高并发读写操作，在实际开发中被广泛用于缓存、共享数据结构等场景。

44. 往 HashMap 存 25 个元素，会扩容几次？

回答：
总共会扩容两次：从默认容量 16 扩容到 32，再扩容到 64。

分析：
默认情况下，HashMap 的初始容量为 16，负载因子为 0.75，因此第一次扩容阈值为 16 × 0.75 = 12。当插入第 13 个元素时触发第一次扩容，容量变为 32；此时新的阈值为 32 × 0.75 = 24。插入第 25 个元素时再次触发扩容，容量翻倍至 64。由此，在插入 25 个元素的过程中，HashMap 会经历两次扩容：一次在第 13 个元素，一次在第 25 个元素。

45. HashMap 在多线程环境下为什么会出现死循环？

回答：
在 JDK 1.7 中多线程扩容时采用头插法，可能因链表重排错误而形成环形结构，导致死循环。

分析：
HashMap 是线程不安全的，在并发场景下不建议直接使用。在 JDK 1.7 中，当多个线程同时触发扩容操作时，由于使用头插法构建新的链表结构，如果两个线程同时修改指针关系，可能会导致某些节点形成闭环，从而在之后的查找中出现死循环。而在 JDK 1.8 中，链表插入方式改为尾插法，从根本上规避了链表反转问题，但这并不意味着线程安全，依然可能存在数据覆盖、丢失等问题。因此，在并发环境下，应使用线程安全的 ConcurrentHashMap 替代 HashMap。

46. HashMap 和 HashTable 有什么区别？

回答：
HashMap 是非线程安全的，效率更高；HashTable 是线程安全的，但性能较低，且设计较为陈旧。

分析：
HashMap 与 HashTable 都是基于哈希表实现的 key-value 容器。HashMap 出现在 JDK 1.2，取代 HashTable 成为主流，主要区别包括：1）线程安全性：HashTable 所有方法都加了 synchronized，适用于单线程但性能低；HashMap 默认非线程安全，适用于单线程或外部同步场景；2）key/value 支持：HashMap 允许 key 为 null，HashTable 不允许；3）扩容机制：HashMap 默认容量为 16，扩容为 2 倍；HashTable 初始容量为 11，扩容为原来的 2 倍 + 1；4）hash 实现：HashMap 使用扰动函数增强 hash 分布，HashTable 直接使用原始 hashCode。综合来看，HashMap 更现代、灵活，而 HashTable 已逐渐被淘汰。

47. 为什么重写 equals 方法时必须重写 hashCode？

回答：
因为 HashMap 查找是先根据 hashCode 定位，再通过 equals 判断是否相等。若两者不一致，会导致查找失败或插入错误。

分析：
在使用对象作为 HashMap 的 key 时，key 的行为由其 hashCode 和 equals 方法共同决定。hashCode 用于计算哈希桶索引，equals 用于在冲突链中比较具体对象。如果两个逻辑上相等的对象（equals 返回 true）却返回不同的 hashCode，会导致它们落入不同的桶，无法命中；反之，若两个对象 hashCode 相同但 equals 不等，则可能覆盖错误的值。因此，在使用自定义对象作为 key 时，必须保证满足 hashCode 与 equals 的通用约定：相等对象必须拥有相同的哈希值。这一原则对集合操作的正确性至关重要。

48. 什么是 LinkedHashMap？其实现原理是什么？

回答：
LinkedHashMap 是在 HashMap 基础上增加了双向链表的结构，用于维护元素的插入顺序或访问顺序。

分析：
LinkedHashMap 继承自 HashMap，保持了哈希表的所有功能，并通过额外的双向链表（before 和 after 指针）实现了有序性。其默认按插入顺序排序，构造时传入 accessOrder=true 则改为按访问顺序排序（最近访问的放后面）。链表结构贯穿所有节点，因此在迭代时能保证顺序性，非常适用于构建缓存（如 LRU）等对元素顺序有要求的场景。除了有序性，其他行为与 HashMap 基本一致，例如允许 null、线程不安全、扩容机制等。LinkedHashMap 的有序特性是其在通用 Map 应用中的重要补充。

49. HashTable 如何实现线程安全？

回答：
HashTable 所有方法基本都被 synchronized 修饰，保证线程安全，但因此性能开销大。

分析：
HashTable 是早期 Java 中的线程安全 Map 实现，它通过在所有公有方法上加 synchronized 锁来实现互斥访问。例如 get()、put()、remove() 等都加了同步关键字。其实现虽然简单直接，但每次操作都要获得对象锁，导致即使线程操作不同 key，也不能并发执行，性能大幅下降。因此现代开发中，HashTable 已不再推荐使用。取而代之的是 ConcurrentHashMap，它通过更精细的锁粒度（如分段锁、CAS 操作等）实现了高性能并发支持，成为新的主流并发 Map 选择。

50. 什么是 TreeMap？

回答：
TreeMap 是基于红黑树实现的有序 Map，它的 key 会自动排序，默认按自然顺序，也可自定义排序逻辑。

分析：
TreeMap 是 SortedMap 接口的一个实现，其底层是红黑树结构，具有 log(n) 级别的插入与查找效率。TreeMap 中的 key 必须具备可比性（实现 Comparable 或提供 Comparator），否则运行时会抛出异常。它按照键的大小自动进行排序，在很多需要有序输出或范围查询的场景中表现出色，例如排行榜、时间区间查找等。由于其底层是树结构，性能较 HashMap 稍低，空间开销也更大，但换来了数据的有序性。TreeMap 不是线程安全的，如需并发控制需额外同步。

51. HashMap、LinkedHashMap、TreeMap 有什么区别？

回答：
三者都实现了 Map 接口，但在顺序、排序和底层结构上差异明显：HashMap 无序，LinkedHashMap 保持顺序，TreeMap 自动排序。

分析：

HashMap：底层为哈希表，元素无序，适用于快速插入与查找，性能优异；
LinkedHashMap：继承自 HashMap，增加双向链表维护元素顺序，适合有顺序需求的场景；
TreeMap：基于红黑树，自动对 key 排序（可定制 Comparator），支持范围查询。
三者的选择应根据实际需求决定：若只关注性能选 HashMap；需要顺序则用 LinkedHashMap；需排序与范围查找则选 TreeMap。需要线程安全版本时，推荐使用 ConcurrentHashMap 或同步包装类。

52. 为什么 ConcurrentHashMap 比 HashTable 效率更高？

回答：
因为 ConcurrentHashMap 使用更细粒度的并发控制机制（如分段锁、CAS、局部 synchronized），避免全表锁，从而支持高并发访问。

分析：
ConcurrentHashMap 是 Java 为并发场景专门设计的线程安全 Map 实现。在 JDK 1.7 中，它采用分段锁 Segment 技术，每段独立加锁，允许多个线程并发访问不同段，极大提升并发性能。而 JDK 1.8 弃用 Segment，改为 Node + CAS + synchronized 的无锁+锁结合机制，读操作尽可能无锁，写操作使用 synchronized 保证一致性。其底层结构也引入红黑树优化冲突严重的桶位，提高效率。相比之下，HashTable 对整个对象加锁（synchronized 全方法），即便访问不同 key 也无法并发，性能较差。综上，ConcurrentHashMap 在并发性能、粒度控制与现代化设计上全面优于 HashTable。