共计 15014 个字符，预计需要花费 38 分钟才能阅读完成。
作者：山猫学生 \
起源：www.cnblogs.com/king0/p/14176609.html
一、Map
1.1 Map 接口
在 Java 中, Map 提供了键——值的映射关系。映射不能蕴含反复的键, 并且每个键只能映射到一个值。
以 Map 键——值映射为根底，java.util 提供了 HashMap（最罕用）、TreeMap、Hashtble、LinkedHashMap 等数据结构。
衍生的几种 Map 的次要特点：
- HashMap：最罕用的数据结构。键和值之间通过 Hash 函数 来实现映射关系。当进行遍历的 key 是无序的
- TreeMap：应用红黑树构建的数据结构，因为红黑树的原理，能够很天然的对 key 进行排序，所以 TreeMap 的 key 遍历时是默认依照天然程序（升序）排列的。
- LinkedHashMap: 保留了插入的程序。遍历失去的记录是依照插入程序的。
1.2 Hash 散列函数
Hash（散列函数）是把任意长度的输出通过散列算法变换成固定长度的输入。Hash 函数的返回值也称为 哈希值 哈希码 摘要或哈希。Hash 作用如下图所示:
Hash 函数能够通过选取适当的函数，能够在工夫和空间上获得较好均衡。
解决 Hash 的两种形式：拉链法和线性探测法
1.3 键值关系的实现
interface Entry<K,V>在 HashMap 中基于链表的实现
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;
}用树的形式实现：
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;
TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);
}1.4 Map 约定的 API
1.4.1 Map 中约定的根底 API
根底的增删改查：
int size(); // 返回大小
boolean isEmpty(); // 是否为空
boolean containsKey(Object key); // 是否蕴含某个键
boolean containsValue(Object value); // 是否蕴含某个值
V get(Object key); // 获取某个键对应的值
V put(K key, V value); // 存入的数据
V remove(Object key); // 移除某个键
void putAll(Map<? extends K, ? extends V> m); // 将将另一个集插入该汇合中
void clear(); // 革除
Set<K> keySet(); // 获取 Map 的所有的键返回为 Set 汇合
Collection<V> values(); // 将所有的值返回为 Collection 汇合
Set<Map.Entry<K, V>> entrySet(); // 将键值对映射为 Map.Entry，外部类 Entry 实现了映射关系的实现。并且返回所有键值映射为 Set 汇合。boolean equals(Object o);
int hashCode(); // 返回 Hash 值
default boolean replace(K key, V oldValue, V newValue); // 代替操作
default V replace(K key, V value);1.4.2 Map 约定的较为高级的 API
default V getOrDefault(Object key, V defaultValue); // 当获取失败时，用 defaultValue 代替。default void forEach(BiConsumer<? super K, ? super V> action) // 可用 lambda 表达式进行更快捷的遍历
default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function);
default V putIfAbsent(K key, V value);
default V computeIfAbsent(K key,
Function<? super K, ? extends V> mappingFunction);
default V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction);
default V compute(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction)
default V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction)1.4.3 Map 高级 API 的应用
- getOrDefault() 当这个通过 key 获取值，对应的 key 或者值不存在时返回默认值，防止在应用过程中 null 呈现，防止程序异样。
- ForEach() 传入 BiConsumer 函数式接口，表白的含意其实和 Consumer 一样，都 accept 领有办法，只是 BiConsumer 多了一个 andThen() 办法，接管一个 BiConsumer 接口，先执行本接口的，再执行传入的参数的 accept 办法。
Map<String, String> map = new HashMap<>();
map.put("a", "1");
map.put("b", "2");
map.put("c", "3");
map.put("d", "4");
map.forEach((k, v) -> {System.out.println(k+"-"+v);
});
}更多的函数用法：
https://www.cnblogs.com/king0…
1.5 从 Map 走向 HashMap
HashMap 是 Map 的一个实现类，也是 Map 最罕用的实现类。
1.5.1 HashMap 的继承关系
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable在 HashMap 的实现过程中，解决 Hash 抵触的办法是拉链法。因而从原理来说 HashMap 的实现就是 数组 + 链表（数组保留链表的入口）。当链表过长，为了优化查问速率，HashMap 将链表转化为红黑树（数组保留树的根节点），使得查问速率为 log(n)，而不是链表的 O(n)。
二、HashMap
/*
* @author Doug Lea
* @author Josh Bloch
* @author Arthur van Hoff
* @author Neal Gafter
* @see Object#hashCode()
* @see Collection
* @see Map
* @see TreeMap
* @see Hashtable
* @since 1.2
*/首先 HashMap 由 Doug Lea 和 Josh Bloch 两位巨匠的参加。同时 Java 的 Collections 汇合体系，并发框架 Doug Lea 也做出了不少奉献。
2.1 基本原理
对于一个插入操作，首先将键通过 Hash 函数转化为数组的下标。若该数组为空，间接创立节点放入数组中。若该数组下标存在节点, 即 Hash 抵触，应用拉链法，生成一个链表插入。
援用图片来自 https://blog.csdn.net/woshima…
如果存在 Hash 抵触，应用拉链法插入，咱们能够在这个链表的头部插入，也能够在链表的尾部插入，所以在 JDK 1.7 中应用了头部插入的办法，JDK 1.8 后续的版本中应用尾插法。
JDK 1.7 应用头部插入的可能根据是最近插入的数据是最罕用的，然而头插法带来的问题之一，在多线程会链表的复制会呈现死循环。所以 JDK 1.8 之后采纳的尾部插入的办法。
在 HashMap 中，后面说到的 数组 + 链表 的数组的定义
transient Node<K,V>[] table;链表的定义：
static class Node<K,V> implements Map.Entry<K,V>2.1.2 提供的构造函数
public HashMap() { // 空参
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) { // 带有初始大小的，个别状况下，咱们须要布局好 HashMap 应用的大小，因为对于一次扩容操作，代价是十分的大的
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor); // 能够自定义负载因子 public HashMap(int initialCapacity, float loadFactor); // 能够自定义负载因子三个构造函数，都没有齐全的初始化 HashMap，当咱们第一次插入数据时，才进行堆内存的调配，这样进步了代码的响应速度。
2.2 HashMap 中的 Hash 函数定义
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // 将 h 高 16 位和低 16 位 进行异或操作。}
// 采纳 异或的起因：两个进行位运算，在与或异或中只有异或到的 0 和 1 的概率是雷同的，而 & 和 | 都会使得后果偏差 0 或者 1。这里能够看到，Map 的键能够为 null，且 hash 是一个特定的值 0。
Hash 的目标是获取数组 table 的下标。Hash 函数的指标就是将数据平均的散布在 table 中。
让咱们先看看如何通过 hash 值得到对应的数组下标。第一种办法：hash%table.length()。然而除法操作在 CPU 中执行比加法、减法、乘法慢的多，效率低下。第二种办法 table[(table.length – 1) & hash] 一个与操作一个减法，依然比除法快。这里的约束条件为 table.length = 2^N。
table.length =16
table.length -1 = 15 1111 1111
// 任何一个数与之与操作，获取到这个数的低 8 位，其余位为 0下面的例子能够让咱们获取到对应的下标, 而 (h = key.hashCode()) ^ (h >>> 16) 让高 16 也参加运算，让数据充分利用，个别状况下 table 的索引不会超过 216，所以高位的信息咱们就间接摈弃了，^ (h >>> 16) 让咱们在数据量较少的状况下，也能够应用高位的信息。如果 table 的索引超过 216，hashCode() 的高 16 为 和 16 个 0 做异或失去的 Hash 也是偏心的。
2.3 HashMap 的插入操作
下面咱们曾经晓得如果通过 Hash 获取到 对应的 table 下标，因而咱们将对应的节点退出到链表就实现了一个 Map 的映射，确实 JDK1.7 中的 HashMap 实现就是这样。让咱们看一看 JDK 为实现事实的 put 操作。
定位到 put() 操作。
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}能够看到 put 操作交给了 putVal 来进行通用的实现。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict);
//onlyIfAbsent 如果以后地位已存在一个值，是否替换，false 是替换，true 是不替换
evict // 钩子函数的参数，LinkedHashMap 中应用到，HashMap 中无意义。2.3.1 putVal 的流程剖析
其实 putVal() 流程的函数十分的明了。这里挑了几个关键步骤来疏导。
是否第一次插入，true 调用 resizer() 进行调整，其实此时 resizer() 是进行残缺的初始化，之后间接赋值给对应索引的地位。
if ((tab = table) == null || (n = tab.length) == 0) // 第一次 put 操作，tab 没有分配内存，通过 redize() 办法分配内存，开始工作。n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);如果链表曾经转化为树，则应用树的插入。
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);用遍历的形式遍历每个 Node，如果遇到键雷同，或者达到尾节点的 next 指针将数据插入，记录节点地位退出循环。若插入后链表长度为 8 则调用 treeifyBin() 是否进行树的转化。
for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}对键反复的操作：更新后返回旧值，同时还取决于 onlyIfAbsent，一般操作中个别为 true，能够疏忽。
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 钩子函数，进行后续其余操作，HashMap 中为空，无任何操作。return oldValue;
}~
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;后续的数据保护。
2.3.2 modCount 的含意
fail-fast 机制是 java 汇合 (Collection) 中的一种谬误机制。当多个线程对同一个汇合的内容进行操作时，就可能会产生 fail-fast 事件。例如：当某一个线程 A 通过 iterator 去遍历某汇合的过程中，若该汇合的内容被其余线程所扭转了；那么线程 A 拜访汇合时，就会抛出 ConcurrentModificationException 异样，产生 fail-fast 事件。一种多线程谬误查看的形式，缩小异样的产生。
个别状况下，多线程环境 咱们应用 ConcurrentHashMap 来代替 HashMap。
2.4 resize() 函数
HashMap 扩容的特点：默认的 table 表的大小事 16，threshold 为 12。负载因子 loadFactor .75，这些都是能够结构是更改。当前扩容都是 2 倍的形式减少。
至于为何是 0.75 代码的正文中也写了起因，对 Hash 函数构建了泊松散布模型，进行了剖析。
2.4.1 HashMap 预约义的一些参数
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 HashMap 的默认大小。为什么应用 1 <<4
static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 加载因子，扩容应用
static final int UNTREEIFY_THRESHOLD = 6;// 树结构转化为链表的阈值
static final int TREEIFY_THRESHOLD = 8; // 链表转化为树结构的阈值
static final int MIN_TREEIFY_CAPACITY = 64; // 链表转变成树之前，还会有一次判断，只有数组长度大于 64 才会产生转换。这是为了防止在哈希表建设初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。// 定义的无关变量
int threshold; // threshold 示意当 HashMap 的 size 大于 threshold 时会执行 resize 操作这些变量都是和 HashMap 的扩容机制无关，将会在下文中用到。
2.4.2 resize() 办法解析
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0; // 定义了 旧表长度、旧表阈值、新表长度、新表阈值 if (oldCap > 0) { // 插入过数据，参数不是初始化的
if (oldCap >= MAXIMUM_CAPACITY) { // 如果旧的表长度大于 1 << 30;
threshold = Integer.MAX_VALUE; // threshold 设置 Integer 的最大值。也就是说咱们能够插入 Integer.MAX_VALUE 个数据
return oldTab; // 间接返回旧表的长度，因为表的下标索引无奈扩充了。}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && //
oldCap >= DEFAULT_INITIAL_CAPACITY) // 新表的长度为旧表的长度的 2 倍。newThr = oldThr << 1; // double threshold 新表的阈值为同时为旧表的两倍
}
else if (oldThr > 0) // public HashMap(int initialCapacity, float loadFactor) 中的 this.threshold = tableSizeFor(initialCapacity); 给正确的地位
newCap = oldThr;
else { // zero initial threshold signifies using defaults，如果调用了其余两个构造函数，则上面代码初始化。因为他们都没有对其 threshold 设置，默认为 0，newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {// 修改 threshold，例如下面的 else if (oldThr > 0) 局部就没有设置。float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})当一些参数设置正确后便开始扩容。
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];当扩容结束之后，天然就是将原表中的数据搬到新的表中。上面代码实现了该工作。
if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {....}
}如何正确的，疾速的扩容调整每个键值节点对应的下标？第一种办法：遍历节点再应用 put() 退出一遍，这种办法实现，然而效率低下。第二种，咱们手动组装好链表，退出到相应的地位。显然第二种比第一种高效，因为第一种 put() 还存在其余不属于这种状况的判断，例如反复键的判断等。
所以 JDK 1.8 也应用了第二种办法。咱们能够持续应用 e.hash & (newCap - 1) 找到对应的下标地位, 对于旧的链表，执行e.hash & (newCap - 1) 操作，只能产生两个不同的索引。一个放弃原来的索引不变，另一个变为 原来索引 + oldCap(因为 newCap 的退出产生导致索引的位数多了 1 位，即就是最右边的一个，且该位此时后果为 1，所以相当于 原来索引 + oldCap)。所以能够应用 if ((e.hash & oldCap) == 0) 来确定出索引是否来变动。
因而这样咱们就能够将原来的链表拆分为两个新的链表，而后退出到对应的地位。为了高效，咱们手动的组装好链表再存储到相应的下标地位上。
oldCap = 16
newCap = 32
hash : 0001 1011
oldCap-1 : 0000 1111
后果为 : 0000 1011 对应的索引的 11
-------------------------
e.hash & oldCap 则定于 1, 则须要进行调整索引
oldCap = 16
hash : 0001 1011
newCap-1 : 0001 1111
后果为 : 0001 1011
相当于 1011 + 1 0000 原来索引 + newCapfor (int j = 0; j < oldCap; ++j) // 解决每个链表非凡条件解决
Node<K,V> e;
if ((e = oldTab[j]) != null) {oldTab[j] = null;
if (e.next == null) // 该 链表只有一个节点，那么间接复制到对应的地位，下标由 e.hash & (newCap - 1) 确定
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) // 若是 树，该给树的处理程序
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);一般状况解决：
else { // preserve order
Node<K,V> loHead = null, loTail = null; // 构建原来索引地位 的链表，须要的指针
Node<K,V> hiHead = null, hiTail = null; // 构建 原来索引 + oldCap 地位 的链表须要的指针
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null); // 将原来的链表划分两个链表
if (loTail != null) { // 将链表写入到相应的地位
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}到此 resize() 办法的逻辑实现了。总的来说 resizer() 实现了 HashMap 残缺的初始化，分配内存和后续的扩容保护工作。
2.5 remove 解析
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}将 remove 删除工作交给外部函数 removeNode() 来实现。
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) { // 获取索引，Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) // 判断索引处的值是不是想要的后果
node = p;
else if ((e = p.next) != null) { // 交给树的查找算法
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do { // 遍历查找
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {if (node instanceof TreeNode) // 树的删除
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p) // 修复链表，链表的删除操作
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}三、HashMap 从链表到红黑树的转变
如果链表的长度（抵触的节点数）曾经达到 8 个，此时会调用 treeifyBin()，treeifyBin() 首先判断以后 hashMap 的 table 的长度，如果有余 64，只进行 resize，扩容 table，如果达到 64，那么将抵触的存储构造为红黑树。在源码还有这样的一个字段。
static final int UNTREEIFY_THRESHOLD = 6;
// 这样表明了从红黑树转化为链表的阈值为 6，为何同样不是 8 那？// 如果插入和删除都在 8 左近，将多二者互相转化将节约大量的工夫，对其性能影响。// 如果是的二者转化的操作不均衡，偏差一方，则能够防止此类影响。3.1 红黑树的数据结构
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; // 删除后须要勾销链接，指向前一个节点（原链表中的前一个节点）boolean red;
}因为 继承了 LinkedHashMap.Entry<K,V>，所以存储的数据还是在 Entry 中：
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;
}
}3.2 承前启后的 treeifyBin()
treeifyBin() 决定了一个链表何时转化为一个红黑树。treeifyBin() 有两种格局：
final void treeifyBin(Node<K,V>[] tab, int hash);
final void treeify(Node<K,V>[] tab); final void treeifyBin(Node<K,V>[] tab, int hash) { // 简略的 Node 批改为 TreeNode，同时保护了 prev 属性。int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab); // 真正生成红黑树的
}
} TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {return new TreeNode<>(p.hash, p.key, p.value, next);
} // 实现 Node 链表节点到 TreeNode 节点的转化。上面函数真正实现了链表的红黑树的转变。首先构建一个规范查问二叉树，而后在规范查问二叉树而后调整为一个红黑树。而 balanceInsertion() 实现了调整。
/**
* Forms tree of the nodes linked from this node.
*/
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) { // 第一次转化过程，将链表的头节点作为根节点。x.parent = null;
x.red = false; // 红黑树的定义 根节点必须为彩色
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h) //// 通过 Hash 的大小来确定插入程序
dir = -1; // dir 大小程序的标识
else if (ph < h)
dir = 1;
else if ((kc == null && // 当 两个 Hash 的值雷同，进行非凡的办法，确定大小。(kc = comparableClassFor(k)) == null) || // Returns x's Class if it is of the form"class C implements Comparable ", else null. 如果 key 类的 源码书写格局为 C implement Comparable<C> 那么返回该类类型 C, 如果间接实现也不行。如果是 String 类型，间接返回 String.class
(dir = compareComparables(kc, k, pk)) == 0) // ((Comparable)k).compareTo(pk)); 强制转换后进行比照，若 dir == 0, 则 tieBreakOrder()，持续仲裁
dir = tieBreakOrder(k, pk); // 首先通过二者的类类型进行比拟，如果相等的话，应用 (System.identityHashCode(a) <= System.identityHashCode(b) 应用原始的 hashcode，不是重写的在比照。TreeNode<K,V> xp = p; // 遍历的，上一个节点
if ((p = (dir <= 0) ? p.left : p.right) == null) { // 通过 dir，将 p 向下查找，直到 p 为 null，找到一个插入机会
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x); // 进行二叉树的调整
break;
}
}
}
}
moveRootToFront(tab, root);
}3.3 将一个二叉树转化为红黑树的操作 -balanceInsertion()
当红黑树中新增节点的时候须要调用 balanceInsertion 办法来保障红黑树的个性。
如果想要理解红黑树的插入过程那么必须对红黑树的性质有一个较为清晰的理解。
红黑树的性质：
- 每个结点或是红色的，或是彩色的
- 根节点是彩色的
- 每个叶结点（NIL）是彩色的
- 如果一个节点是红色的，则它的两个儿子都是彩色的。
- 对于每个结点，从该结点到其叶子结点形成的所有门路上的黑结点个数雷同。
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
x.red = true; // 插入的子节点必须为 red
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { //// x 以后解决节点 xp 父节点 xpp 祖父节点 xppl 祖父左节点 xppr 祖父右节点
if ((xp = x.parent) == null) { // 如果 以后解决节点为根节点，满足红黑树的性质，完结循环
x.red = false;
return x;
}
else if (!xp.red || (xpp = xp.parent) == null)
return root;
if (xp == (xppl = xpp.left)) {if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {if (x == xp.right) {root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
else {if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {if (x == xp.left) {root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}TreeNode 红黑树总结
TreeNode 残缺的实现了一套红黑树的增删改查的规定。实现参考了《算法导论》
/* ------------------------------------------------------------ */
// Red-black tree methods, all adapted from CLR这里举荐一个红黑树动画演示网站 https://rbtree.phpisfuture.com/
红黑树是一个不严格的均衡二叉查找树，高度近似 log(N)。
四、HashMap 的扩大
Map 中 key 有一个性质，就是 key 不能反复，而 Java Set 的含意：汇合中不能有反复的元素。HashMap 的实现曾经足够的优良。那么咱们是否能够用 key 的性质来实现 Set？确实 JDK 中的 HashSet 就是这样做的。
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();}PRESENT 就是存进 Map 中的 value，而 key 正是 Set 语义的实现。而且能够判断出 HashSet 中是容许存入 Null 值的。
近期热文举荐：
1.1,000+ 道 Java 面试题及答案整顿(2022 最新版)
2. 劲爆！Java 协程要来了。。。
3.Spring Boot 2.x 教程，太全了！
4.20w 程序员红包封面，快快支付。。。
5.《Java 开发手册（嵩山版）》最新公布，速速下载！
感觉不错，别忘了顺手点赞 + 转发哦！
