经典问题
- 为什么重写 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(高并发)。


