设计一个 HashMap，给出你的设计思路，包括数据结构、哈希函数、冲突处理、扩容机制以及并发安全等关键方面，并说明你的设计取舍。
考察说明
考查候选人对于哈希表核心原理的掌握程度，以及系统设计中的权衡能力。
回答思路
- 【回答框架 1】HashMap 本质是基于数组和链表（或红黑树）实现的哈希表。数组用于快速定位桶，每个桶存放冲突的键值对，冲突处理常采用链地址法，当链表过长时（如超过阈值）转为红黑树以提升最坏情况下的查找性能。
- 【回答框架 2】哈希函数的设计目标是让键分布均匀，减少冲突。常用做法是对 key 的 hashCode 进行扰动（如异或高位），然后与数组长度减一进行与运算，要求数组长度为 2 的幂，以高效取模并减少碰撞。
- 【回答框架 3】扩容机制：当元素数量超过负载因子（如 0.75）乘以容量时，触发扩容，容量翻倍。扩容需要重新计算每个元素的桶位置，代价较高，但能维持平均 O(1) 的查询复杂度。
- 【回答框架 4】并发安全：Java 的 HashMap 非线程安全，多线程写入可能导致数据丢失或死循环。若需并发，可采用 ConcurrentHashMap，通过分段锁或 CAS + synchronized 实现高并发下的安全更新。
- 【回答框架 5】设计取舍：需平衡空间与时间，如负载因子调低可减少冲突但浪费空间；红黑树转换阈值需权衡树化与退化成本。我的设计会采用上述经典方案，并结合具体场景调整参数。
- 【关键点 1】数组加链表（或红黑树）的存储结构。
- 【关键点 2】哈希函数：扰动函数后与容量取模。
- 【关键点 3】负载因子决定扩容时机，默认 0.75。
- 【关键点 4】扩容时重新哈希，代价高昂。
- 【关键点 5】线程不安全，需用 ConcurrentHashMap 保证并发。
- 【易错点 1】不能直接使用 hashCode 作为桶位置，需扰动以减少冲突。
- 【易错点 2】扩容不是简单复制，需重新计算每个元素位置。
- 【易错点 3】红黑树转换有最小容量限制（如 64），小容量时链表更长可能反而降低性能。