引入
JDK 1.8 的 HashMap 和 ConcurrentHashMap 都有如许一个特点:最开始的 Map 是空的,因为内里没有任何元素,往里放元素时管帐算 hash 值,计算之后,第 1 个 value 会起首占用一个桶(也称为槽点)位置,后续如果颠末计算发现需要落到同一个桶中,那么便会使用链表的情势今后延长,俗称“拉链法”。
当链表长度大于或即是阈值(默以为 8)的时候,如果同时还满意容量大于或即是MIN_TREEIFY_CAPACITY(默以为 64)的要求,就会把链表转换为红黑树。同样,后续如果由于删除或者其他原因调解了巨细,当红黑树的节点小于或即是 6 个以后,又会恢复为链表形态。
更多的时候我们会关注,为何转为红黑树以及红黑树的一些特点,但是为什么转化的这个阈值要默认设置为 8 呢?
原因梳理
要想知道为什么设置为 8,那起首我们就要知道为什么要转换,因为转换是第一步。
每次遍历一个链表,平均查找的时间复杂度是 O(n),n 是链表的长度。红黑树有和链表不一样的查找性能,由于红黑树有自均衡的特点,可以防止不均衡环境的发生,所以可以始终将查找的时间复杂度控制在 O(log(n))。最初链表还不是很长,所以可能 O(n) 和 O(log(n)) 的区别不大,但是如果链表越来越长,那么这种区别便会有所体现。所以为了提拔查找性能,需要把链表转化为红黑树的情势。
那为什么不一开始就用红黑树,反而要履历一个转换的过程呢?
我们可以从HashMap源码中的备注看到表明:
Implementation notes.
This map usually acts as a binned (bucketed) hash table, but when bins get too large, they are transformed into bins of TreeNodes, each structured similarly to those in java.util.TreeMap. Most methods try to use normal bins, but relay to TreeNode methods when applicable (simply by checking instanceof a node). Bins of TreeNodes may be traversed and used like any others, but additionally support faster lookup when overpopulated. However, since the vast majority of bins in normal use are not overpopulated, checking for existence of tree bins may be delayed in the course of table methods.
Tree bins (i.e., bins whose elements are all TreeNodes) are ordered primarily by hashCode, but in the case of ties, if two elements are of the same "class C implements Comparable<C>", type then their compareTo method is used for ordering. (We conservatively check generic types via reflection to validate this -- see method comparableClassFor). The added complexity of tree bins is worthwhile in providing worst-case O(log n) operations when keys either have distinct hashes or are orderable, Thus, performance degrades gracefully under accidental or malicious usages in which hashCode() methods return values that are poorly distributed, as well as those in which many keys share a hashCode, so long as they are also Comparable. (If neither of these apply, we may waste about a factor of two in time and space compared to taking no precautions. But the only known cases stem from poor user programming practices that are already so slow that this makes little difference.)
Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins. In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The first values are:
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million
The root of a tree bin is normally its first node. However, sometimes (currently only upon Iterator.remove), the root might be elsewhere, but can be recovered following parent links (method TreeNode.root()).
All applicable internal methods accept a hash code as an argument (as normally supplied from a public method), allowing them to call each other without recomputing user hashCodes. Most internal methods also accept a "tab" argument, that is normally the current table, but may be a new or old one when resizing or converting.
When bin lists are treeified, split, or untreeified, we keep them in the same relative access/traversal order (i.e., field Node.next) to better preserve locality, and to slightly simplify handling of splits and traversals that invoke iterator.remove. When using comparators on insertion, to keep a total ordering (or as close as is required here) across rebalancings, we compare classes and identityHashCodes as tie-breakers.
The use and transitions among plain vs tree modes is complicated by the existence of subclass LinkedHashMap. See below for hook methods defined to be invoked upon insertion, removal and access that allow LinkedHashMap internals to otherwise remain independent of these mechanics. (This also requires that a map instance be passed to some utility methods that may create new nodes.)
The concurrent-programming-like SSA-based coding style helps avoid aliasing errors amid all of the twisty pointer operations.
翻译:
实现分析:
该映射通常作为一个分桶(基于桶的)哈希表来运作,但当桶变得过大时,它们会被转换成由 TreeNodes 构成的桶,每个 TreeNodes 的布局与 java.util.TreeMap 中的类似。大多数方法会尽量使用常规桶,但在适用时(通过检查节点的实例类型)会将操作委托给 TreeNode 方法。由 TreeNodes 构成的桶可以像其他任何桶一样被遍历和使用,但当桶中元素过多时,它们还能支持更快的查找。然而,由于在正常使用中绝大多数桶都不会元素过多,因此在表方法的执行过程中,对树桶的检查可能会被延长。
树桶(即,其元素全部为 TreeNodes 的桶)主要按 hashCode 排序,但如果两个元素的 hashCode 雷同且它们的类型是 “实现 Comparable 接口的类 C”,则会使用它们的 compareTo 方法进行排序。(我们通过反射审慎地检查通用类型以确认这一点 —— 拜见 comparableClassFor 方法)。树桶的额外复杂性在提供最坏环境下 O(log n) 操作方面是值得的,条件是键的哈希值差别或者键是可排序的。因此,当 hashCode() 方法返回的值分布不佳(无论是意外还是恶意的),以及很多键共享一个 hashCode(只要它们也是 Comparable 的)时,性能可以优雅地 degradation(原文如此,应为 “降级” 之意)。(如果这些环境都不适用,与不采取防备步伐相比,我们可能会在时间和空间上浪费约莫两倍的开销。但目前已知的环境源于用户编程实践不佳,这些实践已经如此缓慢,以至于这一点险些没有区别。)
由于 TreeNodes 的巨细约莫是普通节点的两倍,因此只有当桶中的节点数目足够多时才会使用它们(拜见 TREEIFY_THRESHOLD)。当它们变得太小(由于删除或调解巨细)时,它们会被转换回普通桶。在用户 hashCode 分布良好的环境下,树桶很少被使用。抱负环境下,在随机 hashCode 的环境下,根据默认的 0.75 的调解巨细阈值,桶中节点的频率遵照平均参数约为 0.5 的泊松分布(<http://en.wikipedia.org/wiki/Poisson_distribution>),尽管由于调解巨细的粒度较大,方差也很大。忽略方差,巨细为 k 的列表的预期出现次数为(exp(-0.5)pow(0.5,k)/ factorial(k))。前几个值是:
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million
树桶的根通常是其第一个节点。然而,偶然侯(目前仅在 Iterator.remove 时),根可能在其他地方,但可以通过父链接找到(方法 TreeNode.root())。
全部适用的内部方法都接受一个哈希码作为参数(通常由公共方法提供),以便它们可以在不重新计算用户哈希码的环境下相互调用。大多数内部方法还接受一个 “tab” 参数,通常是当前表,但在调解巨细或转换时可能是新的或旧的表。
当桶列表被树化、拆分或退树化时,我们保持它们的相对访问 / 遍历次序(即,字段 Node.next)以更好地保持局部性,并稍微简化处理拆分和遍历的操作,这些操作可能会调用 iterator.remove。在插入时使用比力器时,为了在重新均衡期间保持总次序(或尽可能靠近此地方需的次序),我们将类和 identityHashCode 作为决胜条件进行比力。
由于存在子类 LinkedHashMap,所以普通模式和树模式之间的使用和转换变得复杂。拜见下面的钩子方法,这些方法被定义为在插入、删除和访问时调用,使得 LinkedHashMap 的内部可以独立于这些机制。(这也要求将地图实例传递给一些可能创建新节点的实用方法。)
这种类似并发编程的 SSA 基于编码风格有助于在全部复杂的指针操作中制止别名错误。
其中我用红色加粗标识了重点内容,其中第一句的意思是单个 TreeNode 需要占用的空间约莫是普通 Node 的两倍,所以只有当包罗足够多的Nodes 时才会转成 TreeNodes,而是否足够多就是由 TREEIFY_THRESHOLD 的值决定的。而当桶中节点数由于移除或者 resize 变少后,又会变回普通的链表的情势,以便节省空间。
通过检察源码可以发现,默认是链表长度达到 8 就转成红黑树,而当长度降到 6 就转换回去,这体现了时间和空间均衡的思想,最开始使用链表的时候,空间占用是比力少的,而且由于链表短,所以查询时间也没有太大的问题。但是当链表越来越长,需要用红黑树的情势来包管查询的服从。对于何时应该从链表转化为红黑树,需要确定一个阈值,这个阈值默以为 8,而且在源码中也对选择 8 这个数字做了分析,正是红色加粗标识内容的后一句。它的意思是如果 hashCode 分布良好,也就是 hash 计算的效果离散好的话,那么红黑树这种情势是很少会被用到的,因为各个值都均匀分布,很少出现链表很长的环境。在抱负环境下,链表长度符合泊松分布,各个长度的掷中概率依次递减,当长度为 8 的时候,概率仅为 0.00000006。这是一个小于千万分之一的概率,通常我们的 Map 内里是不会存储这么多的数据的,所以通常环境下,并不会发生从链表向红黑树的转换。
但是,HashMap 决定某一个元素落到哪一个桶里,是和这个对象的 hashCode 有关的,JDK 并不能阻止我们用户实现自己的哈希算法,如果我们故意把哈希算法变得不均匀,例如:
- @Override
- public int hashCode() {
- return 1;
- }
复制代码 这里 hashCode 计算出来的值始终为 1,那么就很轻易导致 HashMap 里的链表变得很长。让我们来看下面这段代码:
- /**
- * HashMapDemo 类用于演示 HashMap 的使用。
- * 该类包含一个测试方法,用于测试在 HashMap 中存储对象的行为。
- */
- public class HashMapDemo {
- /**
- * 测试方法,用于演示向 HashMap 中插入大量对象的情况。
- * 此方法创建一个初始容量为 1 的 HashMap,并向其中插入 1000 个 HashMapDemo 实例。
- * 由于重写了 hashCode 方法,所有实例的哈希码都相同。
- */
- public static void main(String[] args) {
- // 创建一个初始容量为 1 的 HashMap,键的类型为 HashMapDemo,值的类型为 Integer
- HashMap map = new HashMap<HashMapDemo,Integer>(1);
- // 循环 1000 次,每次创建一个新的 HashMapDemo 实例并插入到 HashMap 中
- for (int i = 0; i < 1000; i++) {
- // 创建一个新的 HashMapDemo 实例
- HashMapDemo hashMapDemo1 = new HashMapDemo();
- // 将新实例作为键,值为 null 插入到 HashMap 中
- map.put(hashMapDemo1, null);
- }
- // 输出运行结束信息
- System.out.println("运行结束");
- }
- /**
- * 重写 hashCode 方法,确保所有 HashMapDemo 实例的哈希码都为 1。
- *
- * @return 固定返回 1
- */
- @Override
- public int hashCode() {
- return 1;
- }
- }
复制代码 在这个例子中,我们建了一个 HashMap,而且不停地往里放入值,所放入的 key 的对象,它的hashCode 是被重写过得,而且始终返回 1。这段代码运行时,如果通过 debug 让步伐暂停在System.out.println("运行竣事") 这行语句,我们观察 map 内的节点,可以发现已经变成了TreeNode,而不是通常的 Node,这分析内部已经转为了红黑树。
事实上,链表长度凌驾 8 就转为红黑树的计划,更多的是为了防止用户自己实现了不好的哈希算法时导致链表过长,从而导致查询服从低,而此时转为红黑树更多的是一种保底策略,用来包管极端环境下查询的服从。
通常如果 hash 算法正常的话,那么链表的长度也不会很长,那么红黑树也不会带来明显的查询时间上的优势,反而会增加空间负担。所以通常环境下,并没有须要转为红黑树,所以就选择了概率非常小,小于千万分之一概率,也就是长度为 8 的概率,把长度 8 作为转化的默认阈值。
所以如果平时开发中发现 HashMap 或是 ConcurrentHashMap 内部出现了红黑树的布局,这个时候每每就分析我们的哈希算法出了问题,需要留意是不是我们实现了效果不好的 hashCode 方法,并对此进行改进,以便减少冲突。
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。 |