Hash的特点：
- 从hash值不可以反向推导出原始的数据
- 输入数据的微小变化会得到完全不同的hash值，相同的数据得到相同的值
- 哈希算法的执行效率很高效，长的文本也能快速的计算出哈希值
- hash算法的冲突概率较小
hash冲突： 由于hash的原理是将 输入的较大值 映射到 hash空间，而hash值是要小于输入空间大，所以必然会有不同的输入对象映射成相同的hash值例如：10个苹果放到9个抽屉，必然有一个抽屉里放了2个苹果
4.1.简介
4.1.1.概述
基于哈希表的Map接口实现，它存储的是内容是键值对
源码注释
//1、哈希表基于map接口的实现，这个实现提供了map所有的操作，并且提供了key和value可以为null，(HashMap和HashTable大致上是一样的除了hashmap是异步的和允许key和value为null)，//这个类不确定map中元素的位置，特别要提的是，这个类也不确定元素的位置随着时间会不会保持不变。Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key.(The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map;in particular, it does not guarantee that the order will remain constant over time.//假设哈希函数将元素合适的分到了每个桶(其实就是指的数组中位置上的链表)中，则这个实现为基本的操作(get、put)提供了稳定的性能，迭代这个集合视图需要的时间跟hashMap实例(key-value映射的数量)的容量(在桶中)//成正比，因此，如果迭代的性能很重要的话，就不要将初始容量设置的太高或者loadfactor设置的太低，【这里的桶，相当于在数组中每个位置上放一个桶装元素】This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.//HashMap的实例有两个参数影响性能，初始化容量(initialCapacity)和loadFactor加载因子，在哈希表中这个容量是桶的数量【也就是数组的长度】，一个初始化容量仅仅是在哈希表被创建时容量，在//容量自动增长之前加载因子是衡量哈希表被允许达到的多少的。当entry的数量在哈希表中超过了加载因子乘以当前的容量，那么哈希表被修改(内部的数据结构会被重新建立)所以哈希表有大约两倍的桶的数量An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table,and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get beforeits capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash tableis rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.//通常来讲，默认的加载因子(0.75)能够在时间和空间上提供一个好的平衡，更高的值会减少空间上的开支但是会增加查询花费的时间（体现在HashMap类中get、put方法上），当设置初始化容量时，应该考虑到map中会存放//entry的数量和加载因子，以便最少次数的进行rehash操作，如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookupcost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be takeninto account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number ofentries divided by the load factor, no rehash operations will ever occur.//如果很多映射关系要存储在 HashMap 实例中，则相对于按需执行自动的 rehash 操作以增大表的容量来说，使用足够大的初始容量创建它将使得映射关系能更有效地存储。If many mappings are to be stored in a HashMap instance, creating it with a sufficiently large capacity will allow the mappings to be stored more efficiently than lettingit perform automatic rehashing as needed to grow the table
4.1.2.数据结构和存储原理
jdk1.7的hashmap，采用数组+链表
- 插入对象到链表使用头插法
jdk1.8后引入红黑树，并且改用尾插法
HashMap内部有一个entry的内部类，其中有四个属性，我们要存储一个值，则需要一个key和一个value，存到map中就会先将key和value保存在这个Entry类创建的对象中。
static class Entry<K,V> implements Map.Entry<K,V> {final K key; //就是我们说的map的keyV value; //value值，这两个都不陌生Entry<K,V> next;//指向下一个entry对象int hash;//通过key算过来的你hashcode值。}
构造好了entry对象，然后将该对象放入数组中
- 通过entry对象中的hash值来确定该对象存放在哪个位置，如果该位置有其他元素就用链表的方式存储
4.1.3.属性
HashMap的实例有两个参数影响其性能。
- 初始容量：哈希表中桶的数量
- 加载因子：哈希表在其容量自动增加之前可以达到多满的一种尺度
当哈希表中条目数超出了当前容量*加载因子(其实就是HashMap的实际容量)时，则对该哈希表进行rehash操作，将哈希表扩充至两倍的桶数。
Java中默认初始容量为16，加载因子为0.75。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16static final float DEFAULT_LOAD_FACTOR = 0.75f;
(1) loadFactor装载因子
loadFactor默认为0.75 是一个较为良好的状态，如果过大可能虽然会提高空间利用率，但是会导致查找速度变慢，如果太小就会导致空间利用率降低！
(2) capacity
capacity译为容量代表的数组的容量，也就是数组的长度，同时也是HashMap中桶的个数。默认值是16。
扩容默认是2倍，都是2的幂
static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;
4.2.构造方法
public HashMap(int initialCapacity, float loadFactor) {
//做了一些校验，capacity必须大于0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//capacity最大只能为MAXIMUM_CAPACITY，超过就直接使用MAXIMUM_CAPACITY
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//负载因子不能小于0，也不能为非数
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//负载因子赋值
this.loadFactor = loadFactor;
//计算threshold-->由于表的长度有要求（2的次方数）
this.threshold = tableSizeFor(initialCapacity);
}
tableSizeFor()
/**
* Returns a power of two size for the given target capacity.
返回一个大于等于当前值cap的数字，并且符合2的次方数
cap= 10
n = 10-1 =9
0b1001 | 0b0100 => 0b1101
0b1101 | 0b0011 => 0b1111
ob1111 | ob0000 => ob1111
ob1111 | ob0000 => ob1111
....
=> ob1111 => 15
由于上面的运算最后的结果一般都是 以1111结尾的，所以最后+1变成 1000结尾，那么就肯定是2的次方数
右移是指二进制 1001 -> 00｜10｜01 去掉右边的01，加上左边进来的00 -> 0010 (右移2位)
（右移几位就几个0）
|运算=>或运算，遇1为1
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
//目的是获得离cap最近的并且符合2的次方数的值，万一传入16不-1的话返回就是32，会超出要求
//所以这里-1可以获得最近的
n |= n >>> 1; //右移一位 然后进行或运算
n |= n >>> 2; //右移2位 ..
n |= n >>> 4; //...
n |= n >>> 8; //..
n |= n >>> 16; // => n=15
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
//最后return n+1 16
}
4.3.主要方法
put()
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
调用了hash()方法: 扰动函数->让哈希值更加散列，在寻址的时候减少哈希冲突
数组长度很短时，只有低位的hashcode值能参与运算，而让高16位参与运算可以更好的均匀散列，减少碰撞，进一步降低hash冲突的几率。并且使得高16位和低16位的信息都被保留了
//作用：让key的hash值的高16位（高位）也参与路由运算
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
//key-null存放在0位
}
主要还是通过==putVal()==方法实现的
/**
* Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value(一般为false)
如果key已存在，则不插入数据
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//tab表示当前hashMap的散列表。 p表示散列表的元素， n表示散列表的长度，i表示路由寻址结果
Node<K,V>[] tab; Node<K,V> p; int n, i;
//只有第一次插入数据才会初始化（否则不插数据就建立散列表结构会浪费资源）
if ((tab = table) == null || (n = tab.length) == 0) //当散列表未被初始化
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) //路由寻址结果下标位置为null
tab[i] = newNode(hash, key, value, null);
else { //下标位置已经有元素了
//e：Node临时元素； k：表示临时的key
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //表示插位中的元素与需要插入的元素完全一致，后续需要替换
else if (p instanceof TreeNode)//当前位置已经为红黑树
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//链表情况，且头元素与插入元素不一致
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {//当迭代到最后一个元素也没有key相同的
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; //找到了key相同元素，需要替换操作
p = e;
}
}
//需要替换的情况：
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue; //结束put方法，返回被替换前的值
}
}
//记录结构修改次数（替换除外）
++modCount;
if (++size > threshold)//如果size值大于扩容阈值，则扩容
resize();
afterNodeInsertion(evict);
return null;
}
resize()
扩容 -> 为了解决哈希冲突导致的链化影响查询效率的问题，扩容会缓解该问题
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; //引用扩容前的哈希表
int oldCap = (oldTab == null) ? 0 : oldTab.length;//判断是扩容还是初始化
int oldThr = threshold; //表示扩容之前的阈值（也就是触发本次扩容的阈值）
int newCap, newThr = 0; //newCap扩容之后达到的长度。newThr新的阈值
if (oldCap > 0) { //正常扩容
if (oldCap >= MAXIMUM_CAPACITY) { //如果数组已经达到默认的最大长度，无法扩容
threshold = Integer.MAX_VALUE; //设置扩容条件位int最大值
return oldTab;
}
//oldCap左移一位（翻1倍）后，小于数组最大限制，并且扩容之前的数组长度>=16
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold 扩容条件阈值也翻倍
}
//初始化情况 oldCap==0 oldThr不为0
//以下构造方法会给oldThr赋值
//new HashMap(initCap, loadFactor);
//new HashMap(initCap)
//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; //16
//通过长度*负载因子计算扩容阈值
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //12
}
if (newThr == 0) { //如果新扩容阈值没有被赋值
float ft = (float)newCap * loadFactor; //计算扩容阈值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; //给全局变量赋值
//以上代码主要是给newCap和newThr赋值 扩容后的数组大小和新的扩容阈值
//扩容⬇️
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //创建出一个扩容需要大小的数组
table = newTab;
//⬇️说明hashMap本次扩容之前，table不为null
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) { //遍历处理
Node<K,V> e;
if ((e = oldTab[j]) != null) { //将节点赋值给e，且不为null
oldTab[j] = null;//将原来的数组该位置变为null，方便gc
if (e.next == null) //表示为单个数据（非链表非树） (hash无冲撞)
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;
//高位链表：重新进行路由寻址后需要更改位置的数据,例如15->31
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) { //低位链表
//例如15中hash为 0 1111的元素（不改变位置
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {//例如15中 hash为 1 1111的元素（高位链表
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null; //把原来的链表拆分需要用null来表示拆分
newTab[j] = loHead;//把链表放到新map的对应位置（原来的位置）
}
if (hiTail != null) {
hiTail.next = null;//把原来的链表拆分需要用null来表示拆分
newTab[j + oldCap] = hiHead;//把链表放到新位置
}
}
}
}
}
return newTab;
}
链表扩容机制图：
解释：原来在16长度的map中，存放在15这个位置的元素hash值通过路由寻址得到的结果都是以1111结尾的（1111=>15)，那么现在map扩容到32了，重新进行路由寻址的话，在15这个位置的元素就会得到两种新的路由寻址结果：要么是（01111）要么是（11111）！只有这两种情况，如果是01111那么还是存放在15这个位置，如果是11111就需要存放在新map的31这个位置了
get()
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
//存的时候通过hash(key)，那么取的时候也要通过hash(key)
}
主要是通过getNode方法获得元素
/**
* Implements Map.get and related methods.
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
//tab:引用当前hashMap的散列表， first：桶位中的头元素， e：临时node元素
// n ：table数组长度
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) { //first为桶位第一个元素
if (first.hash == hash && // 总是最先判断第一个元素
((k = first.key) == key || (key != null && key.equals(k))))
return first; //需要的元素就是first元素
if ((e = first.next) != null) {
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()
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
主要调用了removeNode()方法
/**
* Implements Map.remove and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to match if matchValue, else ignored
* @param matchValue :需要key和value都匹配才删除
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
//tab：引用当前散列表； p：当前node元素； n：散列表数组长度 index：寻址结果
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 && //当前p为桶位第一个数据
((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; //p存储上一个节点
} while ((e = e.next) != null);
//最后会将目标元素赋值给node
}
}
//以上是查找元素⬆️
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode) //红黑树remove
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)//如果是第一个元素
tab[index] = node.next; //那么就将下一个元素作为头节点
else //链表中间的元素
p.next = node.next; //指针后移
++modCount; //记录操作
--size; //记录size
afterNodeRemoval(node);
return node; //返回被移除的元素
}
}
return null;
}
Replace()
主要是找到对应key的元素用新的value替换
@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)))) {
//这里多了一步判断通过key找到的元素的值是否和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;
}
4.4.红黑树
4.4.1.二叉搜索树原理
- 删除
- 删除一个没有子节点的节点：
- 直接改变他的父节点引用该节点的值为null
- 删除有一个子节点的节点
- 将其父节点原本指向该节点的引用，改为指向该节点子节点即可
- 删除有两个子节点的节点
- 用后继节点代替当前节点的位置
- 后继节点：（大于该节点的最小节点）
- 删除一个没有子节点的节点：
二叉搜索树可以完成以链表的形式表示二分查找算法功能
二叉搜索树在极端情况下会失衡导致退化为链表,例：
6
/ \
5 7
/
4
/
3
/
2
如何解决：（平衡二叉搜索树）
4.4.2.红黑树性质
- 节点要么是 黑色 要么是 红色
- 根节点是黑色
- 每个叶子节点(NIL)是 黑色
- 每个红色节点的两个子节点一定都是黑色，不能有两个红色节点相连
- 任意一个节点到每个叶子节点的路径都包含数量相同的黑节点，俗称黑高
- 从性质5可以推出：如果一个节点存在黑子节点，那么该节点肯定有两个子节点
- 如果没有两个子节点的话，除了黑子节点另外一个就会变成NIL就破坏了黑高
//例：该节点如果没有两个子节点的话，那么左边NIL到节点的黑高是1，右边则是0.破坏了黑高 ..... / 节点 / \ 黑 NIL / \ NIL NIL
- 如果没有两个子节点的话，除了黑子节点另外一个就会变成NIL就破坏了黑高
红黑树并不是完美平衡的二叉查找树， 但是左子树和右子树的黑节点的层数是相等的—>性质5
所以我们叫红黑树这种平衡为黑色完美平衡
4.4.3.红黑树自平衡操作
红黑树能够做到自平衡 靠的是： 左旋，右旋，变色
- 变色： 节点的颜色由红变黑或由黑变红
- 左旋： 以某个节点作为支点（旋转节点），其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，左子节点保持不变
- 右旋：以某个节点作为支点（旋转节点），其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持不变
相反就是右旋
//左旋
p p
| |
x y
/ \ ----> / \
lx y x ry
/ \ / \
ly ry lx ly
//右旋
p p
| |
y x
/ \ ----> / \
x ry lx y
/ \ / \
lx ly ly ry
4.4.4.红黑树插入
1.查找插入的位置
2.插入后的自平衡
- 插入场景：
- 1.红黑树为空：
- 直接把插入节点作为根节点—>根据性质2 把插入节点变为黑色
- 2.插入的key已存在：
- 替换value
- 3.插入节点的父节点为黑节点：
- 插入的节点是红色，并不会影响红黑树的平衡，直接插入即可，无需自平衡
- 4.插入节点的父节点为红色节点（红红双连）：
- 4.1.如果叔叔节点存在，且为红色
- 根据性质知道，红红不能相连，同时爷爷节点是黑色节点
- 把当前节点的父亲节点以及叔叔节点都变为黑色，把爷爷节点变成红色
- 然后把爷爷节点变成当前节点—>然后根据当前情况重新选择操作
- 4.2.叔叔节点不存在，或为黑色节点，并且插入节点的父亲节点是爷爷节点的左节点
- 但是根据性质5，叔叔节点非红即空（NIL）否则该路径会比其他路径多一个黑节点
- 4.2.1.插入节点为父亲节点的左子节点（LL双红情况）
- 变颜色：将P节点（父亲）变为黑色，将PP（爷爷）变为红色
- 对PP（爷爷）节点进行右旋
- 4.2.2.插入节点为父亲节点的右子节点（LR双红）
- 对P节点（父亲）进行左旋->变为LL双红情况
- 像4.2.1一样处理LL双红情况—>变色—>PP右旋
- 4.1.如果叔叔节点存在，且为红色
- 1.红黑树为空：
- 4.3.【和4.2是反方向】叔叔节点不存在或黑色，且插入节点的父节点是爷爷节点的**右节点**
- 4.3.1.插入节点为父节点的右子节点（RR双红）
- 变颜色：将P变黑，PP变红
- 以PP为旋转点进行**左旋**
- 4.3.2.插入节点为父节点的左子节点（RL双红）
- 对P节点进行**右旋**-->变为**RR双红**
- 像4.3.1一样处理RR双红情况-->变色-->PP**左旋**
插入例子：
插入7—-> 情况4.1+情况4.2.2—->变色-左旋-变色-右旋
4.4.5.代码实现红黑树
package com.roderick;
public class RBTree<K extends Comparable<K>,V>{
private static final boolean RED = true;
private static final boolean BLACK = false;
/**树根的引用*/
private RBNode root;
public RBNode getRoot() {
return root;
}
/**
* 获取当前节点的父节点
* @param node
*/
private RBNode parentOf(RBNode node){
if (node !=null){
return node.parent;
}
return null;
}
/**
* 节点是否为红色
* @param node
*/
private boolean isRed(RBNode node){
if(node !=null){
return node.color == RED;
}
return false;
}
/**
* 节点是否为黑色
* @param node
*/
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);
}
//重载实现中序⬇
private void inOrderPrint(RBNode root){
if(root!=null){
inOrderPrint(root.left);
System.out.println("key: "+ root.key+" value: "+ root.value);
inOrderPrint(root.right);
}
}
/**
* 左旋方法：
* 示意图：左旋x节点
* p p
* | |
* x y
* / \ ----> / \
* lx y x ry
* / \ / \
* ly ry lx ly
* 1.将x的右子节点指向y的左子节点（ly），并将y的左子节点的父节点更新为x
* 2.当x的父节点（不为空时）更新y的父节点为x的父节点（p），并将p的子树更新为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的父节点（p）
if(x.parent!=null){
y.parent=x.parent;
//并将p的子树更新为y
if(x == x.parent.left){
x.parent.left = y;
}else{
x.parent.right = y;
}
}else{ //x为根节点，更新y为根节点
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的右子节点（ly），并且更新x的右子节点的父节点为y
* 2.当y的父节点（不为空时）更新x的父节点为y的父节点（p），并将p的子树更新为x
* 3.将y的父节点更新为x，将x的右子节点连向y
*/
private void rightRotate(RBNode y){
RBNode x = y.left;
//将y的左子节点指向x的右子节点（ly），并且更新x的右子节点的父节点为y
y.left = x.right;
if(x.right!=null){
x.right.parent = y;
}
//当y的父节点（不为空时）更新x的父节点为y的父节点（p），并将p的子树更新为x
if(y.parent!=null){
x.parent = y.parent;
if(y==y.parent.left){
x=y.parent.left;
}else{
x=y.parent.right;
}
}else{ //当y为根节点时
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);
insert(node);
}
private void insert(RBNode node){
//1.查找当前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.setValue(node.getValue());
return; //替换完毕结束
}else{
x=x.left;
}
}
node.parent = parent;
if(parent!=null){
//判断node与parent的key的大小关系-->存入左子节点还是右子节点
int cmp = node.key.compareTo(parent.key);
if(cmp>0){
parent.right = node;
}else{
parent.left = node;
}
}else{ //红黑树为空--->直接插入
this.root=node;
}
//调用红黑树自平衡的方法
insertFixUp(node);
}
/**
* 红黑树自平衡方法
* ｜---情况1： 红黑树为空树，将根节点染为黑色
* ｜---情况2： 插入节点的key已存在：在插入时已做过处理
* ｜---情况3： 插入节点的父节点为黑色， 插入的所在路径黑色节点并没有变化，所以红黑树依然平衡
*
* ｜---情况4： 插入节点的父节点为红色
* ｜---情况4.1: 叔叔节点存在，且为红色（父-叔 双红）
* ｜ -将父亲和叔叔染色为黑色，将爷爷染色为红色，再以爷爷节点为当前节点进行下一轮处理
* ｜---情况4.2: 叔叔节点不存在或者为黑色，并且插入节点的父亲节点是爷爷节点的左子节点：
* ｜---情况4.2.1: 插入节点为其父节点的左子节点（LL双红）：
* ｜ -将爸爸染色为黑色，将爷爷染色为红色，然后以爷爷节点右旋
* ｜---情况4.2.2: 插入节点为其父节点的右子节点（LR双红）：
* ｜ -以父亲节点进行一次左旋，得到LL双红情况（4.2.1)
* ｜ -指定父亲节点为当前节点进行下一轮处理-->4.2.1
* ｜---情况4.3: 和4.2相反 叔叔节点不存在或者为黑色，并且插入节点的父亲节点是爷爷节点的右子节点：
* ｜---情况4.3.1: 插入节点为其父节点的右子节点（RR双红）
* ｜ -将爸爸染色为黑色，将爷爷染色为红色，然后以爷爷节点左旋
* ｜---情况4.3.2: 插入节点为其父节点的左子节点（RL双红）：
* ｜ -以父亲节点进行一次右旋，得到RR双红情况（4.3.1)
* ｜ -指定父亲节点为当前节点进行下一轮处理-->4.3.1
*/
private void insertFixUp(RBNode node){
this.root.setColor(BLACK);
RBNode parent = parentOf(node);
if(parent==null) return;
RBNode gParent = parentOf(parent);
if(parent!=null && isRed(parent)){ //情况4
//如果父节点是红色，那么一定存在爷爷节点,因为根节点不可能是红色
RBNode uncle = null;
uncle = parent==gParent.left? gParent.right : gParent.left; //判断叔叔节点是左节点还是右节点
if(uncle != null && isRed(uncle)){ //情况4.1
setBlack(parent);
setBlack(uncle);
setRed(gParent);
insertFixUp(gParent);//再以爷爷节点为当前节点进行下一轮处理
return;
}else{
if(parent==gParent.left){ //情况4.2
//情况4.2.1: 插入节点为其父节点的左子节点（LL双红）：
if(node==parent.left){
setBlack(parent);
setRed(gParent);
rightRotate(gParent); //右旋
return;
}else{//情况4.2.2: 插入节点为其父节点的右子节点（LR双红）：
leftRotate(parent);
insertFixUp(parent); //递归 指定父亲节点为当前节点进行下一轮处理
return;
}
}else{//情况4.3
if(node==parent.right){//情况4.3.1: 插入节点为其父节点的右子节点（RR双红）
setBlack(parent);
setRed(gParent);
leftRotate(gParent);//左旋
return;
}else{//情况4.3.2: 插入节点为其父节点的左子节点（RL双红）：
rightRotate(parent);
insertFixUp(parent);//递归 指定父亲节点为当前节点进行下一轮处理
return;
}
}
}
}
}
static class RBNode <K extends Comparable<K>,V>{
private RBNode parent;
private RBNode left;
private RBNode right;
private boolean color;
private K key;
private V value;
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() {
}
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;
}
}
}
若有收获，就点个赞吧
0 人点赞
