建站平台,网站建设与管理教程视频教程,微商自己做网站,wordpress登录后页面引入
JDK 1.8 的 HashMap 和 ConcurrentHashMap 都有这样一个特点#xff1a;最开始的 Map 是空的#xff0c;因为里面没有任何元素#xff0c;往里放元素时会计算 hash 值#xff0c;计算之后#xff0c;第 1 个 value 会首先占用一个桶#xff08;也称为槽点#xff…引入
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 ComparableC, 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.5pow0.5k/ factorialk。前几个值是 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值的类型为 IntegerHashMap map new HashMapHashMapDemo,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*/Overridepublic int hashCode() {return 1;}
}
在这个例子中我们建了一个 HashMap并且不停地往里放入值所放入的 key 的对象它的hashCode 是被重写过得并且始终返回 1。这段代码运行时如果通过 debug 让程序暂停在System.out.println(运行结束) 这行语句我们观察 map 内的节点可以发现已经变成了TreeNode而不是通常的 Node这说明内部已经转为了红黑树。 事实上链表长度超过 8 就转为红黑树的设计更多的是为了防止用户自己实现了不好的哈希算法时导致链表过长从而导致查询效率低而此时转为红黑树更多的是一种保底策略用来保证极端情况下查询的效率。
通常如果 hash 算法正常的话那么链表的长度也不会很长那么红黑树也不会带来明显的查询时间上的优势反而会增加空间负担。所以通常情况下并没有必要转为红黑树所以就选择了概率非常小小于千万分之一概率也就是长度为 8 的概率把长度 8 作为转化的默认阈值。
所以如果平时开发中发现 HashMap 或是 ConcurrentHashMap 内部出现了红黑树的结构这个时候往往就说明我们的哈希算法出了问题需要留意是不是我们实现了效果不好的 hashCode 方法并对此进行改进以便减少冲突。
