HashMap原理及面试高频问题

关于HashMap一些面试高频问题:

  1. HashMap的底层数据结构?
  2. HashMap 的工作原理?
  3. 为什么hashmap的在链表元素数量超过8时改为红黑树?
    a. 为什么在解决hash冲突的时候,不直接用红黑树?而选择先用链表,再转红黑树?
    b. 我不用红黑树,用二叉查找树可以么?
    c. 为什么使用红黑树而不使用AVL树
    d. 那为什么阀值是8呢?
  4. HashMap是如何实现扩容的?(什么时候扩容)
  5. JDK8中对HashMap做了哪些改变?
  6. HashMap为什么是非线程安全的?
  7. HashMap 和 HashTable 的区别?
  8. HashMap 和 ConcurrentHashMap 的区别?
  9. HashMap 和 TreeMap的区别?

1. HashMap的底层数据结构

数组+链表。数组就是Entry数组,也叫table:

transient Node<K,V>[] table;

HashMap采用Entry数组来存储key-value对,每一个键值对组成了一个Entry实体,Entry类实际上是一个单向的链表结构(源码中叫Node),它具有next指针,可以连接下一个Entry实体/Node。 链表是用来解决hash冲突问题,当出现hash值一样的情形,就在数组上的对应位置形成一条链表。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
		// get/set/hashcode/equals/tostring..
    }

为什么用数组+链表? 数组是用来确定桶的位置,利用元素的key的hash值对数组长度取模得到。

JDK1.7中,使用的是链表,对于数组中的每一个元素,都可以有一条链表来存储元素。这就是有名的拉链式存储方法。

JDK1.8中,链表长度大于8的时候,链表会转成红黑树!

HashMap的数据结构图:
HashMap原理及面试高频问题

2. HashMap 的工作原理?

HashMap是基于hashing的原理,我们使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。
HashMap原理及面试高频问题

3. 为什么hashmap的在链表元素数量超过8时改为红黑树?

  • 红黑树是一个自平衡的二叉查找树,也就是说红黑树的查找效率是非常的高,查找效率会从链表的o(n)降低为o(logn)。
  • 首先说一说转换为红黑树的必要性:红黑树的插入、删除和遍历的最坏时间复杂度都是O(log(n)),而只使用单链表的时间复杂度是O(n)。因此,意外的情况或者恶意使用下导致hashCode()方法的返回值很差时,性能的下降将会是"优雅"的,只要Key具有可比性。
  • TreeNodes的大小是常规Nodes的两倍,所以只有桶中包含足够多的元素以供使用时,我们才会使用树。所以总体上来说还是空间换时间

a. 为什么在解决hash冲突的时候,不直接用红黑树?而选择先用链表,再转红黑树?

  1. 构造红黑树要比构造链表复杂,在链表的节点不多的时候,从整体的性能看来, 数组+红黑树的结构可能不一定比数组+链表的结构性能高。就好比杀鸡焉用牛刀的意思。
  2. HashMap频繁的扩容,会造成底部红黑树不断的进行拆分和重组,这是非常耗时的。因此,也就是链表长度比较长的时候转变成红黑树才会显著提高效率。

b. 我不用红黑树,用二叉查找树可以么?

  1. 之所以选择红黑树是为了解决二叉查找树的缺陷,二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了,造成树很深的问题),遍历查找会非常慢。
  2. 而红黑树在插入新数据后可能需要通过左旋,右旋、变色这些操作来保持平衡,引入红黑树就是为了查找数据快,解决链表查询深度的问题。但与此同时,红黑树的插入、拆分和重组相比于二叉查找树更耗时。

c. 为什么使用红黑树而不使用AVL树

红黑树和AVL树(平衡二叉搜索树)的区别:

  • AVL树是更加严格的平衡,因此可以提供更快的查找速度,一般读取查找密集型任务,适用AVL树。
  • 红黑树更适合于插入修改密集型任务
  • 通常,AVL树的旋转比红黑树的旋转更加难以平衡和调试。

原因总结:

  1. AVL以及红黑树是高度平衡的树数据结构。它们非常相似,真正的区别在于在任何添加/删除操作时完成的旋转操作次数
  2. 两种实现都缩放为O(logN),其中N是叶子的数量,但实际上AVL树在查找密集型任务上更快:利用更好的平衡,树遍历平均更短。另一方面,插入和删除方面,AVL树速度较慢:需要更高的旋转次数才能在修改时正确地重新平衡数据结构。
  3. 在AVL树中,从根到任何叶子的最短路径和最长路径之间的差异最多为1。在红黑树中,差异可以是2倍。
  4. 两个都O(log N)查找,但平衡AVL树可能需要O(logN)旋转,而红黑树将需要最多两次旋转使其达到平衡(尽管可能需要检查O(logN)节点以确定旋转的位置)。旋转本身是O(1)操作,因为你只是移动指针
  5. 总结用AVL树开销太大

为什么HashMap使用红黑树而不使用AVL树

d. 为什么阀值是8?

4. HashMap是如何实现扩容的?(什么时候扩容)

概括:hashmap中的元素个数超过数组大小loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,也就是说,默认情况下,数组大小为16,那么当hashmap中元素个数超过16*0.75=12的时候,就把数组的大小扩展为2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置。而这是一个非常消耗性能的操作,所以如果我们已经预知hashmap中元素的个数,那么预设元素的个数能够有效的提高hashmap的性能。扩容过程就是创建一个新的数组,其容量为旧数组的两倍,并重新计算旧数组中结点的存储位置。

流程图
HashMap原理及面试高频问题

5. jdk8中对HashMap做了哪些改变

  1. 之前jdk1.7的存储结构是数组+链表,到了jdk1.8变成了数组+链表+红黑树。(最显著改变)
  2. 发生hash碰撞时,由头插法改为尾插法
  3. Entry被Node替代(换了一个马甲)

6. HashMap为什么是非线程安全的?

HashMap的方法都是不安全的,主要体现在三方面:

  1. put等方法没有使用synchronized关键字
  2. resize时容易发生死循环
  3. put非null元素后get出来的却是null

第一种情况比较好理解,比如有两个线程A和B,首先A希望插入一个key-value对到HashMap中,首先计算记录所要落到的桶的索引坐标,然后获取到该桶里面的链表头结点,此时线程A的时间片用完了,而此时线程B被调度得以执行,和线程A一样执行,只不过线程B成功将记录插到了桶里面,假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的,那么当线程B成功插入之后,线程A再次被调度运行时,它依然持有过期的链表头但是它对此一无所知,以至于它认为它应该这样做,如此一来就覆盖了线程B插入的记录,这样线程B插入的记录就凭空消失了,造成了数据不一致的行为。

第二种较为复杂,容易导致CPU使用率较高,具体分析

1.7中插入链表头部,是考虑到新插入的数据,更可能作为热点数据被使用,放在头部可以减少查找时间。

1.8改为插入链表尾部,原因就是防止环化。因为resize的赋值方式,也就是使用了单链表的头插入方式,同一位置上新元素总会被放在链表的头部位置,在旧数组中同一条Entry链上的元素,通过重新计算索引位置后,有可能被放到了新数组的不同位置上。

这也是HashMap不能用于多线程场景的一个重要原因。

7. HashMap 和 HashTable 的区别?

  1. Hashtable的方法是同步的,HashMap未经同步,所以在多线程场合要手动同步HashMap这个区别就像Vector和ArrayList一样。查看Hashtable的源代码就可以发现,除构造函数外,Hashtable的所有 public 方法声明中都有 synchronized 关键字,而HashMap的源代码中则连 synchronized 的影子都没有
  2. Hashtable不允许 null 值(key 和 value 都不可以),HashMap允许 null 值(key和value都可以)
  3. 哈希值的使用不同:Hashtable直接使用对象的hashCode;HashMap重新计算hash值,而且用代替求模
  4. HashTable的锁是对整张Hash表进行synchronized

8. HashMap 和 ConcurrentHashMap 的区别?

ConcurrentHashMap底层采用分段的数组+链表实现,线程安全:通过把整个Map分为N个Segment,可以提供相同的线程安全;Hashtable的synchronized是针对整张Hash表的,即每次锁住整张表让线程独占,ConcurrentHashMap允许多个修改操作并发进行,其关键在于使用了锁分离技术;有些方法需要跨段,比如size()和containsValue(),它们可能需要锁定整个表而而不仅仅是某个段,这需要按顺序锁定所有段,操作完毕后,又按顺序释放所有段的锁

9. TreeMap

TreeMap是基于红黑树的一种提供顺序访问的Map,与HashMap不同的是它的getputremove之类操作都是O(logN)的时间复杂度,具体顺序可以由指定的Comparator来决定,或者根据键的自然顺序来判断。


参考:

  1. HashMap源码分析(jdk1.8,保证你能看懂)
  2. 这21 个刁钻的HashMap 面试题,我把阿里面试官吊打了!
  3. HashMap面试指南
  4. 面试必备:HashMap、Hashtable、ConcurrentHashMap的原理与区别
上一篇:树形数据结构总结二(AVL,2-3树,红黑树,B树,B+树)


下一篇:常问的数据结构与算法