Java8里的HashMap为什么要引入红黑树?

大家好, 这里是K字的研究.

红黑树在Java8版本的JDK标准库中,被拿来改善HashMap性能, 随之变成了一个面试大大热门, 经常听闻有人要在面试中手写一个正确的红黑树实现之类.

反正咱是写不出,不过这事挡不住咱爱八卦.今天咱来八卦下为什么会用红黑树. 不涉及红黑树源码和实现.

1为什么`Java8`要使用`红黑树`

既然是八卦,咱就不从2-3树,2-3-4树,红黑树,左倾红黑树^[1] 之类的来讲起了, 直接研究八卦核心:

为什么当初会选择引入红黑树, 究竟遇到了什么问题?
都有什么可选的解决方案?
为什么选了红黑树方案?

2JEP

现在来八卦一个概念: JEP.

咱们都知道, 每年开会, 修改法律, 都会有各种人去提交提案. Java 的改变也是一样的. Java 要想发生什么变动, 也需要有人提案. 这个提案叫JEP(java enhance proposal). 这些 Java 的提案,经过大佬们讨论后, 就是开始实施,实现,最后进入 Java 主线(当然也可能最后被否决了). 所有的JEP都记录在openjdk官网,JEP 清单^[2]里.

那么, 修改HashMap的提案是什么呢?

3JEP180

噔噔蹬蹬…可以查到, 在JEP180^[3] 中.

标题是: JEP 180: Handle Frequent HashMap Collisions with Balanced Trees.

用平衡树来解决频繁HashMap碰撞问题.

新问题来了.

频繁碰撞(Frequent HashMap Collisions)咋了?
平衡树就能不碰撞了吗?
平衡树并不等于红黑树啊?

啥是频繁碰撞?

Hashing 的通病

这要先从散列法(Hashing)技术说起,HashMap是Hashing技术在Java中的一种实现, 碰撞不是HashMap特有的问题.而是散列法这项技术通病.

在《具体数学》里是这么描述散列法的:

维持一个记录的集合, 记录包含 ,以及关于的记录数据:. 当给出时, 能够快速的得到 .

看起来很正式, 其实说白了, 就是提供了一个快速找到对应数据的方法.

比如,维持一个八卦->明星的记录集合,一提中间人攻击诈骗50万,我们就知道是那谁谁.

这东西咋说呢, 如果我们有足够多的内存, 比如说无限内存.完全可以,放一个无限长的数组,把对应的数据 ,放到数组的第个位置.

然而, 现实太残忍.

不一定是数字. 我们需要把`非数字`的转换成数字.

比如,现在要获取jkl的公众号标题.

对于字符jkl,熟悉的ASCII里, 每一个字符都对应着一个数字,可以加起来试试看.

可是, 这种把非数字内容转换成数字的方法, 有一个问题, jkl,lkj,甚至kkk在这种方法下,转换出来数字是相同的.

我们先把这种方法得到的结果用来表示. 继续看第二个问题.

内存是有限的.

因为内存是有限的,所以,数组的 length 是有限的, 这里暂时用个来代替.

即使第一步计算的方法是完美的, 可以保证每一个输入对应的都是不同的. 仍然会遇到的情况.

把一个大数字, 转换成比小数字小, 咱们一般都用取余法.计算下余数:, 根据这个新得到的来获取数据的位置.

总结下刚刚遇到的问题

不同的字符串,有可能计算出相同的数值 .
不同的数值, 只要除以 m 的余数相同, 仍然相同.

当不同的东西, 计算出了同一个位置的时候, 就可以说, 发生了哈希碰撞,有时候也叫哈希冲突. 英语就一个词,全看翻译心情.

这里的不同, 指的是equals为 false. 实现 hashcode 时候为什么要实现equals就是为了这里.

那么, 这个碰撞机会,他大吗?

咱们都知道, HashMap之类的实现, 大多是会自动扩容的, 这个其实是不断在变化的. 因为取余发生的碰撞, 几乎是都能避免的.

问题的核心本质, 还在哈希函数上(就是刚才用来把非数值转换成数值那个方法那种了). 碰撞的机会大不大,关键看不同输入计算出相同h的可能性大不大.只要哈希函数写的好, 很多时候是不会出现高频碰撞的.

比如, 著名的ThreadLocal.ThreadLocalMap用的斐波那契哈希技术. 作者因为对自己哈希函数的高度自信, 压根就没采用红黑树来解决问题, 甚至连链表法都没用,而是用了开放散列法.

这个就是ThreadLocal的hashCode数列的可视化. 实现的比较好的hashCode都应该像这样, 在整个int的空间里,较为均匀的分布.

J K L，公众号：K字的研究ThreadLocal.hashCode有多厉害

高中生时间

先做个简单的数学题

假设我们有个抽屉, 个小球, 现在随机把小球放到抽屉里,所有小球都在同一个抽屉的概率有多大?

根据排列组合知识可以知道, 个球,每个球都有种选择可能性,完全随机放可以产生的结果有种结果.所有球都放进同一个抽屉, 只有种可能. 计算概率应该为 .

程序员时间

同理,对于用长度为的数组实现的哈希表,出现n个 key 被哈希函数计算到同一个位置的概率为 .

按照都背过的 HashMap 实现, 发生树化的临界条件是:

MIN_TREEIFY_CAPACITY
TREEIFY_THRESHOLD

那么, 此时的 tablesize 是多少呢?

  static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1: n + 1;
    }

巧了, 还是这个经典公式,可以算出:b=64

那么树界降临时, 8 个 key 全被 hash 计算到同一个位置的概率是多大?

带入公式可知:

咱就不数这里有多少位数了,没必要. 结论其实就一个, 在哈希函数完美的情况下, 这个概率低到无以复加. 频繁的发生碰撞 8 个节点在一个位置,自然情况下, 几乎是不可能的.

WHY WHY WHY?

那为什么, JEP180 要处理频繁碰撞? 难道是,遇到鬼了?

是的, 遇到鬼了.

道高一尺魔高一丈

哈希表到底要设计的多复杂,不是取决于防守者,而是来自攻击者.

一般情况下不会发生频繁碰撞, 二般情况下,往往就发生了.

2003 年有一篇神奇的文章基于算法复杂度的 DOS 攻击^[4](Denial of Service via Algorithmic Complexity Attacks). 这篇文章里,就提出了攻击的方式,利用人为的 key 选择,针对 hash 函数的均匀性进行攻击.让所有的节点都落到相同的slot里.让哈希表在最差的情况下,退化成一个链表.

如何设计输入来让构造碰撞?

先取一个简单的小例子, 来操作一个最简单的哈希函数算法.

比如对输入数字求和,最终结果模10,获得一个10以内的数字.

别笑, 这个虽然简单,但是这真的是一个算法Luhn algorithm^[5] . 这位 Luhn 是 Hash 算法的祖师爷, 这个模 10 的算法就是以他名字命名的,一般用来做校验和.

对这个算法,就可以认为构造出非常多冲突的输入. String 之类的,设计输入略微复杂了点, 但是现代计算机能力高超,仍然可以设计出来.

攻击能成功的关键因素

这个攻击, 主要特点, 就是操纵数据来攻击哈希函数. 能否成功取决于 3 点:

输入 key 个数上限比较高
哈希函数结果是可预测的
最坏场景(worst-case)性能糟糕

治疗方案

针对这几个点, 解决方案也是几大类.

控制 key 个数上限, 比如 10.
解决哈希函数^[6]
引入平衡树来让最坏场景不是变成链表

画成图,大概是这样的

控制 Key 的数量上限

在刚出现这个攻击方式的时候, 一般是走的第一条路, 对数据长度进行限制. 这样, 你就算能攻击, 10 个 8 个元素的链表,性能又能差到哪里去?

解决哈希函数

每个 HashMap 用的 Hash 函数不一样, 或者用的一样, 但是每次带一个随机的种子.哈希函数不可预测,看你怎么攻击.

别说, 这还真是个好方法. 除了 Java 以外的很多语言,都使用了这个法子.

在Java8 采用JEP180之前, 也曾尝试过第二条路. 给String添加一个私有的属性 hash32,新的 hash 算法^[7] murmur3 hashing algorithm along with random hash seeds and index masks. 这个改动宣称:

Summary: All of the hashing based Map implementations: HashMap, Hashtable, LinkedHashMap, WeakHashMap and ConcurrentHashMap are modified to use an enhanced hashing algorithm for string keys when the capacity of the hash table has ever grown beyond 512 entries. The enhanced hashing implementation uses the murmur3 hashing algorithm along with random hash seeds and index masks. These enhancements mitigate cases where colliding String hash values could result in a performance bottleneck.

这个murmur3也是个很有趣的好算法, 在Guava里也有实现. 这个算法的特点是碰撞率更低,再加上随机种子, 在解决哈希函数方面,肯定是能起到效果的.

如果当时选了这个实现, 估计面试题就要背这个了. 其实现在也很常用,比如Redis^[8], 今天不是他主场,不提他了.

然而, 这个方案有几个额外问题.

修改了原 string 接口
不能适用用非 string 做 key 的场景
造成了某些回归测试无法通过
增加属性会占用堆空间.

经典 3 选一场景, 已经排除两个了. 现在, 只能选择第三方案了. 用什么办法呢?

东风来了

在HashMap正在紧锣密鼓增加hash32的时候, 东风来了.

ConcurrentHashMap此时在解决的JEP155^[9] ,改造成功, 率先实现了平衡树.

程序员的爱好是什么?复制粘贴!有代码可抄, 谁会自己写呢?

啊呸,是 DRY 啊.

Java坚持了他的保守性, 在对String类的修改未暴露到社区之前,删掉了这部分代码.移植了平衡树的实现回来, 按照第三个方案实现了攻击防御.

不过感兴趣的,还是可以从代码历史里看到这部分hash32 的代码^[10] . 开头提到的JEP180记录了这个变动的原因:

This technique has already been implemented in the latest version of the java.util.concurrent.ConcurrentHashMap class, which is also slated for inclusion in JDK 8 as part of JEP 155. Portions of that code will be re-used to implement the same IDEA in the HashMap and LinkedHashMap classes. Only the implementations will be changed; no interfaces or specifications will be modified. Some user-visible behaviors, such as iteration order, will change within the bounds of their current specifications.

歌词大意: ConcurrentHashMap 实现过了, 咱抄吧.

4最后的问题

HashMap 为什么会使用红黑树, 呵呵, 因为他抄的ConcurrentHashMap的技术选型.

问题,变了.

`ConcurrentHashMap`会做`红黑树`这个技术选型?

打开百度百科,可以看到,平衡树有很多种

red-black tree
splay tree
treap
avl
B-tree
2-3 tree

这里面

2-3树其实就是一种特化的B-树
红黑树是2-3树的一个特化.
树堆的最坏场景是 ,解决不了问题.
伸展树在最坏场景下也不是很合适.

AVL vs ReadBlack

真正能够值得一比较的, 只有 `AVL`^[11]和`红黑树`^[12].

Algorithm		Average	Worst case
Space
Search
Insert
Delete

参数上看, 这两位其实差不多. 详细比较参见Performance Analysis of BSTs in System Software^[13]

深度方向, AVL其实比红黑树表现好一点的.红黑树在极端情况下,倾斜还是比较大的. 比如前阵子,我们画过的红黑树可视化.这图右侧深度已经达到了极限的两倍于平均深度了.

那么, 为什么ConcurrentHashMap会舍 AVL 树而选红黑呢?还是要回到问题的本源上.

JEP155

打开 JEP 155, 动机是这句cache-oriented enhancements,这里的的 oriented 就是 oop 的那个 o. JEP155 是以缓存为导向做的增强,面向缓存增强.

既然本心是做缓存, 那么对缓存最重要的增删功能,性能必然要求更高.

平衡树这个东西,增,删节点之后的自平衡操作^[14] 也非常重要.

对于删除来说,AVL最坏情况下,需要次旋转. 红黑树可以保证稳定的只需要最多 2 次旋转.算法的可预期程度上来说, 红黑树更稳定,AVL 有一点点需要运气. 概率相关的复杂度计算我不太行, 这段是引入的别人的说法.

个人猜测, ConcurrentHashMap在 JEP155 的改动里, 主要是为了针对缓存做优化,缓存有大量的增删操作,所以他选择了基于 CAS 的无锁红黑树^[15] . 而抄代码的HashMap之类, 也跟了这个选型.

一个段子

当然, 我还看到过一个更有趣的说法. 为什么业界有大量的红黑树使用^[16] . 因为算法导论里给了一个完整实现,抄起来比较容易,不太会出 bug. 权当一个段子记录在这里.

5结语

写这篇主要是为了总结下查资料的笔记和收获.

Java 作为一个历史悠久,用户众多的大工程. 他的修改和演进中的取舍, 选型倾向, 以及稳定和兼容性保证,都是值得在日常中进行学习的.

今天就到这里了. 我是老 K,一个喜欢看八卦的程序员.

参考资料

[1]

LLRB左倾红黑树: https://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf

[2]

JEP 清单: https://openjdk.java.net/jeps/0

[3]

JEP180: https://openjdk.java.net/jeps/180

[4]

基于算法复杂度的DOS攻击: https://www.usenix.org/legacy/events/sec03/tech/full_papers/crosby/crosby.pdf

[5]

Luhn algorithm: https://en.wikipedia.org/wiki/Luhn_algorithm

[6]

解决哈希函数: https://www.cnblogs.com/gaochundong/p/hashtable_and_perfect_hashing.html

[7]

新的hash算法: https://hg.openjdk.java.net/jdk8/jdk8/jdk/rev/43bd5ee0205e

[8]

redis: https://github.com/redis/redis/search?q=murmur

[9]

JEP155: https://openjdk.java.net/jeps/155

[10]

hash32的代码: https://hg.openjdk.java.net/jdk8/jdk8/jdk/rev/43bd5ee0205e

[11]

AVL: https://en.wikipedia.org/wiki/AVL_tree

[12]

红黑树: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

[13]

Performance Analysis of BSTs in System Software: https://benpfaff.org/papers/libavl.pdf

[14]

自平衡操作: https://attractivechaos.wordpress.com/2008/10/02/comparison-of-binary-search-trees/

[15]

CAS 红黑树: http://www.cs.umanitoba.ca/~hacamero/Research/RBTreesKim.pdf

[16]

平衡树比较: https://www.zhihu.com/question/27542473/answer/37058413

原文始发于微信公众号（K字的研究）：Java8里的HashMap为什么要引入红黑树?

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/24850.html