1 概述

• HashMap是使用哈希表实现的Map

• 哈希表概述

  • 哈希表是根据键而直接访问值的数据结构。

若键为k，则其值存放在f(k)的存储位置上，由此，不需比较便可直接取得所查记录。
称f()为哈希函数，按这个思想建立的表为哈希表。

• 实际工作中需视不同的情况采用不同的哈希函数
• 对不同的键可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，这种现象称为冲突。

具有相同函数值的键对该散列函数来说称做同义词。

2 扰动函数

扰动函数指的就是HashMap的hash()方法。使用hash()方法是为了防止一些实现比较差的hashCode()方法增加冲突，而使用扰动函数之后可以减少hash冲突
扰动函数，令key的hashCode的高16位和低16位相异或，使得32位都参与运算，这样hash更均匀，减少冲突

static final int hash(Object key) {
  int h;
  // ^ ：按位异或
  // >>>:无符号右移，忽略符号位，空位都以0补齐
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

3 JDK8之前底层实现

• JDK1.8之前HashMap底层是数组和链表结合在一起使用，也就是链表散列。

• 过程

HashMap首先获得key的hashCode，然后hashCode经过扰动函数（HashMap.hash()方法）处理后得到hash值，然后根据公式(n-1) & hash计算当前元素存放的位置（这里的n指的是数组的长度）。

• 冲突

如果当前位置存在元素的话，就判断该元素与要存入的元素的hash值以及key是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

• 拉链法

拉链法很简单，遇到哈希冲突时，将冲突的值加到链表中即可，加入链表时采用头插法。

4 JDK1.8之后底层实现

• JDK1.8之后，在解决哈希冲突时有了较大的变化

• 当链表长度大于阈值（默认为 8）时，判断当前数组的长度，如果小于64则对数组进行扩容，否则将链表转化为红黑树，以减少搜索时间

5 红黑树

• TreeMap、TreeSet以及JDK1.8之后的HashMap底层都用到了红黑树。

• 二叉排序树/二叉查找树/二查搜索树定义

  • 二叉排序树的性质就是左子树上所有结点的值均小于它的根节点的值，右子树上所有结点的值均大于它的根节点的值。
  • 在一般情况下，查询效率比链表结构要高，但是当结点插入序列有序时，二叉排序树将退化为链表。

• 平衡二叉树（AVL树）定义

  • 平衡二叉树是一种结构平衡的二叉搜索树，在结点插入时通过旋转操作使得叶节点高度差的绝对值不超过1，很好的解决了二叉查找树退化成链表的问题。
  • 平衡二叉树把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。

但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间

• 红黑树定义

  • 红黑树是一种平衡二叉树的变体
  • 红黑树的左右子树高差有可能大于1，所以红黑树不是严格意义上的平衡二叉树（AVL）
  • 由于每一棵红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法，即在查找过程中不需要颜色信息
  • 红黑树保证在O(logN)时间内做查找，插入和删除操作

• 红黑树与AVL树的复杂度对比

空间复杂度

• 红黑树和AVL树都没有利用额外空间，所以他们空间复杂度都为O(1)

时间复杂度

• AVL树和红黑树查询时间复杂度均为O(logN)，平均查询时间红黑树稍微慢一点。
• 对于插入和删除节点，AVL树和红黑树最坏情况下时间复杂度均为O(logN)，但在自平衡的时候，红黑树由于有黑色节点的存在，每次父节点为黑色时复杂度降为O(1)。根据特性4和特性5，得出红黑树的每条路径上黑节点数量大于等于红节点数量，所以至少50%的概率父节点为黑色，所以红黑树自平衡的平均时间复杂度小于等于AVL树平均时间复杂度的一半。
• 因此相比于AVL树来说，由于红黑树进行平衡的代价较低，平均统计性能要强于AVL树。

• 红黑树特性

特性1：每个节点上都有存储位表示节点的颜色，可以是红或黑。
特性2：根节点是黑色
特性3：null节点是黑色（color=black;value=null）。
特性4：红色节点的子节点必须是黑色的
特性5：任意一个节点到所有null节点的路径上包含相同数目的黑色节点。（红黑树不是完美平衡，但是黑色完美平衡）

• 特性4和特性5作为约束可以保证任意节点到所有null节点的路径最长不会超过最短路径的两倍
• 最极端情况下，最短路径都是黑节点，最长路径是红黑节点相间构成，路径上红节点数量=黑节点数量。

此时最长路径是最短路径的两倍。

1 旋转

• 旋转的目的

红黑树的基本操作是查找、添加和删除。在添加或删除红黑树中的节点之后，红黑树就发生了变化，可能无法满足红黑树的特性。通过旋转，可以使这颗树重新成为红黑树。简单点说，旋转的目的是让树保持红黑树的特性。

• 红黑树的旋转包括两种：左旋和右旋

左旋

• 对节点x进行左旋，意味着将x变成一个左子节点。
• 如果x的右子节点有左子节点，左旋后，该左子节点将变为x的右子节点。

右旋

• 对节点x进行右旋，意味着将x变成一个右子节点。
• 如果x的左子节点有右子节点，右旋后，该右子节点将变为x的左子节点。

2 插入节点

• 向红黑树插入节点的三个步骤

1. 将红黑树当作一颗二叉查找树，将节点插入。
2. 将插入的节点着色为”红色”。

着色为红色是保证红黑树的特性5

1. 通过一系列的旋转或着色等操作来修正树，使之重新成为一颗红黑树。

第二步中，将插入节点着色为红色之后，保证了红黑树的特性5，但是可能会违背特性4，此时需要进行旋转或着色操作将树重新构造成红黑树。

• 插入红色节点后，树的状态可以分为三种情况，分别对应三种处理办法 | 情况说明 | 处理方法 | | —- | —- | | 插入的节点是根节点 | 直接把插入的节点涂为黑色 | | 插入的节点的父节点是黑色 | 什么也不需要做，插入后树仍然为红黑树 | | 插入的节点的父节点是红色 | 这种情况下，插入节点是一定存在非空祖父节点，并且插入节点也一定存在叔叔节点（即使叔叔节点为空，我们也视之为存在，因为空节点本身就是黑色节点）。此时我们依据叔叔节点的情况，进一步划分为以下三种情况 |

处理以下三种情况的核心思路：将红色的节点移到根节点，然后将根节点设为黑色。
1.父节点是红色，叔叔节点也是红色

• 处理策略
  • 将“父节点”设为黑色。
  • 将“叔叔节点”设为黑色。
  • 将“祖父节点”设为红色。（父节点是红色，祖父节点一定是黑色）
  • 将“祖父节点”视为插入节点，之后根据情况对当前的“插入节点”进行处理。
• 原因
  • 令“祖父节点”的代号为G；“父节点”的代号为F；“叔叔节点”的代号为U；“插入节点”的代号为S。
  • “插入节点”和“父节点”都是红色，违背特性4。所以，将“父节点”设置为黑色以解决这个问题。

但是将“父节点”由红色变成黑色之后，因为包含“父节点”的分支的黑色节点的总数增加了1，所有违背了特性5（以“父节点”为起始节点的分支黑色节点的总数也增加了1，但是不违背特性5）。

• 解决这个问题的办法是将“祖父节点”由黑色变成红色，同时，将“叔叔节点”由红色变成黑色。

因为包含“父节点”的分支的黑色节点的总数增加了1也意味着包含“祖父节点”的分支的黑色节点的总数增加了1，因此我们可以通过将“祖父节点”由黑色变成红色来解决包含“祖父节点”的分支的黑色节点的总数增加了1的问题。
但是，这样处理之后又会引起另一个问题，即包含“叔叔”节点的分支的黑色节点的总数减少了1，我们已知“叔叔节点”是红色的，将“叔叔节点”设为黑色就能解决这个问题。

• 按照上面的步骤处理之后，插入节点、父节点、叔叔节点之间都不会违背红黑树特性，但祖父节点却不一定。此时我们将“祖父节点”视为新的“插入节点”，对其进行新一轮分析。例如“祖父节点”是根节点的话，直接将“祖父节点”变为黑色即可。

2.父节点是红色，叔叔节点黑色，且插入节点是父节点的右孩子

• 处理策略
  • 以“父节点”为支点进行左旋
  • 将原先的“父节点”视为新的“插入节点”
• 原因
  • 令“父节点”的代号为F，“插入节点”的代号为S。
  • 以F为支点进行左旋的原因

根据已知条件可知，S是F的右孩子。而我们处理红黑树的核心思想是将红色的节点移到根节点，然后将根节点设为黑色。既然要将红色的节点移到根节点，那就是说要不断的将破坏红黑树特性的红色节点上移。 而S又是一个右孩子，因此，我们可以通过左旋来将S上移

• 不以S为“插入节点”继续处理，而以F为“插入节点”来进行处理的原因

因为左旋之后，F变成了S的“子节点”，并且也是红色的，而我们处理问题的时候，需要从下至上进行处理，也就是说必须先解决孩子的问题，再解决父亲的问题。所以将“父节点”作为“插入节点”。

3.父节点是红色，叔叔节点黑色，且插入节点是父节点的左孩子

• 处理策略
  • 将“父节点”设为黑色。
  • 将“祖父节点”设为红色。
  • 以“祖父节点”为支点进行右旋。
• 原因
  • 令“祖父节点”的代号为G；“父节点”的代号为F；“叔叔节点”的代号为U；“插入节点”的代号为S。
  • S和F都是红色，将F由红色变为黑色，就解决了违背特性4的问题，但却违背了特性5，因为将F由红色改为黑色之后，所有经过F的分支的黑色节点的个数增加了1。此时可以将G由黑色变成红色，同时以G为支点进行右旋来解决。

3 删除节点

• 删除红黑树节点的两个步骤

1. 将红黑树当作一颗二叉查找树，将节点删除。

这里删除节点时和常规二叉树中删除节点的方法是一样的，分三种情况

• 被删除节点没有儿子

直接删除将节点，并用null节点（黑色）顶替它的位置。

• 被删除节点只有一个儿子。

直接删除该节点，并用该节点的唯一子节点顶替它的位置。

• 被删除节点有两个儿子。

找出中序遍历中被删除节点的后继节点，然后将后继节点的内容（包括颜色）复制给该节点，最后删除它的后继节点。
由于后继节点不可能有两个儿子，所以删除后继节点后，转为上述两种情况。

1. 通过一系列的旋转或着色等操作来修正树，使之重新成为一颗红黑树。

删除节点之后，红黑树可能会违背红黑树的特性，所以需要通过旋转或重新着色来修正，使之重新成为一棵红黑树。

• 在删除节点后，原红黑树的性质可能被改变

如果删除的是红色节点，那么原红黑树的性质依旧保持，此时不用做修正操作
如果删除的节点是黑色节点，原红黑树的性质可能会被改变，有以下三种情况

• 如果删除节点不是树的唯一节点，那么删除节点的那一个支的到各null节点的黑色节点数会发生变化，此时性质5被破坏。
• 如果被删节点的唯一非空子节点（被删节点至多有一个非空子节点）是红色，而被删节点的父节点也是红色，那么性质4被破坏。
• 如果被删节点是根节点，而它的唯一非空子节点是红色，则删除后新根节点将变成红色，违背性质2。

• 修复红黑树

被删节点是黑色节点的话，我们就需要修复红黑树。

• 可以从顶替被删节点的那个节点开始调整，将该节点标记为x，并认为它有额外的黑色。这里并不是给x加上除红与黑的另一种颜色，这里只是一种假设，可以认为额外的黑色是被删节点继承给x的。因此现在x可以容纳两种颜色，如果x原来是红色，那么现在是红+黑，如果x原来是黑色，那么现在是黑+黑。x添加了额外的黑色，原红黑树性质5就能保持不变，但是违背了性质1。现在需要恢复红黑树的性质1、性质2和性质4。
• 上一步操作后，根据x的情况，可以分为三种情况，分别对应三种处理方法 | 情况说明 | 处理方法 | | —- | —- | | x的颜色是“红+黑” | 直接把x设为黑色，此时红黑树性质全部恢复。 | | x的颜色是“黑+黑”，且x是根节点 | 什么都不做，此时红黑树性质全部恢复。 | | x的颜色是“黑+黑”，且x不是根节点 | 这种情况可以分为4种子情况，如下 |

处理以下情况的核心思想：将x包含的额外的黑色不断沿树上移
1.x是“黑+黑”节点，x的兄弟节点是红色（此时x的父节点和x兄弟节点的子节点都是黑色）

• 处理策略
  • 将x的兄弟节点设为“黑色”。
  • 将x的父节点设为“红色”。
  • 当x是父节点的左儿子，以父节点为支点左旋，否则右旋
• 原因

上述处理后，红黑树的性质5仍没有违反，只是把问题转化为兄弟结点为黑色的情况。

2.x是”黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的两个孩子都是黑色

• 处理策略
  • 将x的兄弟节点设为“红色”。
  • 设置x的父节点为新的x节点。
• 原因
  • 首先需要明确的是这个情况的处理思想是将x中额外的黑色上移。
  • x是“黑+黑”节点，我们将x由“黑+黑”节点变成黑色节点，额外的黑色转移到x的父节点中（若x的父节点原先是黑色，则此时变成了“黑+黑”；若x的父节点原先是红色，则此时变成了“红+黑”)。
  • 此时所有经过x的分支中黑色节点个数没变化，但是所有经过x的兄弟节点的分支中黑色节点的个数增加了1。为了不违背红黑树的性质5，将x的兄弟节点由黑色变成红色。
  • 经过上面的步骤，额外的黑色已经跑到x的父节点中。我们需要将x的父节点设为新的x节点。若此时x是“黑+红”，直接将x设为黑色，即可完全解决该问题；若x是“黑+黑”，则需要对x进行进一步处理（虽然重新开始处理，但是成功地将额外的黑色上移了）。

3.x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的

• 处理策略
  • 将x兄弟节点的左孩子设为“黑色”。
  • 将x兄弟节点设为“红色”。
  • 以x的兄弟节点为支点右旋
• 原因
  • 上述处理是为了将该情况转换成下一种情况，从而进行进一步的处理。
  • 转换的方式是对x的兄弟节点进行右旋。为了不违背红黑树的性质5，就需要在右旋前将x的兄弟节点的左孩子设为黑色，同时将x的兄弟节点设为红色。

4.x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的，左孩子是任意颜色

• 处理策略
  • 将x兄弟节点的颜色设为x父节点的颜色
  • 将x父节点设为黑色
  • 将x兄弟节点的右子节设为黑色
  • 以x的父节点为支点进行左旋（假设x是左儿子）
  • 将x额外的黑色转移给根节点，然后设置x为根节点
• 原因
  • 理解处理策略的核心，是理解核心思想：去掉当前节点额外的黑色。
  • 处理的目的是去掉x中额外的黑色，将x变成单独的黑色。为了便于说明，设置x的兄弟节点为B，兄弟节点的左孩子为BLS，兄弟节点的右孩子为BRS，x的父节点为F。
  • 我们要对F进行左旋。但在左旋前，我们需要调换F和B的颜色，并设置BRS为黑色。为什么需要这里处理呢？因为左旋后，F和BLS是父子关系，而我们已知BL是红色，如果F是红色，则违背了特性4，因此我们将F设置为黑色。
  • F设置为黑色之后，为了保证满足特性5，即为了保证左旋之后：

a. 同时经过根节点和x的分支的黑色节点个数不变
要满足a，只需要x将额外的黑色转移给根节点即可。因为S的颜色是“黑+黑”，而左旋后同时经过根节点和x的分支的黑色节点个数增加了1，因此只需将S由“黑+黑”变成单独的黑色，将额外的黑色交由根节点处理即可。
b. 同时经过根节点和BLS的分支的黑色节点数不变
之前我们已经将F设置为黑色（即将B的颜色黑色，赋值给了F），因此要满足b，只需要将F的原始颜色赋值给B即可。即调换F和B的颜色。
c. 同时经过根节点和BRS的分支的黑色节点数不变
在b已经满足的情况下，若要满足c，只需要将BRS设置为黑色即可。

• 经过上面的处理，加上根节点作为x处理后，红黑树的特性全部得到的满足