一、HashMap核心原理

1. 底层结构
   采用数组+链表+红黑树的组合结构：
   • 数组（哈希桶）作为主体框架
   • 链表解决哈希冲突（Java 7及以前）
   • 红黑树优化长链表性能（Java 8引入，链表长度≥8且数组长度≥64时触发）
2. 存储机制
   • 通过key.hashCode()计算哈希值
   • 经扰动函数处理后，通过(n-1) & hash计算数组索引
   • 索引位置无元素则直接存储，存在冲突则通过链表/红黑树挂载
3. 扩容机制
   • 默认初始容量16，负载因子0.75
   • 当元素数量超过容量×负载因子时触发扩容
   • 扩容为原容量2倍，需重新计算所有元素位置（Rehash）

二、关键技术点

1. 哈希冲突解决
   • Java 7采用头插法（多线程下可能形成环形链表）
   • Java 8改用尾插法+红黑树优化
   • 树化阈值8/反树化阈值6的设计避免频繁转换
2. 性能优化设计
   • 红黑树使最坏查找复杂度从O(n)降至O(log n)
   • 扰动函数减少哈希碰撞概率
   • 负载因子0.75平衡空间与时间效率
3. 线程安全问题
   • 非线程安全，多线程环境下可能出现：
     • 数据覆盖（同时put同一位置）
     • 死循环（Java 7扩容时链表成环）
   • 并发场景需使用ConcurrentHashMap

三、扩展知识

1. hashCode()与equals()契约
   • 需同时重写，保证相等对象有相同哈希码
   • 作为键对象时，若未正确实现将导致存取异常
2. 容量预设建议
   • 已知数据量时显式指定初始容量
   • 避免频繁扩容带来的性能损耗
3. 结构演化对比表格版本插入方式冲突解决线程安全风险Java 7头插法纯链表扩容时可能成环Java 8+尾插法链表+红黑树无环但非原子操作问题

四、关联知识延伸

1. 红黑树改造原因
   解决极端哈希冲突下链表遍历退化问题，将最坏时间复杂度控制在O(log n)
2. 典型面试关联题
   • ConcurrentHashMap 1.7/1.8差异
   • HashMap与Hashtable对比
   • 扰动函数具体实现原理