环境和版本
- Mac M1
- IDEA 2021
-
简介
HashMap，开发中非常常用的Key-Value数据结构。
- 其在JDK7和JDK8之后，底层的实现有了很大的区别，我们先讨论数据结构的变化，在说一下API的使用和实现。
- HashMap实现了Map接口，即允许放入key为null的元素，也允许插入value为null的元素；除该类未实现同步外，其余跟Hashtable大致相同；跟TreeMap不同，该容器不保证元素顺序，根据需要该容器可能会对元素重新哈希，元素的顺序也会被重新打散，因此不同时间迭代同一个HashMap的顺序可能会不同。
- 根据对冲突的处理方式不同，哈希表有两种实现方式，一种开放地址方式(Open addressing)，另一种是冲突链表方式(Separate chaining with linked lists)(也可称为拉链法)
-
理解哈希
哈希：Hash，也称为散列，基本原理就是把任意长度输入，转化为固定长度输出 这个映射的规则就是Hash算法，而原始数据映射的二进制串就是Hash值
- 哈希的特点：
- 从Hash值不可以反向推导出原始数据
- 输入数据的微小变化会得到完全不同的Hash值相同的数据一定可以得到相同的值
- 哈希算法的执行效率要高效，长的文本也能快速计算Hash值
- Hash算法的冲突概率要小
- 由于Hash原理就是将输入空间映射成Hash空间，而Hash空间远远小于输入空间，根据抽屉原理，一定存在不同输出有相同的映射
抽屉原理 桌子上有10个苹果，将其放在9个抽屉里面，那必有一个抽屉不少于2个苹果
Java7 HashMap存储结构
从上图容易看出，如果选择合适的哈希函数，put()和get()方法可以在常数时间内完成，但是对HashMap进行迭代的时候，需要遍历整个table以及后面的冲突链表。因此对于迭代比较频繁的场景，不宜将HashMap的初始大小设的过大。
- 有两个参数可以影响HashMap的性能: 初始容量(inital capacity)和负载系数(load factor)。初始容量指定了初始table的大小，负载系数用来指定自动扩容的临界值。当entry的数量超过capacity*load_factor时，容器将自动扩容并重新哈希。对于插入元素较多的场景，将初始容量设大可以减少重新哈希的次数。
将对象放入到HashMap或HashSet中时，有两个方法需要特别关心: hashCode()和equals()。hashCode()方法决定了对象会被放到哪个bucket里，当多个对象的哈希值冲突时，equals()方法决定了这些对象是否是“同一个对象”。所以，如果要将自定义的对象放入到HashMap或HashSet中，需要@OverridehashCode()和equals()方法。
get方法
get(Object key)方法根据指定的key值返回对应的value，该方法调用了getEntry(Object key)得到相应的entry，然后返回entry.getValue()。因此getEntry()是算法的核心。
- 算法思想是首先通过hash()函数得到对应bucket的下标，然后依次遍历冲突链表，通过key.equals(k)方法来判断是否是要找的那个entry
- 上图中hash(k)&(table.length-1)等价于hash(k)%table.length，原因是HashMap要求table.length必须是2的指数，因此table.length-1就是二进制低位全是1，跟hash(k)相与会将哈希值的高位全抹掉，剩下的就是余数了。
```java
// addEntry()
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
} // 在冲突链表头部插入新的entry Entry// 自动扩容，并重新哈希resize(2 * table.length);hash = (null != key) ? hash(key) : 0;bucketIndex = hash & (table.length-1);//hash%table.length
<a name="NZ0z6"></a># remove方法- remove(Object key)的作用是删除key值对应的entry，该方法的具体逻辑是在removeEntryForKey(Object key)里实现的。removeEntryForKey()方法会首先找到key值对应的entry，然后删除该entry(修改链表的相应引用)。查找过程跟getEntry()过程类似。```java// removeEntryForKey()final Entry<K,V> removeEntryForKey(Object key) {// ......int hash = (key == null) ? 0 : hash(key);// hash&(table.length-1)int i = indexFor(hash, table.length);// 得到冲突链表Entry<K,V> prev = table[i];Entry<K,V> e = prev;// 遍历冲突链表while (e != null) {Entry<K,V> next = e.next;Object k;// 找到要删除的entryif (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) {modCount++; size--;// 删除的是冲突链表的第一个entryif (prev == e) table[i] = next;else prev.next = next;return e;}prev = e; e = next;}return e;}
Java8 HashMap存储结构
- Java8对HashMap做了一些修改，最大的不同就是利用了红黑树，所以其由 数组+链表+红黑树 组成
- 很具上面对HashMap的介绍，我们知道，在查找的时候，根据hash值来快速确认数组的具体下标。但是之后，需要到一个链表去找某个元素，时间复杂度为O(n)
- 为了降低这部分的开销，在Java8中，当链表中的元素达到了8之后，将会把链表转换为红黑树，在这些位置进行查找的时候，时间复杂度为O(logN)
- 在链表长度大于 8 并且 表的长度大于 64 的时候会转化红黑树，如果表的长度小于64，只会扩容。只是尝试树化。
- Java8 HashMap扩容的条件：当hashmap中的元素个数(size)超过数组大小*loadFactor时，就会扩容。
- Java8 HashMap扩容的条件有很多，我们先讲一个，然后再源码中体会。
上面的只是示意图，在手撕讲Java8 HashMap源码之前，我们先来手写一下红黑树
手写红黑树
概述
数据结构的基石，我认为只有2个：数组和链表。所有的数据结构都可以通过二者演变出来
红黑树原理讲解
├─ 红黑树的性质├─ 红黑树有几种变化策略？(为满足红黑树性质)│ ├─ 改变颜色│ ├─ 左旋│ ├─ 右旋├─ 红黑树的查找├─ 红黑树的插入│ ├─ 情景1：红黑树为空树│ ├─ 情景2：插入节点的Key已经存在│ ├─ 情景3：插入节点的父节点为黑色│ ├─ 情景4：插入节点的父节点为红色│ │ ├─ 情景4.1：叔叔节点存在，并且为红色(父 - 叔 双红)│ │ ├─ 情景4.2：叔叔节点不存在，或者为黑色，父节点为爷爷节点的左子树│ │ │ ├─ 情景4.2.1：插入节点为其父节点的左子节点(LL情况)│ │ │ ├─ 情景4.2.2：插入节点为其父节点的右子节点(LR情况)│ │ ├─ 情景4.3：叔叔节点不存在，或者为黑色，父节点为爷爷节点的右子树│ │ │ ├─ 情景4.3.1：插入节点为其父节点的右子节点(RR情况)│ │ │ ├─ 情景4.3.2：插入节点为其父节点的左子节点(RL情况)├─ 红黑树的插入案例分析
红黑树的性质
性质1：每个节点要么是红色，要么是黑色。
- 性质2：根节点是黑色
- 性质3：每个叶子节点是黑色
- 性质4：每个红色节点的子节点一定是黑色
- 性质5：任意一个节点到每个子节点的路径都包含数量相同的黑节点，俗称黑高
- 从性质5可以推出：如果一个节点存在黑子节点，那么该节点肯定有两个子节点
- 红黑树不是一个完美平衡二叉树，从上图可以看到，根节点P的左子树比右子树高
但是左子树和右子树的层数是相等的，也就是任意一个节点到每个叶子节点的路径都包含相同数量的黑节点，所以称这种红黑树的平衡为 黑色完美平衡
红黑树有几种变化策略
前面讲到红黑树可以自平衡，它靠的是什么？三总操作：左旋，右旋，变色
- 变色：节点的颜色由红变黑或由黑变红
- 左旋：以某个节点作为支点(旋转节点)，其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，左子节点保持不变
- 右旋：以某个节点作为支点(旋转节点)，其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持不变
- 左旋展示
- 右旋展示
- 红黑树查找
- 红黑树的插入
- 插入操作：查找插入的位置；插入后自平衡
- 注意：插入节点，必须为红色。理由很简单，红色在父节点(如果存在)为黑色节点的时候，红黑树的黑色平衡没有被破坏，不需要做自平衡操作；如果父节点为红色节点，这个时候就要重新平衡。但是如果插入的是黑色节点，那么插入位置的子树节点总是多1，必须做平衡。
- 在开始每个情景讲解前，先约定一下名称：父亲节点-叔叔节点-爷爷节点
情景1：红黑树为空树
- 最简单的一种场景，直接把插入节点作为根节点即可
注意：根据红黑树的性质2：根节点是黑色，还需要把插入节点设置为黑色
情景2：插入节点的key已经存在
-
情景3：插入节点的父节点为黑节点
由于插入的节点是黑色的，当插入的节点为黑色的时候，并不会影响红黑树的平衡，直接插入即可，无需做自平衡
情景4：插入的节点的父节点为红色
- 再一次回想红黑树的性质2：根节点是黑色。如果插入节点的父节点是红节点，那么该父节点则不可能是根节点，所以插入节点总是存在祖父节点，这一点很关键，因为后续的旋转操作肯定需要祖父节点的参与。
情景4.1 叔叔节点存在且为红节点
- 根据红黑树的性质4可知：红色节点不能相连 => 祖父节点肯定为黑节点
- 因为不能存在两个相连的红节点，那么此时该插入了子树的红黑层级的情况是：黑红红。显然最简单的处理方式是：红黑红。
- 处理：
- 将P和U改为黑色
- 将PP改为红色
- 将PP设置为当前节点，进行后续处理
可以看到，我们把PP节点变为红色了，如果PP节点是黑色，则无需处理，但是如果PP的父节点是红色，就违反红黑树的性质了，所以需要将PP设置为当前节点，继续做插入操作自平衡处理，直到平衡为止
情景4.2 叔叔节点不存在或者为黑节点，并且插入节点的父亲节点是祖父节点的左子节点
注意：单纯从插入来看，叔叔节点非红即空(NIL)，否则的话破坏了红黑树性质5，此路径会比其他路径多了一个黑色节点
4.2.1 新插入节点，为其父节点的左子节点(LL红色情况)
- 处理
- 变颜色：将P设置为黑色，将PP设置为红色
- 对PP节点进行右旋
4.2.2 新插入节点，为其父节点的右子节点（LR红色情况）
- 处理
- 对P进行左旋
- 将P设置为当前节点，得到LL的红色情况
- 按照LL红色情况处理
- 变颜色，将P设置为黑色，将PP设置为红色
- 右旋PP节点
情景4.3 叔叔节点不存在，或者为黑色，父节点为爷爷节点的右子树
- 其实就是4.2的反方向
4.3.1 插入节点为其父节点的右子节点(RR情况)
- 处理
- 变颜色，将P设置为黑色，将PP设置为红色
- 对PP节点进行左旋
4.3.2 插入节点为其父节点的左子节点(RL情况)
- 处理
- 对P进行右旋
- 将P设置为当前节点，得到RR的情况
- 按照RR进行处理
红黑树插入案例分析
手写红黑树
- 创建RBTree，定义颜色
- 创建RBNode
- 辅助方法定义：parentOf(node)、isRed(node)、isBlack(node)、setRed(node)、setBlack(node)、inOrderPrint()
- 左旋方法定义：leftRotate(node)
- 右旋方法定义：rightRotate(node)
- 公开插入接口方法定义：insert(K key,V value)
- 内部插入接口方法定义：insert(RBNode node)
- 修正插入导致红黑树失衡的方法定义：insertFlxUp(RBNode node)
- 测试红黑树的正确性
代码实现如下
```java // RBTree.java package cn.icanci.tree;
/**
- 1 创建RBTree，定义颜色
- 2 创建RBNode
- 3 辅助方法定义：parentOf(node)、isRed(node)、isBlack(node)、setRed(node)、setBlack(node)、inOrderPrint()
- 4 左旋方法定义：leftRotate(node)
- 5 右旋方法定义：rightRotate(node)
- 6 公开插入接口方法定义：insert(K key,V value)
- 7 内部插入接口方法定义：insert(RBNode node)
- 8 修正插入导致红黑树失衡的方法定义：insertFlxUp(RBNode node)
- 9 测试红黑树的正确性 */
/**
- 创建 创建RBTree，定义颜色 *
- @param
Key @param
Value / public class RBTree , V> { /* - RED 红色节点 / private static final boolean RED = true; /*
BLACK 黑色节点 */ private static final boolean BLACK = false;
/**
树根的引用 */ private RBNode root;
public RBNode getRoot() { return root; }
public void setRoot(RBNode root) { this.root = root; }
/**
- 获取当前节点的父节点 *
- @param node 当前节点
@return 返回当前节点的父节点，没有就返回null */ private RBNode parentOf(RBNode node) { if (node != null) {
return node.parent;
} return null; }
/**
- 节点是否为红色 *
- @param node 当前节点
@return 返回当前节点的颜色，节点为null就返回false */ private boolean isRed(RBNode node) { if (node != null) {
return node.color == RED;
} return false; }
/**
- 节点是否为黑色 *
- @param node 当前节点
@return 返回当前节点的颜色，节点为null就返回false */ private boolean isBlack(RBNode node) { if (node != null) {
return node.color == BLACK;} return false; }
/**
- 设置节点为红色 *
- @param node 当前的节点
*/
private void setRed(RBNode node) {
if (node != null) {
} }node.color = RED;
/**
* 设置节点为黑色
*
* @param node 当前的节点
*/
private void setBlack(RBNode node) {
if (node != null) {
node.color = BLACK;
}
}
/**
* 红黑树的中序打印
*/
public void inOrderPrint() {
inOrderPrint(this.root);
}
/**
* 红黑树的中序打印
*
* @param node 根节点
*/
private void inOrderPrint(RBNode node) {
if (node != null) {
inOrderPrint(node.left);
System.out.println("Key:" + node.key + " Value:" + node.value);
inOrderPrint(node.right);
}
}
/**
* 左旋方法
* 左旋示意图：左旋x节点
* p p
* | |
* x y
* / \ ----> / \
* lx y x ry
* / \ / \
* ly ry lx ly
*/
/**
* 左旋做了几件事？
* 1.并将x的右子节点指向y的左子节点(ly) 将y的左子节点的父节点更新为x
* 2.当x的父节点不为空的时候，更新y的父节点为x的父节点，并将x的父节点指定子树(当前x的子树位置)指定为y
* 3.将x的父节点更新为y，将y的左子节点指向x
*/
private void leftRotate(RBNode x) {
// 先拿到当前节点的右子节点
RBNode y = x.right;
// 将x的右子节点指向y的左子节点(ly)
x.right = y.left;
if (y.left != null) {
// 将y的左子节点的父节点更新为x
y.left.parent = x;
}
// 当x的父节点不为空的时候，更新y的父节点为x的父节点
// 并将x的父节点指定子树(当前x的子树位置)指定为y
if (x.parent != null) {
y.parent = x.parent;
if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
} else {
// 说明x为根节点
this.root = y;
this.root.parent = null;
}
// 将x的父节点更新为y，将y的左子节点指向x
x.parent = y;
y.left = x;
}
/**
* 右旋方法
* 右旋示意图：右旋y节点
*
* p p
* | |
* y x
* / \ ----> / \
* x ry lx y
* / \ / \
*lx ly ly ry
*/
/**
* 1.将y的左子节点指向x的有子节点，并且更新x的有子节点的父节点为y
* 2.当y的父节点不为空的时候，更新x的父节点为y的父节点，更新y的父节点的指定子节点（y当前的位置）为x
* 3.更新y的父节点为x。更新x的右子节点为y
*/
private void rightRotate(RBNode y) {
RBNode x = y.left;
// 将y的左子节点指向x的有子节点，并且更新x的有子节点的父节点为y
y.left = x.right;
if (x.right != null) {
x.right.parent = y;
}
if (y.parent != null) {
x.parent = y.parent;
if (y == y.parent.left) {
y.parent.left = x;
} else {
y.parent.right = x;
}
} else {
this.root = x;
this.root.parent = null;
}
// 更新y的父节点为x。更新x的右子节点为y
y.parent = x;
x.right = y;
}
/**
* 公开的插入方法
*
* @param key
* @param value
*/
public void insert(K key, V value) {
RBNode node = new RBNode();
node.setKey(key);
node.setValue(value);
// 新节点一定是红色
node.setColor(RED);
this.insert(node);
}
/**
* 私有的插入方法
*
* @param node 需要插入的节点
*/
private void insert(RBNode node) {
//第一步：查找当前的node的父节点
RBNode parent = null;
RBNode x = this.root;
while (x != null) {
parent = x;
// cmp > 0 说明node.key 大于 x.key 需要到x的右子树去寻找
// cmp == 0 说明node.key 等于 x.key 说明需要替换操作
// cmp < 0 说明node.key 小于 x.key 说明需要到x的左子树去寻找
int cmp = node.key.compareTo(x.key);
if (cmp > 0) {
x = x.right;
} else if (cmp < 0) {
x = x.left;
} else {
x.value = node.value;
return;
}
}
node.parent = parent;
if (parent != null) {
// 判断node与parent的key谁大
int cmp = node.key.compareTo(parent.key);
// 当前node的key比parent的key大，那么就要把node放入parent的右子节点
if (cmp > 0) {
parent.right = node;
} else {
// 当前node的key比parent的key小，那么就要把node放入parent的左子节点
parent.left = node;
}
} else {
this.root = node;
}
// 需要调用修复红黑树平衡的方法
this.insertFlxUp(node);
}
/**
* 插入后修复红黑树平衡的方法
* |---情景1：红黑树为空树，将根节点染色为黑色
* |---情景2：插入节点的key已经存在，不需要处理
* |---情景3：插入节点的父节点为黑色，因为你所插入的路径，黑色节点，没有变化，红黑树依旧平衡，不需要处理
* 情景4 需要咱们去处理
* |---情景4：插入节点的父节点为红色
* |---情景4.1：叔叔节点存在，并且为红色（父-叔 双红），将父亲节点和叔叔节点染色为黑色
* 并且再以爷爷节点为当前节点，进行下一轮处理
* |---情景4.2：叔叔节点不存在，或者为黑色，父节点为爷爷节点的左子树
* |---情景4.2.1：插入节点为其父节点的左子节点（LL情况）
* 将父亲染色为黑色，将爷爷染色为红色，
* 然后以爷爷点右旋，就完成了
* |---情景4.2.2：插入节点为其父节点的右子节点（LR情况）
* 以父亲节点进行一次左旋，得到LL（4.2.1） 的场景
* 然后指定父亲节点为当前节点，进行下一个处理
* |---情景4.3：叔叔节点不存在，或者为黑色，父节点为爷爷节点的右子树
* |---情景4.3.1：插入节点为其父节点的右子节点（RR情况）
* 父亲染色为黑色，将爷爷染色为红色
* 然后以爷爷节点左旋，就完成了
* |---情景4.3.2：插入节点为其父节点的左子节点（RL情况）
* 以父亲节点进行一次右旋，得到RR双红（4.3.1）的场景
* 然后指定父亲节点进行下一论处理
*/
/**
* 修复红黑树的方法
*
* @param node
*/
private void insertFlxUp(RBNode node) {
this.root.setColor(BLACK);
RBNode parent = parentOf(node);
RBNode gParent = parentOf(parent);
// 情景4：插入节点的父节点为红色
if (parent != null && isRed(parent)) {
// 如果父节点是红色，那么一定存在爷爷节点，因为根节点不可能是红色
RBNode uncle = null;
// 父节点为爷爷节点的右左子树
if (parent == gParent.left) {
uncle = gParent.right;
// 情景4.1：叔叔节点存在，并且为红色（父-叔 双红）
if (uncle != null && isRed(uncle)) {
// 将父亲节点和叔叔节点染色为黑色
setBlack(parent);
setBlack(uncle);
setRed(gParent);
// 并且再以爷爷节点为当前节点，进行下一轮处理
insertFlxUp(gParent);
return;
}
// 情景4.2：叔叔节点不存在，或者为黑色，父节点为爷爷节点的左子树
if (uncle == null || isBlack(uncle)) {
// 情景4.2.1：插入节点为其父节点的左子节点（LL情况）
// 将父亲染色为黑色，将爷爷染色为红色，
// 然后以爷爷点右旋，就完成了
if (node == parent.left) {
setBlack(parent);
setBlack(gParent);
rightRotate(gParent);
return;
}
// 情景4.2.2：插入节点为其父节点的右子节点（LR情况）
// 以父亲节点进行一次左旋，得到LL（4.2.1） 的场景
// 然后指定父亲节点为当前节点，进行下一个处理
if (node == parent.right) {
leftRotate(parent);
insertFlxUp(parent);
return;
}
}
} else {
// 父节点为爷爷节点的右子树
uncle = gParent.left;
// 情景4.1：叔叔节点存在，并且为红色（父-叔 双红）
if (uncle != null && isRed(uncle)) {
// 将父亲节点和叔叔节点染色为黑色
setBlack(parent);
setBlack(uncle);
setRed(gParent);
// 并且再以爷爷节点为当前节点，进行下一轮处理
insertFlxUp(gParent);
return;
}
// 情景4.3：叔叔节点不存在，或者为黑色，父节点为爷爷节点的右子树
if (uncle == null || isBlack(uncle)) {
// 4.3.1：插入节点为其父节点的右子节点（RR情况）
// 父亲染色为黑色，将爷爷染色为红色
// 然后以爷爷节点左旋，就完成了
if (node == parent.right) {
setBlack(parent);
setRed(gParent);
leftRotate(gParent);
return;
}
// 情景4.3.2：插入节点为其父节点的左子节点（RL情况）
// 以父亲节点进行一次右旋，得到RR双红（4.3.1）的场景
// 然后指定父亲节点进行下一论处理
if (node == parent.left) {
rightRotate(parent);
insertFlxUp(parent);
return;
}
}
}
}
}
/**
* 创建 内部类 RBNode
*
* @param <K> Key
* @param <V> Value
*/
static class RBNode<K extends Comparable<K>, V> {
// parent 父节点
private RBNode parent;
// left 左节点
private RBNode left;
// right 右节点
private RBNode right;
// 节点的颜色
private boolean color;
// key
private K key;
// value
private V value;
public RBNode() {
}
public RBNode(RBNode parent, RBNode left, RBNode right, boolean color, K key, V value) {
this.parent = parent;
this.left = left;
this.right = right;
this.color = color;
this.key = key;
this.value = value;
}
public RBNode getParent() {
return parent;
}
public void setParent(RBNode parent) {
this.parent = parent;
}
public RBNode getLeft() {
return left;
}
public void setLeft(RBNode left) {
this.left = left;
}
public RBNode getRight() {
return right;
}
public void setRight(RBNode right) {
this.right = right;
}
public boolean isColor() {
return color;
}
public void setColor(boolean color) {
this.color = color;
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
}
}
<a name="gAn1Y"></a>
### 辅助工具类
```java
// TreeOperation.java 用来打印方法
package cn.icanci.tree;
/**
* @ClassAction: 打印红黑树
*/
public class TreeOperation {
/*
树的结构示例：
1
/ \
2 3
/ \ / \
4 5 6 7
*/
// 用于获得树的层数
public static int getTreeDepth(RBTree.RBNode root) {
return root == null ? 0 : (1 + Math.max(getTreeDepth(root.getLeft()), getTreeDepth(root.getRight())));
}
private static void writeArray(RBTree.RBNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
// 保证输入的树不为空
if (currNode == null) {
return;
}
// 先将当前节点保存到二维数组中
res[rowIndex][columnIndex] = String.valueOf(currNode.getKey() + "-" + (currNode.isColor() ? "R" : "B") + "");
// 计算当前位于树的第几层
int currLevel = ((rowIndex + 1) / 2);
// 若到了最后一层，则返回
if (currLevel == treeDepth) {
return;
}
// 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
int gap = treeDepth - currLevel - 1;
// 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
if (currNode.getLeft() != null) {
res[rowIndex + 1][columnIndex - gap] = "/";
writeArray(currNode.getLeft(), rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
}
// 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值
if (currNode.getRight() != null) {
res[rowIndex + 1][columnIndex + gap] = "\\";
writeArray(currNode.getRight(), rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
}
}
public static void show(RBTree.RBNode root) {
if (root == null) {
System.out.println("EMPTY!");
}
// 得到树的深度
int treeDepth = getTreeDepth(root);
// 最后一行的宽度为2的（n - 1）次方乘3，再加1
// 作为整个二维数组的宽度
int arrayHeight = treeDepth * 2 - 1;
int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
// 用一个字符串数组来存储每个位置应显示的元素
String[][] res = new String[arrayHeight][arrayWidth];
// 对数组进行初始化，默认为一个空格
for (int i = 0; i < arrayHeight; i++) {
for (int j = 0; j < arrayWidth; j++) {
res[i][j] = " ";
}
}
// 从根节点开始，递归处理整个树
// res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
writeArray(root, 0, arrayWidth / 2, res, treeDepth);
// 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
for (String[] line : res) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < line.length; i++) {
sb.append(line[i]);
if (line[i].length() > 1 && i <= line.length - 1) {
i += line[i].length() > 4 ? 2 : line[i].length() - 1;
}
}
System.out.println(sb.toString());
}
}
}
测试类
// RBTree.java 测试类
package cn.icanci.tree;
import java.util.Scanner;
/**
* @ClassAction: 手写 RBTree 测试类
*/
public class RBTreeTest {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
RBTree<String, Object> rbt = new RBTree();
while (true) {
System.out.print("请输入Key>");
String key = sc.next();
System.out.println();
rbt.insert(key, null);
TreeOperation.show(rbt.getRoot());
}
}
}
总结
- 最重要的一点就是理解红黑树的核心性质
- 性质1：每个节点要么是黑色，要么是红色
- 性质2：根节点是黑色
- 性质3：每个叶子节点（NIL）是黑色
- 性质4：每个红色节点的两个子节点一定都是黑色
性质5：任意一节点到每个叶子节点的路径都包含数量相同的黑节点，俗称黑高
继承体系
- HashMap继承了AbstractMap，实现了Cloneable接口、Serializable接口、Map
Node数据结构
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; } }put原理
- 什么是Hash碰撞：假如我有存储一个元素，发现其Key的Hash值还是1122，那么经过扰动之后，其位置还是2，所以此时，就有冲突，这个时候就要解决冲突。
解决Hash碰撞的方法
threshold：扩容阈值
- loadFactor：负载因子
- size：map实际的元素个数
- modCount：map修改元素的次数，如删除和增加，但是对同一个位置进行修改value，不增加
构造方法
```java public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0)
if (initialCapacity > MAXIMUM_CAPACITY)throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor))initialCapacity = MAXIMUM_CAPACITY;
this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }
public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }
<a name="f4FyE"></a>
# 重要方法tableSizeFor
```java
// 此方法核心功能就是求出，大于等于输入长度的2次幂的值
// 如输出：8，输出为8
// 如输出：9，输出为16
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1; // n = n | (n >>> 1);
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
为什么table长度一定是2的幂
- 计算Hash值得算法，实际就是取模，hash%length，
- 计算机中直接求余效率不如位移运算，源码中做了优化hash&(length-1)
- 要想保证hash%length==hash&(length-1)
- 那么length必须是2的n次方
hash方法
// 扰动函数 // 作用：如果table比较短的时候，让key的hash值的高16位参与路由运算 // 异或：相同为0，不同为1 // 举例如下 // h = 0b 0010 0101 1010 1100 0011 1111 0010 1110 // ^ // 0b 0000 0000 0000 0000 0010 0101 1010 1100 [h >>> 16] // => 0010 0101 1010 1100 0001 1010 1000 0010 // 在 table 还不是很长的情况下，让高16位也参与进来，为了减少冲突和碰撞 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }put方法
```java // 丢值 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
// put的核心方法
// hash: key的hash值
// key: key
// value: value
// onlyIfAbsent: 如果为true,则不要更改现有值
// evict: 如果为false,则表处于创建模式
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab: 当前的HashMap散列表
// p: 当前元素在散列表节点
// n: 当前散列表的长度
// i: 表示路由寻址的结果
Node
<a name="oCH13"></a>
# resize方法
```java
static final int MAXIMUM_CAPACITY = 1 << 30;
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final float DEFAULT_LOAD_FACTOR = 0.75f
// 扩容方法
// 为什么需要扩容？
// 当元素越来越多的时候，hashMap的查找速度就从O(1)升到O(n)，导致链化严重，
// 为了解决冲突带来的查询效率的下降，因此需要扩容[扩容是一个很不好的动作]
final Node<K,V>[] resize() {
// 老的table
Node<K,V>[] oldTab = table;
// 计算老的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 老的扩容阈值
int oldThr = threshold;
int newCap, newThr = 0;
// 如果老的size大于0
if (oldCap > 0) {
// 如果，老的size大于 MAXIMUM_CAPACITY[1 << 30]
// 扩容阈值设置为 Integer.MAX_VALUE
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
// 没有扩容，返回原来的值
return oldTab;
}
// 否则 newCap 增加2倍
// 如果扩容2倍之后，小于MAXIMUM_CAPACITY 并且大于16
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 新的扩容阈值加倍
newThr = oldThr << 1; // double threshold
}
// oldCap == 0 [说明hashMap中的散列表是null]
// 1.new HashMap(initCap,loadFactor)
// 2.new HashMap(intiCap)
// 3.new HashMap(map) 并且Map有数据
else if (oldThr > 0) // initial capacity was placed in threshold
// 新的容量等于老的阈值
newCap = oldThr;
// oldCap == 0 && oldThr == 0
// new HashMap();的时候
else { // zero initial threshold signifies using defaults
// 都赋值为默认值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// newThr为0的时候，通过newCap和loadFactor计算出一个newThr
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 更新阈值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 创建 newTab
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 如果老的表不为空，说明扩容之前不为空
if (oldTab != null) {
// 遍历老的hash表
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// j位置有数据
if ((e = oldTab[j]) != null) {
// 老的设置为null help gc
oldTab[j] = null;
// 如果只有一个元素
if (e.next == null)
// 计算新的位置，这是为e
newTab[e.hash & (newCap - 1)] = e;
// 如果是红黑树节点，则split TODO
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;
// 当前链表的一个元素
Node<K,V> next;
do {
next = e.next;
// hash -> .... 1 1111
// hash -> .... 0 1111
// 0b 1 0000
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;
}
}
}
}
}
return newTab;
}
TreeNode#split方法
// map: 当前map
// tab: newTab
// index: 遍历下标
// bit: oldCap
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
// 当前node节点
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
// 低位
TreeNode<K,V> loHead = null, loTail = null;
// 高位
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
// 遍历当前树节点
// 数据从旧数组转移到新数组中时，旧数组上的数据会根据(e.hash & bit)是否等于0，
// 重新rehash计算其在数组上的索引位置，分两种情况
// 1.等于0时，则将该树链表头节点放到新数组时的索引位置等于其在旧数组时的索引位置，记为低位区树链表lo
// 2.不等于0时，则将该树链表头节点放到新数组时的索引位置等于其在旧数组时的索引位置再加上旧数组长度，记为高位区树链表hi
for (TreeNode<K,V> e = b, next; e != null; e = next) {
// 下一个节点
next = (TreeNode<K,V>)e.next;
e.next = null;
// 区分树链表的高低位
if ((e.hash & bit) == 0) {
// 低位尾部标记为null,表示还未开始处理，此时e是第一个要处理的低位树链表节点，故e.prev等于loTail都等于null
if ((e.prev = loTail) == null)
// 低位树链表的第一个树链表节点
loHead = e;
else
loTail.next = e;
loTail = e;
// 计数器
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
// 当红黑树被split分割开成为两个小红黑树后
// 1.当低位区小红黑树元素个数小于等于6时，开始去树化untreeify操作
// 2.当低位区小红黑树元素个数大于6且高位区红黑树不为null时，开始树化操作(赋予红黑树的特性)
// 低位树链表不为null
if (loHead != null) {
// 小于6
if (lc <= UNTREEIFY_THRESHOLD)
// 开始去树化操作(就是将元素TreeNode节点都转换成Node节点)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
// 若高位数链表头节点为空，说明全部都是低位，高位无需树化
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
// 高位树链表不为null
if (hiHead != null) {
// 高位树链表元素个数若小于等于6
if (hc <= UNTREEIFY_THRESHOLD)
// 开始去树化操作(就是将元素TreeNode节点都转换成Node节点)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
// 若低位数链表头节点为空，说明还没有处理完全部都是高位，无需树化
if (loHead != null)
hiHead.treeify(tab);
}
}
}
treeifyBin方法
static final int MIN_TREEIFY_CAPACITY = 64
// 树化方法
final void treeifyBin(Node<K,V>[] tab, int hash) {
// n:数组长度
// index:hash的下标
// e:hash的桶节点
int n, index; Node<K,V> e;
// 如不tab == null 或者 长度小于最小64
// 扩容
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);
// tab[index] 下标不为null
// 进行树化
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
TreeNode#treeify和TreeNode#untreeify方法
// 树化方法
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)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
// 将树转换为数组节点
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
get方法
// get方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
// 获取节点
// key 的 hash
// key
final Node<K,V> getNode(int hash, Object key) {
// tab:当前哈希表的引用
// first:桶位中的头元素
// e:临时node元素
// n:数组长度
// k:key
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 如果头节点直接匹配到了
// hash 和 key.equals(k)
// 至二级返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 如果下个节点不为null
if ((e = first.next) != null) {
// 如果是TreeNode节点
if (first instanceof TreeNode)
// 去红黑树中进行寻找
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 否则遍历数组进行寻找
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
remove方法
// 移除key
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
// 移除key
// hash:hash
// key:key
// value:value
// matchValue:如果为true，则仅在值相等时删除
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
// tab:当前的hash表
// p:桶元素
// n:数组长度
// index:hash出来的下标
Node<K,V>[] tab; Node<K,V> p; int n, index;
// tab 不为空
// 长度大于0
// 当前桶节点存在且不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
// node:目标节点
// e：当前Node的下一个元素
// k:key
// v:value
Node<K,V> node = null, e; K k; V v;
// 就是当前节点，找到了
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// node为当前桶节点
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)))) {
// 如果node是红黑树节点
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;
}
replace方法
// 寻找并替换
@Override
public boolean replace(K key, V oldValue, V newValue) {
Node<K,V> e; V v;
if ((e = getNode(hash(key), key)) != null &&
((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
e.value = newValue;
afterNodeAccess(e);
return true;
}
return false;
}
@Override
public V replace(K key, V value) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) != null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}
参考文章
- Map-HashMap & HashSet 源码解析：https://www.pdai.tech/md/java/collection/java-map-HashMap&HashSet.html
- Java-Review：https://gitee.com/icanci/Java-Review
- 红黑树之Java实现：https://www.cnblogs.com/skywang12345/p/3624343.html
红黑树深入剖析及Java实现：https://zhuanlan.zhihu.com/p/24367771
推荐网站
演示的网站：
- 数据结构演示网站1：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
- 数据结构演示网站2：https://visualgo.net/zh
- 数据结构演示网站3：https://algorithm-visualizer.org/
- 网站1截图：
- 网站2截图：
- 网站3截图：
若有收获，就点个赞吧
0 人点赞
