为什么面试官那么喜欢问HashMap

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

        很多人在面试的时候总会被问到HashMap原理,却很少有人能够回答的好,或者说回答的太粗浅,被人一下看出大概的技术水平自己却毫不知情。今天我们来研究一下为什么面试官这么喜欢问HashMap吧?

1.HashMap put()相关知识

首先我们先了解hashmap的大致原理,hashmap是由数组+链表的方式组成的,如下图:

为什么面试官那么喜欢问HashMap

上图左边的数组长度是16(初始大小),每个数组位置上放置的是一个链表(Node),put数据时,当链表中的key的hash值相同时而value值不同(Java 7存入链表头部,Java 8存入链表尾部),如果key值也相同则覆盖之前的链表节点。链表长度大于8则转换为红黑树(Java 8),为什么要用红黑树后面再进行讲解,这里要详细介绍一下hash表中的有关红黑树的3个关键参数:

  • TREEIFY_THRESHOLD = 8

    一个桶的树化阈值,桶中元素超过这个值才使用红黑树节点替换链表节点,这个值必须为8,要不然频繁转换效率也不高。

  • static final int UNTREEIFY_THRESHOLD = 6

    一个树的链表还原阈值,当扩容时,会进行重新hash(Java 7 全部重新hash,Java 8部分重新hash)桶中元素个数小于这个值时,就会把树形的桶元素还原为链表结构。这个值至多为6。

  • static final int MIN_TREEIFY_CAPACITY = 64

    /**
    * The smallest table capacity for which bins may be treeified.
    * (Otherwise the table is resized if too many nodes in a bin.)
    * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
    * between resizing and treeification thresholds.
    */

对于第三点尚有疑问,上面是从源码中拷贝的注释,我个人理解是哈希表的最小的被树形化的值是64,然后后面什么防止树形化和扩容冲突至少是32,我的疑问是链表长度超过8不就转化为红黑树了吗,这个值具体含义也不是很理解,希望大家指点。

2.为什么要引入红黑树?

JDK 1.8以前是数组+链表,还未引入红黑树,这就导致了链表过长时查找的时间复杂度是O(n), 完全失去了设计HashMap时的设计初衷,针对这种情况JDK 1.8引入了红黑树(查找的时间复杂度为O(logN),什么是红黑树呢,红黑树是一种自平衡的二叉查找树,不是一种绝对平衡的二叉树,它放弃了追求绝对平衡,追求大致平衡,在与平衡二叉树的时间复杂度相差不大的情况下,保证每次插入最多只需要三次旋转就能达到平衡,实现起来也更为简单。从而获得更高的查找性能。

3.为什么初始值大小为2的n次方

hashmap的初始值是16,即2的4次方,之后的每次扩容都是两倍扩容,为什么要这么设计呢?我觉得有一下几点:

  • 如果往hashmap中存放数据,我们首先得保证它能够尽量均匀分布,为了保证能够均匀分布,我们可能会想到用取模的方式去实现,如果用传统的‘%’方式来实现效率不高,当大小(length)总为2的n次方时,h&(length-1)运算等价于对length取模,也就是h%lenth,但是&比%具有更高的效率,同时也减少了hash碰撞。

  • 和h&(length-1)相关,当容量大小(n)为2的n次方时,n-1 的二进制的后几位全是1,在h为随机数的情况下,与(n-1)进行与操作时,会分布的更均匀,想一想,如果n-1的二进制数是1110,当尾数为0时,与出来的值尾数永远为0,那么0001,1001,1101等尾数为1的位置就永远不可能被entry占用,就造成了空间浪费。

在hashmap源码中,put方法会调用indexFor方法,这个方法主要是根据key的hash值找到这个entry在table中的位置,最后 return 的是 h&(length-1)

4.HashMap和其他数据结构的关联

  • 与Hashtable的关系,Hashtable是线程安全的,比如put,get等很多使用了synchronized修饰,和ConcurrentHashMap相比,在Hashtable的大小增加到一定的时候,效率会急剧下降,因为迭代时需要被锁定很长的时间,ConcurrentHashMap引入了分割,仅仅需要锁定map的某个部分,所以其实效率并不高。再看看Hashtable的put方法

    public synchronized V put(K key, V value) {
       // Make sure the value is not null
       if (value == null) {
           throw new NullPointerException();
      }

       // Makes sure the key is not already in the hashtable.
       HashtableEntry<?,?> tab[] = table;
       int hash = key.hashCode();
       int index = (hash & 0x7FFFFFFF) % tab.length;
       @SuppressWarnings("unchecked")
       HashtableEntry<K,V> entry = (HashtableEntry<K,V>)tab[index];
       for(; entry != null ; entry = entry.next) {
           if ((entry.hash == hash) && entry.key.equals(key)) {
               V old = entry.value;
               entry.value = value;
               return old;
          }
      }

       addEntry(hash, key, value, index);
       return null;
    }

可以看到,里面的index是用%的方式进行取下标,看起来效率也不行啊,最后从命名上看HashMap和Hashtable,Hashtable明显没遵循驼峰式命名规则,这可能也是它被弃用原因之一(哈哈哈)。

  • 与HashSet的关系,我们先来看HashSet的add方法

    public boolean add(E e) {
       return map.put(e, PRESENT)==null;
    }

这里面的map是一个HashMap,e是放入的元素,value此时有一个统一的值:

private static final Object PRESENT = new Object();

可以看出,其实HashSet就是一个限制功能了的HashMap,如果你了解了HashMap,HashSet你自然就懂了。虽然说Set对于重复的元素不放入,倒不如直接说是底层的Map直接把原值替代了。HashSet没有提供get方法,原因同HashMap一样,Set内部是无序的,只能通过迭代的方式获取。

  • 与LinkedHashMap的关系,LinkedHashMap是一个数组+双向链表与HashMap不同,可以保证元素的迭代顺序,该迭代顺序可以是插入顺序或者是访问顺序(LRU原理)。

  • 与LinkedHashSet的关系,LinkedHashSet是继承自HashSet,底层实现是LinkedHashMap。

  • TreeSet中存放的元素是有序的(不是插入时的顺序,是有按关键字大小排序的),且元素不能重复。

5. HashMap在 Java7 和 Java8 的变化

扩容时是否全部重新hash和引入红黑树

总结

通过上面的分析,你应该明白为什么面试官那么喜欢问HashMap了,因为HashMap设计到的点太多了,可问的东西太多了,比较具有代表性,如果能够充分了解HashMap,也能够渐渐做到一通百通了。

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