likes
comments
collection
share

JDK8util包解读-HashMap(二)经典问题

作者站长头像
站长
· 阅读数 14

本文针对HashMap日常使用中遇到的一些经典问题进行解释和总结

经典问题

1.底层数据结构是怎样的?

  • JDk8之前:数组+链表
  • JDK8及以后:数组+链表/红黑树
//数组
transient Node<K,V>[] table;
//链表
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
...
}
//红黑树
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
...
}

2.如何会发生hash冲突,该怎么解决。常见的解决方式有哪些?

哈希冲突在 HashMap 中发生在两个不同的键具有相同的哈希码的情况下。当两个键的哈希码相同时,它们会被映射到 HashMap 的同一个数组索引位置上,这就是哈希冲突。

常见的解决哈希冲突的方式包括:

  1. 链地址法(Separate Chaining):在哈希桶数组的每个位置上,使用链表来存储冲突的键值对。当发生冲突时,新的键值对会被添加到链表的末尾。这种方式不需要重新分配内存,但是在链表较长时,查找效率会降低。
  2. 开放地址法(Open Addressing):在哈希桶数组的每个位置上,存储一个键值对。当发生冲突时,通过一定的探测方法(如线性探测、二次探测等)在哈希桶数组中寻找下一个可用的位置。这种方式不使用链表,可以节省内存,但是可能会导致聚集性冲突,影响查找效率。
  3. 再哈希法(Rehashing):当发生哈希冲突时,通过应用一个不同的哈希函数来重新计算键的哈希码,以找到一个新的位置来存储冲突的键值对。

HashMap 中,采用的是链地址法来解决哈希冲突。当发生冲突时,将新的键值对添加到冲突位置的链表末尾。如果链表长度超过一定阈值(默认为8),则将链表转换为红黑树,以提高查找效率。如果红黑树的节点数量减少到一定程度(默认为6),则将红黑树转换回链表。

3.JDK8中做了哪些优化优化?

  • 数组+链表改成了数组+链表或红黑树
  • 链表的插入方式从头插法改成了尾插法
  • 扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置,1.8采用更简单的判断逻辑,位置不变或索引+旧容量大小;
  • 在插入时,1.7先判断是否需要扩容,再插入;1.8先进行插入,插入完成再判断是否需要扩容;

4.红黑树的实现原理是怎么样的,相比较于链表他的优势和劣势分别是什么?

红黑树是一种自平衡的二叉搜索树,它在实现上具有以下特点:

  1. 每个节点都有一个颜色属性,可以是红色或黑色。
  2. 根节点是黑色的。
  3. 所有叶子节点(NIL 节点,表示空节点)都是黑色的。
  4. 如果一个节点是红色的,则它的两个子节点都是黑色的。
  5. 对于每个节点,从该节点到其所有后代叶子节点的简单路径上,均包含相同数目的黑色节点。

这些特点保证了红黑树的平衡性和搜索性能。

相比于链表,红黑树的优势包括:

  1. 查找、插入和删除操作的时间复杂度都是 O(log n),其中 n 是红黑树中节点的数量。这是因为红黑树保持了相对平衡的状态,使得树的高度保持在较小的范围内,从而提供了较快的操作。
  2. 红黑树支持高效的有序遍历。由于红黑树是一种二叉搜索树,它可以方便地进行按照键的顺序进行遍历,因此在需要有序访问元素的场景下具有优势。
  3. 红黑树支持范围查询。由于红黑树的有序性,可以快速找到满足某个范围条件的节点,对于范围查询的需求,在效率上有较大的提升。

然而,红黑树也有一些劣势

  1. 相比于简单的链表结构,红黑树的实现较为复杂。需要处理节点的颜色属性、旋转操作等,使得实现和维护红黑树的过程相对复杂。
  2. 红黑树的存储空间开销相对较大。每个节点需要额外存储颜色属性,而且红黑树的平衡性需要保持,可能需要进行节点的旋转操作,增加了额外的开销。

参考

hashmap经典面试问题以及答案 HashMap面试题及答案

转载自:https://juejin.cn/post/7310124656996843546
评论
请登录