HashMap原理及面试高频问题

2024-02-22 08:22:40

关于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
  5. …

8. HashMap 和 ConcurrentHashMap 的区别？

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

9. TreeMap

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


参考：

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


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