400电话网络推广商城网站,百度收录哪个网站多,国内最新新闻摘抄2023年,百度问问转载自 Java 8 HashMap键与Comparable接口 这篇文章主要介绍了 Java 8 在 HashMap 哈希冲突处理方面的新特性。
相对之前的版本#xff0c;Java 8 在许多方面有了提升。其中有很多类被更新了#xff0c;HashMap 作为最常使用的集合类之一也不例外。这篇文章将介绍 Java 8 中…转载自 Java 8 HashMap键与Comparable接口 这篇文章主要介绍了 Java 8 在 HashMap 哈希冲突处理方面的新特性。
相对之前的版本Java 8 在许多方面有了提升。其中有很多类被更新了HashMap 作为最常使用的集合类之一也不例外。这篇文章将介绍 Java 8 中的 HashMap 在处理哈希冲突时的新特性。
让我们从头开始。最容易使 HashMap 发生哈希冲突的方法是什么呢我们可以创建一个类让它的哈希函数返回一个最糟糕的结果 —— 比如一个常数。这也是我在面试的时候经常问面试者的问题哈希方法返回常数会造成什么结果有很多次面试者会回答说 map 集合里会有且仅有一个元素因为 map 中的旧元素总会被新的覆盖。这个回答当然是错误的。哈希冲突并不会导致 HashMap 覆盖一个已经存在于集合中的元素这种情况只会在使用者试图向集合中放入两个元素并且它们的键对于 equal() 方法是相等的时候才会发生。键不相等但又会产生哈希冲突的不同元素最终会以某种数据结构存储在 HashMap 的同一个桶中注意在这种情况下因为插入和查找的操作都要耗费更长的时间所以整体的性能就会受到影响。
首先我们用一个小程序来模拟哈希冲突。下面的写法可能比较夸张因为它造成的冲突比现实中多得多但这个程序对于证实哈希冲突的条件还是很重要的。
我们使用一个 Person 对象作为 map 的键以字符串作为值。下面是 Person 的具体实现有一个 firstName 字段一个 lastName 字段和一个 ID 属性其中 ID 属性以 UUID 对象表示。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public class Person { private String firstName; private String lastName; private UUID id; public Person(String firstName, String lastName, UUID id) { this.firstName firstName; this.lastName lastName; this.id id; } Override public int hashCode() { return 5; } Override public boolean equals(Object obj) { // ... pertty good equals here taking into account the id field... } // ... }
现在我们可以开始制造一些冲突。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 private static final int LIMIT 500_000; private void fillAndSearch() { Person person null; MapPerson, String map new HashMap(); for (int i0;iLIMIT;i) { UUID randomUUID UUID.randomUUID(); person new Person(fn, ln, randomUUID); map.put(person, comment i); } long start System.currentTimeMillis(); map.get(person); long stop System.currentTimeMillis(); System.out.println(stop-start millis); }
上面的代码在一台高性能计算机上运行了两个半小时。其中最后的查找操作耗费了大约 40 毫秒。现在我们对 Person 类进行修改使它实现 Comparable 接口并且添加了下面的方法 1 2 3 4 Override public int compareTo(Person person) { return this.id.compareTo(person.id); }
再一次运行之前的程序这一次在我的机器上它耗费的时间少于 1 分钟。其中最终的查找操作耗费的时间接近为 0 毫秒 —— 比之前提高了 150 倍
就像前面说的Java 8 做了很多优化其中也包括HashMap 类。在 Java 7 中两个不同的元素如果它们的键产生了冲突那么会被存储在同一个链表中。而从 Java 8 开始如果发生冲突的频率大于某一个阈值8并且 map 的容量超过了另一个阈值64整个链表就会被转换成一个二叉树。
原来如此所以对于没有实现 Comparable 的键最终的树是不平衡的而对于实现了 Comparable 的键其二叉树就会是高度平衡的。事实是这样吗不是。HashMap 内部是红黑树也就是说它总是平衡的。我通过反射机制查看了最终的树结构。对于拥有 50000 个元素不敢让数字更大了的 HashMap 来说两种不同的情况下实现或是不实现 Comparable 接口树的高度都是 19 。
那么为什么之前的实验结果会有那么大的差别呢原因在于当 HashMap 想要为一个键找到对应的位置时它会首先检查新键和当前检索到的键之间是否可以比较也就是实现了 Comparable 接口。如果不能比较它就会通过调用 tieBreakOrder(Object a,Object b) 方法来对它们进行比较。这个方法首先会比较两个键对象的类名如果相等再调用 System.identityHashCode 方法进行比较。这整个过程对于我们要插入的 500000 个元素来说是很耗时的。另一种情况是如果键对象是可比较的整个流程就会简化很多。因为键对象自身定义了如何与其它键对象进行比较就没有必要再调用其他的方法所以整个插入或查找的过程就会快很多。值得一提的是在两个可比的键相等时compareTo 方法返回 0的情况下仍然会调用 tieBreakOrder 方法。
总而言之在 Java 8 的 HashMap 里如果一个桶里存放了大量的元素它在达到阈值时就会被转换为一棵红黑树对于实现了 Comparable 接口的键来说插入或删除的操作会比没有实现 Comparable 接口的键更简单。通常如果一个桶不会发生那么多次冲突的话这整个机制不会带来多大的性能提升但起码现在我们对 HashMap 的内部原理有了更多了解。
