在 Java 世界里, 有一个古老而神秘的家族 --Map. 从底层架构到上层应用, 他们活跃于世界的每一个角落. 但是, 每次出现时, 他们都戴着一张冷硬的面具(接口), 深深隐藏着自己的内心. 所有人都认识他们, 却并非每个人都理解他们. 在这个热闹的世界中, Map 们活得光荣却孤独...... 这个系列博文, 就将尝试透过接口的伪装, 走进每个家族成员的内心世界, 聆听家族内部的动人传说......
注: 各种 Map 在不同的 JDK 中有不同的实现. 如无特别声明, 本文只针对当前 (2019 年 3 月) 最新的 OpenJDK(13-ea)的实现
一, 从 HashMap 开始
好了, 上面都是扯淡, 目的是为了让气氛更加尴尬......
第一个介绍的 Map 成员是 HashMap, 因为它应用最广, 实现也最简单 -- 简单到我一直在纠结要不要单独为它写一篇文章. 代码在这里
HashMap 将键值对存储于若干个 bin 中. 所谓 bin(或者叫 bucket, 桶), 是一个可以保存多个键值对的数据结构. 初始状态下, 一个 bin 就是一个链表. 具体代码如下
- static class Node<K,V> implements Map.Entry<K,V> {
- final int hash;
- final K key;
- V value;
- Node<K,V> next;
- }
- transient Node<K,V>[] table;
Node 类是链表的元素. 变量 table 是一个链表的数组, 或者说是 bin 的数组. HashMap 所有的数据就保存在 table 中.(或许你注意到了 transient 关键字. HashMap 并不直接序列化 table 变量, 而是重写了 writeObject 和 readObject 处理数据的序列化)
当向 HashMap 中 put 数据时, 首先计算 key 的 hashCode, 根据 hashCode 找到它所属的 bin, 然后将键值对放入 bin 中, 也就是插入到链表的末尾. 可见, 有相同 hashCode 的两个 key, 一定会放入同一个 bin 中, 这种现象叫 hash 冲突(hash collision). 而 get 的过程也一样, 计算 key 的 hashCode 并找到对应的 bin, 然后在 bin 中搜索包含相同 key 的 Node.
以上是 HashMap 的基本实现原理.
二, 扩容 (resize) 与树化(treeify)
可见, put 和 get 消耗的时间与链表长度是 o(n)的关系. 如果数据量太大, 每一个链表都会很长; 或者运气太差, 大部分数据都集中于一个 bin 中, 这时 HashMap 的性能就会迅速下降. 怎么办呢?
有两种思路, 要么是缩短链表长度, 要么是提高 bin 的搜索速度. HashMap 的具体策略也是从这两方面入手. 每次 put 数据时, 都记录 Map 中整体的数据量, 以及链表的长度, 然后
(1)当整体数据量超过 bin 的数量的 3/4 时, 增加 bin 的数量, 这个过程叫扩容(resize). 扩容后, 各条数据都要重新计算它属于哪个 bin, 这叫做 rehash. 这样, 有些数据移动到新的 bin 中, 各个 bin 的链表长度就会缩短.
(2)当某个链表很长(超过 7), 而 bin 的数量很少(小于等于 64 个), 也会扩容, 以缩短链表.
(3)当某个链表长度超过 7, 而 bin 的数量大于 64 个, 就将这个 bin 由链表转变为红黑树, 提高搜索速度. 这个过程叫做树化(treeify). 树化是在 JDK 1.8 才实现的.
为什么不一开始就使用树呢? 个人理解, 这是出于时间 - 空间的综合考量. 当数据量很小时, 树的搜索速度并不明显优于链表, 而占用的空间却比链表多, 因此初始选择是链表, 遇到性能瓶颈也优先选择扩容.
而当 bin 足够多时, 继续扩容就会出现问题:
(1)继续扩容也会增加空间占用(而且占用的是连续空间. 还记得 table 是一个数组吗?). 相比于树化, 扩容不再具有空间上的优势.
(2)resize 之后要对所有的数据做 rehash, 当数据量很大时, rehash 的性能负担远高于对单个 bin 做树化.
可以说, 扩容改变所有数据的分布方式, 是一种针对整体的优化方案; 树化只改变单个 bin 的结构, 是针对局部的优化方案. 如果 bin 很多却依然存在很长的链表, 说明整体优化方案对于某个 bin 不起作用, 这可能是 hashCode 分布不均匀导致的. 继续扩容徒然增加空间, 效果却不见得理想. 这时, 就该采用局部优化方案, 也就是树化了.
以上纯属个人理解与猜测, 仅供参考.
最后说一点, bin 的数量并非到了 64 之后就不再增长了. 根据策略(1), 只要整体数据量足够多, 就会扩容. 不过, 扩容也不是无限的, 毕竟数组太大了也会造成问题. bin 的最大数量是 2 的 30 次方, 或者写成 1<<<30.
三, hashCode 与扩容策略
如何根据 hashCode 找到数据所属的 bin? 每次扩容增大多少? 如何 rehash? 这几个问题互相关联.
最简单的方案当然是取余. 假设 bin 的数量为 N,key 的 hashCode 为 H, 那么 key 所属的 bin 就是第 H%N 个. 而扩容可以任意增加 bin 的数量. 比如扩容后的 bin 有 N+M 个, rehash 时某个 key 所属的 bin 是第 H%(N+M)个.
这种方法可以实现功能, 但性能不好, rehash 阶段会非常耗时. 而且有可能两个 bin 中的数据被 rehash 到同一个 bin 中, 从而构建了一个比以前更长的链表. 而 OpenJDK 采用的方法则颇具技巧性, 充分利用了高效的位运算.
/**** 开始说正事的分割线 ****/
OpenJDK 要求 bin 的数量必须是 2 的整数幂, 即 1<<<N 个(乘以 2 和左移一位等价, 乘以 N 个 2 和左移 N 位等价). 初始状态 N=4, 即 bin 的初始数量是 2 的 4 次方, 或者是 1 左移四位的结果, 也就是 16 个.
有了这个要求, 许多事情就变得简单了.
如何 resize 呢? 为了保证上述条件成立, 每次扩容, bin 的数量都变为 2 倍. 如果当前 bin 的数量为 1<<<N, 扩容一次后 bin 的数量是 1<<<(N+1).
一个 key 应该属于哪个 bin 呢? 如果 key 的 hashCode 是 H,bin 的数量是 B=1<<<N, 则 key 所属的 bin 是第 H^(B-1)个. 也就是截取了 hashCode 最后的 N 位, 如下图所示
这种计算 bin 的方式与取余的结果实际是相同的. 但是它利用了位运算, 效率高于取余. 而且这种方式对 rehash 很友好.
扩容之后, bin 的数量是 B'=1<<<(N+1)=B<<<1 .rehash 前, key 所属的 bin 是 b1=H^(B-1), 它是 hashCode 截取后 N 位的结果; rehash 之后, key 所属的 bin 是 b2=H^(B'- 1), 他是 hashCode 截取后 N+1 位的结果. 可见, rehash 前后的差异只在 hashCode 的第 N+1 位, 也就是 H^B'的结果. 因此有
(1)如果 H^B'==0, 则 rehash 后这个 key 的位置不变
(2)如果 H^B'==1, 则 rehash 后这个 key 所属的 bin 是 b2=b1+B. 也就是将 b1 的第 N+1 位由 0 变为 1
整个 rehash 过程, 全部使用位运算以及一次简单的加法运算, 保证了最高效率. 而且两个 bin 的数据不会 rehash 到同一个 bin 中, 也不会把数据 rehash 到一个扩容前就存在的 bin 中, 保证了所有的 bin 在扩容后都不可能变得更长.
最后再说一个问题, hashCode 如何计算? 方法如下
- static final int hash(Object key) {
- int h;
- return (key == null) ? 0 : (h = key.hashCode()) ^ (h>>> 16);
- }
将 hashCode()方法的结果的高 16 位与低 16 位做 and 运算. 为什么不直接用 hashCode()方法的结果呢? OpenJDK 的解释是, 开发者可能用 Double 做为 key, 如果各个浮点数之间差别很小, 那么它们的低位将相同. 而 bin 的位置是由 hashCode 的低 N 位决定的. 这种情况下, 大量的数据将进入同一个 bin, 发生大量 hash 冲突, 严重影响性能. 于是, OpenJDK 最终选择了高位低位混淆的方案. 据说, 这种方案得到的 hashCode 满足泊松分布(虽然我不知道为什么会满足), 分布很均匀.
四, 关于树的二三趣事
比起链表, 红黑树更复杂, 也要处理更多的问题和细节. 可能这就是 Java 拖到 1.8 才实现树化的原因吧. 许多关于树的问题并不重要, 不影响整体思路, 但细细品味很有意思. 所以在最后写上一些.
(1)是一棵树, 也是链表
树化后, 新生成的树其实保持着原有链表的结构和顺序. 它既是树, 也是链表. 树的节点用类 TreeNode 表示, 贴一段 TreeNode 的声明
- static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
- TreeNode<K,V> parent; // red-black tree links
- TreeNode<K,V> left;
- TreeNode<K,V> right;
- TreeNode<K,V> prev; // needed to unlink next upon deletion
- boolean red;
- }
TreeNode 间接继承自链表节点类 Node, 所以它也是链表节点. 看到声明中的 prev 了吗? 它不仅是链表, 还是双向链表.
这么做意义何在呢? 首先是方便遍历, 我们大概都写过类似的代码
- Map<Integer, String> m = new HashMap<>();
- ...
- Iterator<Entry<Integer, String>> it = m.entrySet().iterator();
- while(it.hasNext()) {
- it.next();
- }
Iterator 的底层就是沿着链表的顺序遍历的. 遍历链表, 比遍历一棵树要高效得多.
然后, 是方便逆树化(untreeify). 链表太长了会树化成一棵树. 可树中的数据量可能因为 resize 或者 remove 而减少, 数据太少了, 树就会逆树化成一个链表. 因为链表结构没有丢, 逆树化就非常简单了.
(2)根节点在哪?
树的节点类 TreeNode 是链表节点类 Node 的子类. 因此, 树化不用改变 table 变量的类型
transient Node<K,V>[] table;
数组里的 Node, 我们称它为首节点 (first node). 它可能表示链表, 也可能表示树. 如果是链表, 首节点当然就是头节点. 可如果是树, 首节点是哪个节点呢? 根节点(root) 吗? 不一定.
大部分情况下首节点都是红黑树的根节点, 因为每次改变树的结构时, 都会调用下面的 moveToFront 方法将根移动到 table 数组里
- static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
- int n;
- if (root != null && tab != null && (n = tab.length)> 0) {
- int index = (n - 1) & root.hash;
- TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
- if (root != first) {
- Node<K,V> rn;
- tab[index] = root;
- TreeNode<K,V> rp = root.prev;
- if ((rn = root.next) != null)
- ((TreeNode<K,V>)rn).prev = rp;
- if (rp != null)
- rp.next = rn;
- if (first != null)
- first.prev = root;
- root.next = first;
- root.prev = null;
- }
- assert checkInvariants(root);
- }
- }
代码涉及到很多细节, 只想了解基本思路的话, 无需都看懂. 但请注意第 8 行, root 被放到 table 中. 这时, 根节点就是首节点了.
但是, 有一个例外情况, 就是在 Iterator 中 remove 一个数据时
- Map<Integer, String> m = new HashMap<>();
- ...
- Iterator<Entry<Integer, String>> it = m.entrySet().iterator();
- it.remove();
为什么呢? 注意 moveToFront 方法的第 10-17 行, 改变了一些节点的 next 和 prev 指针, 也就是改变了链表的顺序. 因为 root 节点必须同时是链表的头节点. 但是,(1)中说过, Iterator 是靠链表遍历的, 因此它不能随便改变链表的顺序, 也就不会移动 root.
这里需要多说一句, 虽然单个 bin 中的数据构成链表, 但不同 bin 的数据却没有联系, 而且 moveRootToFront 还会改变链表顺序. 因此, HashMap 不是一个有序的数据结构.
(3)树中的数据如何比较
红黑树中的数据必须是可以比较的. 那么 HashMap 的树如何比较呢. 比较顺序如下:
a. 首先, 比较 key 的 hashCode;
b. 如果 hashCode 相同, 检查 key 是否是 Comparable 的. 是的话, 直接比较 key;
c. 如果 key 不是 Comparable 的, 或者两个 key 比较结果相同, 则比较两个 key 各自的类的字符创, 即 key.getClass().getName()// 看看你把 JDK 逼成什么样了 ;
d. 如果还是相同, 就比较两个 key 的 System.identityHashCode.
可见, 从第三步起, 事情就变得莫名诡异起来了. 这也说明了, 使用 HashMap 时, key 最好是 Comparable 类型的, 对性能有益.
五, 最后吐个槽
本文是一篇薄码文, 贴的代码很少. 因为大多数代码比较长, 又涉及诸多细节, 不好看也无益于理解整体思路.
但是, 从少数的代码中大概可以体会到, OpenJDK 的代码质量真的不高. 随处可见魔幻的变量声明和鬼畜的代码格式, 就是照着写业务代码有可能会被打死的那种. 学习 JDK 源码的主要目的是了解细节, 方便开发. 如果抱着参考优秀代码的目的, 那你算来错了地方.
当然, 这种底层的轮子, 也许开发者更多考虑的是性能和可靠性, 至于可读性或许并不那么重要.
来源: https://www.cnblogs.com/tjxing/p/10478547.html