教育改变生活

标题: Java 8系列之重新认识HashMap(三) [打印本页]
作者: 李玮    时间: 2021-4-25 16:54
标题: Java 8系列之重新认识HashMap(三)
线程安全性
在多线程使用场景中，应该尽量避免使用线程不安全的HashMap，而使用线程安全的ConcurrentHashMap。那么为什么说HashMap是线程不安全的，下面举例子说明在并发的多线程使用场景中使用HashMap可能造成死循环。代码例子如下(便于理解，仍然使用JDK1.7的环境)：
  1. public class HashMapInfiniteLoop {  

  3.     private static HashMap<Integer,String> map = new HashMap<Integer,String>(2，0.75f);  
  4.     public static void main(String[] args) {  
  5.         map.put(5， "C");  

  7.         new Thread("Thread1") {  
  8.             public void run() {  
  9.                 map.put(7, "B");  
  10.                 System.out.println(map);  
  11.             };  
  12.         }.start();  
  13.         new Thread("Thread2") {  
  14.             public void run() {  
  15.                 map.put(3, "A);  
  16.                 System.out.println(map);  
  17.             };  
  18.         }.start();        
  19.     }  
  20. }
复制代码


其中，map初始化为一个长度为2的数组，loadFactor=0.75，threshold=2*0.75=1，也就是说当put第二个key的时候，map就需要进行resize。
通过设置断点让线程1和线程2同时debug到transfer方法(3.3小节代码块)的首行。注意此时两个线程已经成功添加数据。放开thread1的断点至transfer方法的“Entry next = e.next;” 这一行；然后放开线程2的的断点，让线程2进行resize。结果如下图。
注意，Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表。
线程一被调度回来执行，先是执行 newTalbe = e， 然后是e = next，导致了e指向了key(7)，而下一次循环的next = e.next导致了next指向了key(3)。
e.next = newTable 导致 key(3).next 指向了 key(7)。注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。
于是，当我们用线程一调用map.get(11)时，悲剧就出现了——Infinite Loop。
JDK1.8与JDK1.7的性能对比
HashMap中，如果key经过hash算法得出的数组索引位置全部不相同，即Hash算法非常好，那样的话，getKey方法的时间复杂度就是O(1)，如果Hash算法技术的结果碰撞非常多，假如Hash算极其差，所有的Hash算法结果得出的索引位置一样，那样所有的键值对都集中到一个桶中，或者在一个链表中，或者在一个红黑树中，时间复杂度分别为O(n)和O(lgn)。 鉴于JDK1.8做了多方面的优化，总体性能优于JDK1.7，下面我们从两个方面用例子证明这一点。
Hash较均匀的情况
为了便于测试，我们先写一个类Key，如下：
  1. class Key implements Comparable<Key> {

  3.     private final int value;

  5.     Key(int value) {
  6.         this.value = value;
  7.     }

  9.     @Override
  10.     public int compareTo(Key o) {
  11.         return Integer.compare(this.value, o.value);
  12.     }

  14.     @Override
  15.     public boolean equals(Object o) {
  16.         if (this == o) return true;
  17.         if (o == null || getClass() != o.getClass())
  18.             return false;
  19.         Key key = (Key) o;
  20.         return value == key.value;
  21.     }

  23.     @Override
  24.     public int hashCode() {
  25.         return value;
  26.     }
  27. }
复制代码


这个类复写了equals方法，并且提供了相当好的hashCode函数，任何一个值的hashCode都不会相同，因为直接使用value当做hashcode。为了避免频繁的GC，我将不变的Key实例缓存了起来，而不是一遍一遍的创建它们。代码如下：
  1. public class Keys {

  3.     public static final int MAX_KEY = 10_000_000;
  4.     private static final Key[] KEYS_CACHE = new Key[MAX_KEY];

  6.     static {
  7.         for (int i = 0; i < MAX_KEY; ++i) {
  8.             KEYS_CACHE[i] = new Key(i);
  9.         }
  10.     }

  12.     public static Key of(int value) {
  13.         return KEYS_CACHE[value];
  14.     }
  15. }
复制代码


现在开始我们的试验，测试需要做的仅仅是，创建不同size的HashMap（1、10、100、......10000000），屏蔽了扩容的情况，代码如下：
  1.   static void test(int mapSize) {

  3.         HashMap<Key, Integer> map = new HashMap<Key,Integer>(mapSize);
  4.         for (int i = 0; i < mapSize; ++i) {
  5.             map.put(Keys.of(i), i);
  6.         }

  8.         long beginTime = System.nanoTime(); //获取纳秒
  9.         for (int i = 0; i < mapSize; i++) {
  10.             map.get(Keys.of(i));
  11.         }
  12.         long endTime = System.nanoTime();
  13.         System.out.println(endTime - beginTime);
  14.     }

  16.     public static void main(String[] args) {
  17.         for(int i=10;i<= 1000 0000;i*= 10){
  18.             test(i);
  19.         }
  20.     }
复制代码


在测试中会查找不同的值，然后度量花费的时间，为了计算getKey的平均时间，我们遍历所有的get方法，计算总的时间，除以key的数量，计算一个平均值，主要用来比较，绝对值可能会受很多环境因素的影响。结果如下：
通过观测测试结果可知，JDK1.8的性能要高于JDK1.7 15%以上，在某些size的区域上，甚至高于100%。由于Hash算法较均匀，JDK1.8引入的红黑树效果不明显，下面我们看看Hash不均匀的的情况。
Hash极不均匀的情况
假设我们又一个非常差的Key，它们所有的实例都返回相同的hashCode值。这是使用HashMap最坏的情况。代码修改如下：
  1. class Key implements Comparable<Key> {

  3.     //...

  5.     @Override
  6.     public int hashCode() {
  7.         return 1;
  8.     }
  9. }
复制代码


仍然执行main方法，得出的结果如下表所示：
从表中结果中可知，随着size的变大，JDK1.7的花费时间是增长的趋势，而JDK1.8是明显的降低趋势，并且呈现对数增长稳定。当一个链表太长的时候，HashMap会动态的将它替换成一个红黑树，这话的话会将时间复杂度从O(n)降为O(logn)。hash算法均匀和不均匀所花费的时间明显也不相同，这两种情况的相对比较，可以说明一个好的hash算法的重要性。
测试环境：处理器为2.2 GHz Intel Core i7，内存为16 GB 1600 MHz DDR3，SSD硬盘，使用默认的JVM参数，运行在64位的OS X 10.10.1上。小结
(1) 扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。
(2) 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。
(3) HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。
(4) JDK1.8引入红黑树大程度优化了HashMap的性能。
(5) 还没升级JDK1.8的，现在开始升级吧。HashMap的性能提升仅仅是JDK1.8的冰山一角。





欢迎光临 教育改变生活 (http://bbs.goldoar.com/) Powered by Discuz! X3.2