HashMap 进阶篇：红黑树、多线程坑和 equals/hashCode 的那些事

上篇讲了 HashMap 的核心机制put、get、扩容、2 的 n 次方这些。当时留了个尾巴说还有几个进阶话题没聊完。这篇就来填那个坑。其实写完上篇之后我又翻了翻源码发现有几个细节我之前也是一知半解的。比如为什么选红黑树而不是平衡二叉树HashMap 在多线程下到底会出什么问题equals 和 hashCode 到底怎么重写才能不出 bug这些问题的共同点是平时写代码可能不太会碰到但面试必问而且理解了之后你对 HashMap 的认识会上一个台阶。为什么是红黑树不是平衡二叉树上篇提到 JDK 1.8 之后HashMap 在链表太长的时候会转成红黑树。但我当时就有个疑问红黑树是一种平衡二叉树那为啥不用更平衡的 AVL 树呢先说结论不是 AVL 树不好而是对 HashMap 的场景来说红黑树更合适。AVL 树的严格和平常觉得不划算AVL 树对平衡的要求很严格任何节点的左右子树高度差不能超过 1。这个要求保证了树的查找效率非常高最坏情况也是 O(log n)。但代价是每次插入、删除都可能破坏这个平衡一旦破坏了就要通过左旋、右旋、双旋来修复而且有时候要一路旋转到根节点。红黑树就不一样。它不要求严格的高度平衡只要求黑色高度平衡最长路径不超过最短路径的 2 倍就行了。所以它的旋转次数比 AVL 树少得多。我当时想那 AVL 树查找更快啊为什么不用后来想明白了HashMap 不是纯树形结构。它的主体是数组加链表树只是哈希冲突严重后的补救措施。而且链表转树的阈值是 8也就是说一个桶里的元素得超过 8 个才会触发树化。这是一个低频事件。你想想看一个低频发生的事发生后你还要频繁地做插入删除操作如果每次插入删除都要触发大量旋转那就不划算了。红黑树的旋转次数少综合下来更划算。再一个HashMap 里对一棵树的操作不是只读不改的。你往里 put 的时候要插入节点往里 get 的时候要查找节点往里 remove 的时候要删除节点增删改查都有。AVL 树的查找是快一点但插入删除的代价太高了。红黑树的增删改查都是 O(log n)虽然查找比 AVL 慢一点点但增删快得多。在 HashMap 的场景下这个取舍是对的。我当时自己画了一个对比表AVL 树红黑树平衡程度严格平衡高度差≤1弱平衡最长≤2×最短查找快严格平衡稍慢一点点插入/删除旋转频繁开销大旋转少开销小适用场景查找多、增删少的场景增删改查均衡的场景HashMap 显然是增删改查都有的场景所以选了红黑树。哈希冲突不只有一种解法上篇主要讲了拉链法链表红黑树这种解决哈希冲突的方式。但其实哈希冲突的解决办法不止这一种。我当初学的时候只知道链表法后来发现还有好几种。1. 拉链法就是 HashMap 用的这种冲突的元素用链表串起来挂在同一个桶里。JDK 1.8 之后还加了红黑树做优化链表太长就升级成树。这个方法优点是实现简单而且桶可以无限扩容一个桶里的链表理论上可以无限长虽然实际不会。缺点是每个节点要额外存一个 next 指针空间上多一点点开销。2. 开放寻址法这个思路不一样如果算出来的位置被人占了就在附近再找一个空位放进去。找空位的方式有好几种线性探测被占了就往下一位放再被占就继续往下直到找到空位。优点是简单缺点是容易产生聚集——一旦有一个地方堵了后面一串都会被影响。二次探测不是挨个往后找而是按 1²、2²、3² 的步长跳着找。比线性探测分散一些聚集问题好一点。双重散列用两个哈希函数第一个算出位置被占了就换第二个哈希函数再算。这个方法最均匀但也最复杂。我当时听说 ThreadLocalMap 用的就是开放寻址法。它的结构是一个数组没有链表。如果算出来位置被人占了就用线性探测往后找空位。3. 再哈希法这个更好理解准备多个哈希函数第一个冲突了就换第二个算还冲突就换第三个直到找到空位为止。4. 扩容冲突严重了直接扩数组把元素重新分散开。HashMap 就是用的这种思路链表太长先试着扩容扩完还长再转树。所以 HashMap 其实组合了好几种策略拉链法为基础 尾部插入 树化升级 扩容降级。这是看了源码之后才意识到的——它没有只靠一种方法解决问题而是打了一套组合拳。为什么 String 是最适合做 Key 的类型我刚学的时候看到别人用 HashMap 基本上都是用 String 做 key。我心想为什么大家都用 String用 Integer 不行吗用自定义对象行不行答案是当然行但 String 是最安全的。原因在于 String 的不可变性。String 对象一旦创建就不能被修改。“hello永远都是hello”不会变成world。这就保证了 String 的 hashCode 值也是固定的只要内容一样hashCode 就一样。如果用一个可变对象做 key会出什么问题我举个例子。假设我写了一个类classUser{Stringname;intage;// 省略 getter/setter}然后我用这个 User 对象做 key存到 HashMap 里MapUser,StringmapnewHashMap();UserusernewUser(张三,20);map.put(user,一些数据);这个时候一切都好。但如果后面我改了 user 的年龄user.setAge(25);问题就来了——user 的 hashCode 可能变了如果 hashCode 里用到了 age。但它在 HashMap 里的位置还是根据旧的 hashCode 算出来的。这个时候用map.get(user)去获取算出来的新位置和存数据时的旧位置不一样就找不到了。更糟的情况是你修改了 key 之后原来的那个桶里还挂着这个 entry但它已经失效了——桶还在数据还在但你已经取不出来了。这就造成了内存泄漏。String 不会出现这个问题因为它不可变。你拿到一个 String 对象不用担心它哪天突然变了。所以如果你问我最安全的 key 是什么类型我会说是不可变类型。String、Integer、Long 这些都行。但非要用自定义对象做 key那就必须保证它是不可变的——所有字段都是 final 的不提供修改方法。equals 和 hashCode一个面试必问的话题这个话题我一直觉得有点虚平时写代码很少会自己去重写 equals 和 hashCodeIDE 会自动生成。但面试就是爱问。不过后来有一次我真的踩坑了才意识到这里面确实有门道。它俩的约定Java 对 equals 和 hashCode 有一个约定如果两个对象 equals 相等它们的 hashCode 一定相等。如果两个对象 hashCode 相等equals 不一定相等。这就是哈希冲突第二条好理解。第一条是重点——如果你重写了 equals 但没有重写 hashCode就可能打破这个约定。我当时试过一个很简单的例子。先写一个 Student 类只重写 equals不重写 hashCodeclassStudent{Stringid;Stringname;Student(Stringid,Stringname){this.idid;this.namename;}Overridepublicbooleanequals(Objecto){if(thiso)returntrue;if(onull||getClass()!o.getClass())returnfalse;Students(Student)o;returnid.equals(s.id);}}然后我往 HashSet 里放两个 “学号相同” 的对象SetStudentsetnewHashSet();set.add(newStudent(001,张三));set.add(newStudent(001,李四));System.out.println(set.size());你猜输出是 1 还是 2我当时以为会是 1——因为 equals 认为学号相同就是同一个学生。但实际输出是2。因为 HashSet 的底层是 HashMap它先比较 hashCode 再比较 equals。两个 Student 对象没有重写 hashCode所以用的是 Object 的默认 hashCode——每个对象的内存地址不同hashCode 自然不同。HashSet 把它们放到了不同的桶里根本没机会去调 equals。正确做法重写 equals 的时候一定要同时重写 hashCode。而且 hashCode 的计算逻辑要跟 equals 里用到的字段保持一致。equals 里根据 id 判断相等那 hashCode 里也要用 id 来计算OverridepublicinthashCode(){returnid.hashCode();}这样学号相同的两个 Student 对象hashCode 就一样了。HashSet 会把它们放到同一个桶里然后通过 equals 发现是同一个学生就不会重复存储。IDE 自动生成的重写一般都是正确的——它会把 equals 里比较的所有字段都拿去算 hashCode。但核心是你要理解它为什么要这么做保证 equals 相等的对象hashCode 也相等这样才能在哈希表里正常工作。重写不当的后果重写 equals 不重写 hashCode 会导致集合行为异常——两个明明 equals 相等的对象却被认为不相等地存到了 HashSet 或 HashMap 里。但如果反过来——hashCode 写得太粗糙比如所有对象都返回同一个 hashCode 值OverridepublicinthashCode(){return1;}这不会影响正确性equals 仍然能正确区分但会导致所有对象都挤到同一个桶里HashMap 退化成链表性能从 O(1) 掉到 O(n)。这就叫哈希冲突严重。所以好的 hashCode 要尽量让不同的对象返回不同的值分布越均匀越好。IDE 生成的 hashCode 方法用的 31 这个质数就是出于这个目的——31 * 某个字段 另一个字段能产生比较均匀的分布。get 方法调用真的安全吗上篇讲了 get 方法的工作流程但有一个问题我当时没有仔细想调用 get 方法会不会抛异常先说说最常见的误解。有人觉得用 null 调 get 会抛空指针但其实不会。HashMap 是明确支持 null key 的——它会直接把 null 的 hash 值设为 0放到 0 号桶里。所以在 HashMap 上调get(null)是安全的。但有个前提HashMap 对象本身不能是 null。如果你写了HashMapString,Stringmapnull;map.get(key);那当然会抛 NPE——你都还没 new 对象呢拿一个 null 引用调任何方法都会抛。另外就是线程安全问题。get 方法本身不抛异常但如果另一个线程同时在往同一个 HashMap 里 put而且触发了扩容那 get 的时候可能会读到不完整的数据或者读到一半被修改了的链表结构。这就是并发修改异常 ConcurrentModificationException 的根源。我之前在面试里被问到过这个问题——“HashMap 是线程安全的吗get 方法安全吗”我当时回答“不抛异常但读到的不一定对。”面试官后来说这个回答还行。因为 get 本身不会破坏 HashMap 的结构它只是读。但多线程环境下你读到的数据可能不是你想要的——因为你读的时候别人正在写。所以后来我在需要多线程的地方要么自己加锁要么直接用 ConcurrentHashMap。HashMap 在多线程下到底会出什么问题这是一个老生常谈的问题了也是面试的高频题。我刚开始准备面试的时候把HashMap 线程不安全这个结论背得滚瓜烂熟。但面试官一问具体怎么不安全我就卡住了。后来我去翻了源码才搞清楚细节。JDK 1.7 的时候环形链表JDK 1.7 的 HashMap 用的是头插法——每次往链表中插入元素的时候新元素插到头部。这种实现在单线程下没问题但多线程并发扩容的时候可能会形成一个环形链表。为什么会有环形链表因为扩容的时候要把旧数组的元素搬到新数组。如果两个线程同时做这件事线程 A 搬了一部分元素线程 B 也搬了一部分而且它们对链表的引用操作互相交叉就可能让链表的最后一个节点指回前面的节点形成一个环。环形链表意味着什么你下次 get 某个 key 的时候遍历这个环形链表就会一直转圈死循环。CPU 跑到 100%程序卡死。我当时读到这个的时候心想这个 bug 确实很严重。因为这不仅仅是数据不对的问题是程序直接崩溃的问题。JDK 1.8 的改进JDK 1.8 把头插法改成了尾插法——新元素插到链表尾部。同时修改了扩容时元素的迁移逻辑。这样就不会再出现环形链表了。但 JDK 1.8 的 HashMap 就线程安全了吗不是。多线程同时 put 的时候还是会出现数据覆盖的问题。举个例子线程 A 和线程 B 同时调 put恰好它们算出来的 hash 位置是一样的。线程 A 先检查位置是空的正要插入的时候让出了 CPU。线程 B 也检查了这个位置发现也是空的就直接插入了。然后 A 恢复执行又把它的数据插入到同一个位置——这样就覆盖了 B 的数据。更隐蔽的问题是 size 的计算。HashMap 里维护了一个 size 变量记录存放了多少个元素。size 在 Java 里不是原子操作它可以拆成读取 size、size1、写回 size三步。两个线程同时做 size 的时候可能两个都读到了同样的旧值加完之后写回去就少了一个。那怎么办如果你要在多线程环境下用 HashMap有几种选择Collections.synchronizedMap()把 HashMap 包一层所有方法加同步锁。但锁的粒度是整个对象性能不太行。Hashtable老牌的线程安全哈希表但也是整个对象加锁跟 synchronizedMap 差不多。ConcurrentHashMap这是最推荐的方式。JDK 1.7 用分段锁JDK 1.8 进一步缩小锁粒度到每个桶的头节点并发性能最好。所以我的习惯是单线程用 HashMap多线程用 ConcurrentHashMap。Hashtable 基本不碰了——历史遗留产物。写在最后这篇聊了几个 HashMap 的进阶话题红黑树和 AVL 树的取舍、哈希冲突的多种解法、String 做 key 的原因、equals 和 hashCode 的规范、get 的安全性、多线程下的问题。写这些的时候我一直想到的是当初背面试题的自己。那时候 HashMap 相关的题目背得滚瓜烂熟但问到为什么就说不清楚了。后来去翻源码、自己写 demo 验证才慢慢把这些答案变成了理解。两篇下来HashMap 的核心机制和进阶原理都聊得差不多了。下一篇聊聊并发场景下的解决方案——ConcurrentHashMap 和 Hashtable看看它们是怎么解决 HashMap 的线程安全问题的。如果你也跟我一样在学这些东西建议看完之后去翻翻源码一行一行对着文章看。纸上得来终觉浅源码里面才有真东西。