本文针对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面试题及答案