经典问题
- 为什么重写 equals() 一定要重写 hashcode?
- HashMap 是怎么判断两个对象是否相等的？
- HashMap 为什么要这么做？
一、为什么重写 equals() 一定要重写 hashCode()？
1. Java 官方的硬性契约（必须遵守）
java.lang.Object 类中明确规定了两个方法的共生关系：
- 如果两个对象通过 equals() 比较相等，那么它们的 hashCode()必须返回相同的整数。
- 如果两个对象通过 equals() 比较不相等，它们的 hashCode()可以相同也可以不同（但建议不同，以提高哈希表性能）。
2. 违反契约的后果（以 HashMap 为例）
如果你只重写了 equals() 而没重写 hashCode()，会导致哈希集合（HashMap、HashSet、HashTable 等）逻辑混乱：
- 场景：你创建了两个对象 A 和 B，A.equals(B) == true，但 A.hashCode() != B.hashCode()。
- 存入 HashMap：map.put(A, "value") 会根据 A 的哈希码找到一个位置存入。
- 读取 HashMap：map.get(B) 会根据 B 的哈希码去找（可能找到另一个位置），结果找不到（认为是两个不同的 Key），尽管逻辑上它们是相等的。
二、HashMap 是怎么判断两个对象（Key）是否相等的？
HashMap 判断两个 Key 是否相等，遵循**'先哈希码，后 equals'**的双重检查机制：
- 第一步：比较 hashCode()
- 先调用 Key 对象的 hashCode() 方法，计算哈希值。
- 如果哈希值不同：直接判定两个对象不相等（连 equals 都不用比了，效率高）。
- 如果哈希值相同（哈希碰撞）：进入第二步。
- 第二步：比较 equals()
- 调用 Key 对象的 equals() 方法进行内容比对。
- 如果 equals() 返回 true：判定两个对象相等（视为同一个 Key）。
- 如果 equals() 返回 false：判定两个对象不相等（虽然哈希冲突，但仍是不同 Key）。
三、HashMap 为什么要这么设计？
这是为了兼顾性能与准确性，本质是由 HashMap 底层的**'哈希表（数组 + 链表/红黑树）'**数据结构决定的：
1. 为什么要先比 hashCode()？（为了快）
- HashMap 的核心优势是查询速度极快（接近 O(1)）。
- 它通过 hashCode 直接计算出 Key 在数组中的存储下标，从而快速定位。
- 如果不先比 hashCode，而是每次都遍历所有元素调用 equals，那性能就退化成了链表（O(n)），失去了哈希表的意义。
2. 为什么还要比 equals()？（为了准）
- 哈希碰撞是不可避免的：不同的对象可能算出相同的 hashCode（就像不同的人可能有相同的指纹概率）。
- 因此，hashCode 相同只能说明它们应该放在数组的同一个'篮子'（链表/红黑树）里，但不能说明它们是同一个对象。
- 必须通过 equals() 进行最终的内容确认，才能保证逻辑的绝对正确性。
总结
- hashCode 决定了对象在哈希表中**'坐哪一排'**（快速定位）。
- equals 决定了对象在这一排里**'是不是同一个人'**（精确匹配）。
- 两者缺一不可，所以重写 equals 必须重写 hashCode。
List 接口（有序、可重复，按索引访问）
| 实现类 | 底层数据结构 | 核心特色 |
|---|---|---|
| ArrayList | 动态数组 | 1. 随机访问（索引）效率 O(1)，增删需移动元素（效率 O(n)）； 2. 线程不安全，适合查询多、增删少的场景。 |
| LinkedList | 双向链表（JDK1.7+ 取消循环） | 1. 增删只需修改节点指针（首尾操作 O(1)），随机访问需遍历（O(n)）； 2. 实现了 Deque 接口，可作为队列/栈使用； 3. 线程不安全，适合增删多、查询少的场景。 |
| Vector | 动态数组 | 1. 与 ArrayList 类似，但所有方法加 synchronized 修饰； 2. 线程安全但效率低，已很少使用。 |
| Stack | 继承 Vector，动态数组 | 1. 后进先出（LIFO）； 2. 线程安全但效率低，推荐用 Deque（如 LinkedList）替代。 |
Set 接口（无序、不可重复，依赖 equals()+hashCode()）
| 实现类 | 底层数据结构 | 核心特色 |
|---|---|---|
| HashSet | 基于 HashMap（存储在 key 中） | 1. 哈希表（数组 + 链表 + 红黑树，JDK1.8+）实现； 2. 无序，添加/查询/删除效率平均 O(1)； 3. 线程不安全，需重写 equals() 和 hashCode() 保证唯一性。 |
| LinkedHashSet | 继承 HashSet，基于 LinkedHashMap | 1. 哈希表 + 双向链表实现； 2. 有序（按插入顺序或访问顺序）； 3. 性能略低于 HashSet（需维护链表），线程不安全。 |
| TreeSet | 基于 TreeMap（红黑树） | 1. 红黑树（自平衡二叉搜索树）实现； 2. 有序（自然排序或定制排序，需实现 Comparable 接口）； 3. 增删改查效率 O(logn)，线程不安全。 |
Map 接口（键值对存储，key 不可重复，value 可重复）
| 实现类 | 底层数据结构 | 核心特色 |
|---|---|---|
| HashMap | 哈希表（数组 + 链表 + 红黑树） | 1. JDK1.8+：链表长度≥8 且数组长度≥64 时转红黑树； 2. 无序，允许1 个 null 键和多个 null 值； 3. 线程不安全，多线程需用 ConcurrentHashMap 替代。 |
| LinkedHashMap | 继承 HashMap，哈希表 + 双向链表 | 1. 维护插入顺序或访问顺序（accessOrder=true 时为 LRU 缓存）； 2. 性能略低于 HashMap，线程不安全。 |
| TreeMap | 红黑树 | 1. 按 key自然排序或定制排序； 2. 不允许 null 键（但允许 null 值）； 3. 增删改查效率 O(logn)，线程不安全。 |
| Hashtable | 哈希表（数组 + 链表，无红黑树） | 1. 所有方法加 synchronized 修饰； 2. 线程安全但效率低，不允许 null 键/值； 3. 已过时，推荐用 ConcurrentHashMap。 |
| ConcurrentHashMap | 哈希表（数组 + 链表 + 红黑树） | 1. JDK1.8+：用 CAS+synchronized（只锁链表/红黑树头节点）替代分段锁； 2. 线程安全，效率远高于 Hashtable； 3. 不允许 null 键/值，适合高并发场景。 |
快速选择指南
- List：选 ArrayList（查询多）或 LinkedList（增删多/队列）。
- Set：选 HashSet（通用）、LinkedHashSet（需有序）、TreeSet（需排序）。
- Map：选 HashMap（通用）、LinkedHashMap（需有序）、TreeMap（需排序）、ConcurrentHashMap（高并发）。
