为什么面试官那么喜欢问HashMap(二)

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

昨天晚上写了一篇为什么面试官那么喜欢问HashMap,今天收到一些读者反馈,加上自己感觉写得还不够完整,所以决定对上一篇的内容加一些补充,希望大家多多指点。

Java7 和 Java8 HashMap的区别

首先从扩容时是否会全部进行重新hash来说,Java7 是全部重新hash,Java8 是部分数据根据之前的hash值重新计算位置,提升了效率,主要讲一下Java8 是如何操作的,因为每次扩容都是2次幂的扩展,长度扩展为原来的2倍,了解源码后可以发现,扩展后元素的位置要么是在原位子,要么是在原位置再移动2次幂的位置,可以通过下图来了解,n表示table的长度,也就是总容量。图a 表示扩容前key1和key2两种key确定索引位置的实例,此时HashMap的总大小是16,n-1的值为15,转化为二进制(32位)最后四位是1111(因为前面都是0,0与任何数都是0),上篇文章讲到通过与的方式确定索引位置,key1的hash值与n-1进行与计算,也就是h&(length-1),这里的length就是n,同理我们也可以计算出key2的索引位置(图a右侧)。

为什么面试官那么喜欢问HashMap(二)

扩容前的情况我们了解了。接下来是扩容后(图b),扩容后的大小是32,n-1的值是31,转化为二进制就是11111(前面27位都是0)。接下来我们来看key1和key2的位置是否会变化,key1的hash值的最后5位为00101(为什么就算后5位呢,因为是与方式来进行的[h&(n-1)],n-1的前27位都是0啊),key2的hash值的最后5位是10101,元素重新计算hash之后,n-1的mask范围在高位多1bit(红色),所以新的index就会方式这样的变化

为什么面试官那么喜欢问HashMap(二)

所以我们再扩充HashMap的时候,不需要想Java7那样重新计算hash,只要看原来的hash值新增的那个bit是1还是0就好了,0的话索引没变,是1的话索引就变成“原索引+oldCap"。key1的hash值新增的那位是0,所以没变,key2的hash值新增的那位是1,所以发生变化了。

这样设计既省去了重新计算了hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此在resize的过程,均匀的把之前冲突的节点分散到新的bucket了。

接下来就是Java8引入了红黑树,在查找效率上提升了不少(二分查找),至于为什么超过8的时候链表才转化为红黑树,想一想3层的满二叉树的节点也就7个,如果数据量很小就开始转化用上红黑树,那么就有一种杀鸡有宰牛刀的感觉呢,而且转化本身也涉及一定的耗时。

最后我们来对比Java7 和 Java8 版本 HashMap的效率,首先我们自定义一个key类,然后重写equals方法,并提供了相当好的hashcode方法,任何值的hashcode都不会相同,下面是测试结果:

为什么面试官那么喜欢问HashMap(二)

可以看到,性能一般会提高15%,某些情况甚至提示好几倍。

继续测试,我们再实现一种hash极不均匀的情况,就是每个key的hashcode都返回相同的值。对比一下结果,Java7 版本的花费时间是增长的趋势,而Java8 是明显的降低趋势,并且呈现对数增长稳定。

为什么面试官那么喜欢问HashMap(二)

通过上述两种情况的对比,Java8 的效率明显要高出很多,也足以证明一个好的hash算法的重要性。


链表长度大于8一定会转化成红黑树吗?

下面做个小测验,链表长度大于8是否一定会转化成红黑树,首先我们自定义一个key类

private class Key implements Comparable<Key> {

   private final int value;

   Key(int value) {
       this.value = value;
  }

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

   @Override
   public boolean equals(Object o) {
       if (this == o) return true;
       if (o == null || getClass() != o.getClass())
           return false;
       Key key = (Key) o;
       return value == key.value;
  }

   @Override
   public int hashCode() {
       return 1;
  }
}

可以看到我重写了hashcode方法,所有的key的hashcode的值都是1,下面是我的测试方法

public void test(){
   Map<Key, String> map = new HashMap<>();
   map.put(new Key(1), "13");
   map.put(new Key(2), "23");
   map.put(new Key(3), "33");
   map.put(new Key(4), "43");
   map.put(new Key(5), "53");
   map.put(new Key(6), "63");
   map.put(new Key(7), "73");
   map.put(new Key(8), "83");
   map.put(new Key(9), "93");
   map.put(new Key(10),"103");
   map.put(new Key(11),"104");
   map.put(new Key(12),"123");
}

我们可以先大致预想一下结果,一开始前8个数都是在同一个链表上,然后超过8个转化为红黑树。还记得昨天讲到的红黑树的第三个关键参数

static final int MIN_TREEIFY_CAPACITY = 64

然后我们再看看链表转化为红黑树的源码,可以得出

为什么面试官那么喜欢问HashMap(二)

就算链表长度超过8,进入了这个转化为红黑树的方法,仔细看第756行,还是要判断当前容量的大小是否小于64,如果小于这个值还是要进行扩容而不是转化为红黑树,然后你应该可以看到上面那个test()方法的结果了,在put第9个值后,扩容为32,put第10个值后,扩容为64,这时链表的长度已经超过8了啊(因为已经写死了hashcode方法),直到put第11个值后,才开始转化为红黑树。下面是我用调试这个方法时的截图,可供参考

为什么面试官那么喜欢问HashMap(二)

扩容为32

为什么面试官那么喜欢问HashMap(二)

扩容为64

为什么面试官那么喜欢问HashMap(二)

HashMap并发的问题

HashMap不是线程安全的,在Java7 中,HashMap被多个线程操作可能造成形成环形链表,造成死循环。可以用ConcurrentHashMap来解决,Java7 中ConcurrentHashMap 是用分段锁的方式实现的,也就是二级哈希表。在Java8 中的实现方式是通过Unsafe类的CAS自旋赋值+synchronized同步+LockSupport阻塞等手段实现的高效并发,代码可读性稍差。最大的区别在于JDK8的锁粒度更细,理想情况下talbe数组元素的大小就是其支持并发的最大个数。

对于形成环形链表,如何判断链表中是否存在环,最简单的就是通过两个快慢的指针遍历链表,如下代码。环的入口点的就自行Google吧。

public static boolean isHasRoundList(ListNode head){
   ListNode quick = head;
   ListNode slow = head;
   while (quick != null && quick.next != null){
       quick = quick.next.next;
       slow = slow.next;
       if (quick.number == slow.number){
           return true;
      }
  }
   return false;
}


最最重要的

作为一名程序员,下面给你一个判断

if(我写的有帮助到你){
   加个关注
}
if(下面那个可乐很好喝){
   点一下好看
}

为什么面试官那么喜欢问HashMap(二)

原文始发于微信公众号(九局下半大逆转):为什么面试官那么喜欢问HashMap(二)