java8hashmap键与comparable接口-编程开发技术

《java8hashmap键与comparable接口-编程开发技术》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、Java8HashMap键与Comparable接口-编程开发技术Java8HashMap键与Comparable接口木文作者：ImportNew・chowchowDT未经许口J,禁止转载！这篇文章主要介绍了Java8在HashMap哈希冲突处理方面的新特性。相对Z前的版本，Java8在许多方而有了提升。其中有很多类被更新了，HashMap?作为最常使用的集合类之一也不例外。这篇文章将介绍Java8屮的HashMap在处理哈希冲突时的新特性。让我们从头开始。最容易使HashMap发生哈希冲突的方法是什么呢？我们可以创建一个类，让它的

2、哈希函数返回一个最糟糕的结果?——比如一个常数。这也是我在面试的时候经常问面试者的问题：哈希方法返回常数会造成什么结杲？有很多次而试者会回答说map集合里会冇月.仅冇一个元素，因为map屮的旧元素总会被新的覆盖。这个冋答当然是错误的。哈希冲突并不会导致HashMap覆盖一个已经存在于集合屮的元素，这种情况只会在使用者试图向集合屮放入两个元索，并且它们的键对于equal()方法是相等的时候才会发生。键不相等但又会产生哈希冲突的不同元素最终会以某种数据结构存储在HashMap的同一个桶中(注意，在这种情况下，因为插入和查找的操作都要耗费

3、更长的时间，所以整体的性能就会受到影响)。首先，我们用一个小程序来模拟哈希冲突。下面的写法可能比较夸张，因为它造成的冲突比现实中多得多，但这个程序对于证实哈希冲突的条件还是很重要的。我们使用一个Person对彖作为map的键，以字符串作为值。下而是Person的具体实现，有一个?firstName?字段，一个?lastName?字段和一个1D属性，其中ID属性以UUID对象表示。publicclassPerson{privateStringfirstName;privatcStringlastNamc;privateUUIDid;p

4、ublicPerson(StringfirstName,StringlastName,UUIDid){this,firstName二firstName;this.lastName二lastName;this・id=id;}©OverridepublicinthashCode(){return5;}©Overridepublicbooleanequals(Objectobj){//・・・perttygoodequalsheretakingintoaccounttheidfield.・・}〃…}现在我们可以开始制造一些冲突。privat

5、estaticfinalintLIMIT=500000;privatevoidfillAndSearchO{Personperson二null;Mapmap二newHashMapO();for(inti=0;i

6、et(person);longstop二System,currentTimeM订lis();System,out.println(stop-start+〃mi11is〃)；}上而的代码在一台高性能计算机上运行了两个半小时。其屮，最后的查找操作耗费了大约40毫秒。现在我们对Person类进行修改：使它实现Comparable接口，并且添加了下面的方法：©OverridepublicintcompareTo(Personperson){returnthis・id.compareTo(person・id);}再一次运行之前的程序，这一次在

7、我的机器上它耗费的吋间少于1分钟。其中,最终的查找操作耗费的时间接近为0毫秒?——比之前提高了150倍！就像前面说的，Java8做了很多优化，其中也包括IlashMap类。在Java7中，两个不同的元素，如果它们的键产生了冲突，那么会被存储在同一个链表中。而从Java8开始，如果发生冲突的频率大于某一个阈值(8),并且map的容量超过了另一个阈值(64),整个链表就会被转换成一个二叉树。原來如此！所以，对于没有实现Comparable的键，最终的树是不平衡的；而对于实现了Comparable的键,其二叉树就会是高度平衡的。事实是这样

8、吗？不是。HashMap内部是红黑树，也就是说它总是平衡的。我通过反射机制，查看了最终的树结构。对于拥冇50000个元素（不敢让数字更大了）的HashMap来说，两种不同的情况下（实现或是不实现Comparable接口）树的高度都是1