一文讲解Java中的HashMap

先说一下HashMap的底层数据结构

• JDK 8 中 HashMap 的数据结构是数组+链表+红黑树。
  

• 数组（Node[] table）用来存储键值对。数组中的每个元素被称为“桶”（Bucket），每个桶的索引通过对键的哈希值进行 hash() 处理得到。

• 当多个键经过哈希处理后得到相同的索引时，需要通过链表来解决哈希冲突——即将具有相同索引的键值对通过链表连接起来。

• 不过，链表过长时，查询效率会比较低，于是当链表的长度超过 8 时（且数组的长度大于 64），链表就会转换为红黑树。红黑树的查询效率是 O(logn)，比链表的 O(n) 要快。

• hash() 的目标是尽量减少哈希冲突，保证元素能够均匀地分布在数组的每个位置上。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

• 如果键已经存在，其对应的值将被新值覆盖。

• 当从 HashMap 中获取元素时，也会使用 hash() 计算键的位置，然后根据位置在数组查找元素。

• HashMap 的初始容量是 16，随着元素的不断添加，HashMap 的容量可能不足，于是就需要进行扩容，阈值是capacity * loadFactor，capacity 为容量，loadFactor 为负载因子，默认为 0.75。

• 扩容后的数组大小是原来的 2 倍，然后把原来的元素重新计算哈希值，放到新的数组中，这一步也是 HashMap 最耗时的操作。

对红黑树了解多少？为什么不用二叉树/平衡树呢？

• 红黑树是一种自平衡的二叉查找树：

  1. 每个节点要么是红色，要么是黑色；

  2. 根节点永远是黑色；

  3. 所有的叶子节点都是是黑色的（下图中的 NULL 节点）；

  4. 红色节点的子节点一定是黑色的；

  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

为什么不用二叉树

• 二叉树是最基本的树结构，每个节点最多有两个子节点，但是二叉树容易出现极端情况，比如插入的数据是有序的，那么二叉树就会退化成链表，查询效率就会变成 O(n)

为什么不用平衡二叉树？

• 平衡二叉树比红黑树的要求更高，每个节点的左右子树的高度最多相差 1，这种高度的平衡保证了极佳的查找效率，但在进行插入和删除操作时，可能需要频繁地进行旋转来维持树的平衡，维护成本更高。

为什么用红黑树？

• 链表的查找时间复杂度是 O(n)，当链表长度较长时，查找性能会下降。红黑树是一种折中的方案，查找、插入、删除的时间复杂度都是 O(log n)。

红黑树是怎么保持平衡的？

• 红黑树有两种方式保持平衡：旋转和染色。

  ①、旋转：旋转分为两种，左旋和右旋
  
  
  ②、染⾊：