对二叉排序树加以约束，要求每个结点的左右两个子树的高度差的绝对值不超过1，这样的二叉树称为平衡二叉树，同时要求每个结点的左右子树都是平衡二叉树，这样，就不会因为一边的疯狂增加导致失衡。
失衡情况包括以下四种：
左左失衡：通过右旋进行调整。
右右失衡：通过左旋进行调整。
左右失衡：先进行左旋，再进行右旋来调整。
右左失衡：先进行右旋，再进行左旋来调整。
通过以上四种情况的处理，最终得到维护平衡二叉树的算法。
红黑树有了平衡二叉树，为什么还需要红黑树？
1、AVL的左右子树高度差不能超过1，每次进行插入、删除 *** 作时，几乎都需要通过旋转 *** 作保持平衡。
2、在频繁进行插入/删除的场景中，频繁的旋转 *** 作使得AVL的性能大打折扣。
3、红黑树通过牺牲严格的平衡，换取插入/删除时少量的旋转 *** 作，整体性能优于AVL。红黑树插入时的不平衡，不超过两次旋转就可以解决；删除时的不平衡，不超过三次旋转就能解决。
红黑树的特性:
（1）每个节点或者是黑色，或者是红色。（非黑即红）
（2）根节点是黑色。
（3）每个叶子节点都是黑色的空节点（NIL节点）。
（4）如果一个节点是红色的，则它的子节点必须是黑色的。(根到叶子的所有路径不可能存在两个连续的红色节点)
（5）从一个节点到该节点的叶子节点的所有路径上包含相同数目的黑节点。（相同的黑色高度）
约束4和5，保证了红黑树的大致平衡：根到叶子的所有路径中，最长路径不会超过最短路径的2倍。
红黑树的基本插入规则
基本的插入规则和平衡二叉树一样，但是在插入后：
1. 将新插入的节点标记为红色。
情况1：父节点是黑色节点，直接插入，无需任何 *** 作调整（不会打破上述规则）
情况2：插入的节点为根结点，则标记为黑色。
情况3：父节点是红色节点，需要调整（打破规则4）。
①叔节点为红色（叔父同色）
①.1 将叔节点、父节点都标记为黑色
①.2 祖父节点标记为红色
①.3 然后把祖父节点当作插入节点进行分析
②叔节点为黑色（叔父异色）
要分四种情况处理
a.左左 (父节点是祖父节点的左孩子，并且插入节点是父节点的左孩子)
进行右旋 *** 作
b.左右 (父节点是祖父节点的左孩子，并且插入节点是父节点的右孩子)
进行左旋、再进行右旋 *** 作
c.右右 (父节点是祖父节点的右孩子，并且插入节点是父节点的右孩子)
进行左旋 *** 作
d.右左 (父节点是祖父节点的右孩子，并且插入节点是父节点的左孩子)
进行右旋、再进行左旋 *** 作
其实这种情况下处理就和的平衡二叉树一样。
最后还是对于祖父节点重新进行分析。
分步和动画演示
向下面这棵树插入26；
插入后26是红色，判断当前为情况3中的①，进行变色 *** 作；
变色 *** 作后，找到26的祖父节点22，再重新进行分析。节点22满足情况3中的②中的c，就是右右的情况，因此需要进行左旋；
左旋之后如下图所示，节点22的祖父节点为15（见上图），15作为插入节点变为红色；
15变红色，父节点为根节点变成黑色，15没有祖父节点，红黑树插入流程结束。
动图展示：
其他情况可以通过以下链接的动画演示，自行分析，或者参考维基百科的详细分析。
动画演示链接：（由于附上外部链接会被gf警告，需要动画演示链接可以私信获取！）
HashMap底层实现（JDK1.8）在JDK1.8里面，HashMap是通过数组 + 链表 + 红黑树实现的，这部分的分析主要通过对源码的解读实现理解，具体看注释。
首先我们需要知道HashMap当中的成员变量。
基础参数 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 必须是2的幂 <= 1<<30，即最大容量 为 2的30次方。
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 构造函数中未指定时使用的负载系数（默认的加载因子）。
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 将树而不是列表用于存储的存储单元计数阈值
* 桶。当向至少有这么多节点的容器中添加元素时，容器将转换为树。大于2，* 该值必须并且至少应为8
*/
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 可将链表转化成红黑树的数组的最小容量。
*（否则，如果bin中的节点太多，则会调整表的大小。）
* 应至少为4*TreeFiy_阈值，以避免调整大小和转化红黑树阈值之间的冲突。
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* 此映射中包含的键值映射数。
*/
transient int size;
/**
* 哈希桶，存放链表。长度是2的N次方，或者初始化时为0。
*/
transient Node<K,V>[] table;
transient int modCount;
/**
* 要调整大小的下一个大小值（容量 * 负载系数）
* 哈希表内元素数量的阈值，当哈希表内元素数量超过阈值时，会发生扩容resize()
*/
// javadoc描述在序列化时为真。
// 此外，如果尚未分配表数组，则此字段将保留初始数组容量，或表示为零
// 默认容量（初始容量）
int threshold;
/**
* 哈希表的加载因子，用于计算哈希表元素数量的阈值。
* threshold = 哈希桶.length * loadFactor
*/
final float loadFactor;
然后来看看最经常用到的put()⽅法
public V put(K key, V value) {
// 根据key计算hashcode，相对于JDK7中hash算法有所简化
return putVal(hash(key), key, value, false, true);
}
下面来看看hash方法，变量先保存了hashcode值，然后进行了一次异或运算。
这个异或运算可以近似看作是hashcode值的高位和低位进行的异或，为什么需要这样处理hashcode值呢？
这个主要跟JDK1.8中HashMap计算下标值有关，并不是通过对数组的大小取余进行计算，而是通过对（数组 - 1）进行与运算得到的一个下标值。提前处理hashcode值，得到结果是通过hashcode值高位和低位一起计算出来的，所以后续的与运算不只是是hashcode的低位有关，也就是这个下标（索引）值是由hashcode值的高位和低位一起决定的。
/* ---------------- Static utilities -------------- */
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
putVal()⽅法 ，注意这里还对putIfAbsent()方法实现了一定程度的维护。
putVal()⽅法中要点：
普通链表可能转化成红黑树Node -> TreeNode
单向链表会改造成双向链表，再变成红黑树，所以红黑树的结构既是红黑树，也是双向链表。
// 如果参数onlyIfAbsent是true，那么不会覆盖相同key的值value，用于实现putIfAbsent()方法。如果evict是false。那么表示是在初始化时调用的。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 给tab赋值，并判断数组是否为null，如果是则初始化数组，并得到数组⼤⼩n
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 根据hashcode计算出对应的数组下标i，并判断该位置是否存在元素
// 下标i 是利用 哈希值 & 哈希桶的长度-1，替代模运算
// 如果为null，则⽣成⼀个Node对象赋值到该数组位置
// 否则，将该位置对应的元素取出来赋值给p
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 如果该下标位置存在元素，则进⾏⼀系列判断
Node<K,V> e; K k;
// ⾸先判断该下标位置存在的元素的key是否和当前put进来的key是否相等
// 如果相等，则再后续代码中更新value，并返回oldValue，就是覆盖的 *** 作
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果该下标位置存在的元素的类型是TreeNode，表示该位置存的是⼀颗红⿊树
// 那么就会把新元素添加到红⿊树中，并且也会判断新key是否已经存在红⿊树中
// 如果存在则返回该TreeNode，并在后续代码中更新value，完成红黑树节点的覆盖
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 否则该位置存的是⼀个链表，那就要把新元素插⼊到链表中
// 因为要看当前链表的⻓度，所以就需要遍历链表
// 在遍历链表的过程中，⼀边记录链表上的元素个数，⼀边判断是否存在相同的key
// 遍历到尾节点后，将新元素封装为Node对象并插⼊到链表的尾部
// 并且链表上的元素个数如果已经有8个了（不包括新元素对应的节点），则将链表改造为红⿊树
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 将新元素封装为Node对象并插⼊到链表的尾部(尾插法)
p.next = newNode(hash, key, value, null);
//链表上的元素个数如果已经有8个了（不包括新元素对应的节点），则将链表改造为红⿊树，也就是转化成的红黑树至少有9个节点
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;
}
}
// 如果key存在相同的，则更新value，完成覆盖，并返回oldValue
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 这是一个空实现的函数，用作LinkedHashMap重写使用。
afterNodeAccess(e);
return oldValue;
}
}
// 增加修改次数
++modCount;
// 新元素插⼊之后，判断是否需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
通过代码简单理解方法的返回值
import java.util.HashMap;
public class Main {
public static void main(String[] args) {
HashMap<String, String> map = new HashMap<>();
map.put("orange", "2");
String result = map.put("orange", "3");
System.out.println(result);
System.out.println(map.get("orange"));
String result2 = map.putIfAbsent("orange", "4");
System.out.println(result2);
System.out.println(map.get("orange"));
}
}
2
3
3
3
treeifyBin()方法比较简单，这里只实现了一些简单的逻辑判断处理，在这段代码中可以看到有用到resize()方法、replacementTreeNode()方法和treeify()方法，后面这两种方法本文不会过多赘述，涉及红黑树的理论基础也在开篇解释过了，下面的文章还会对resize()方法进行分析。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 数组⻓度如果⼩于MIN_TREEIFY_CAPACITY(默认为64)，则会扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 把链表改造为双向链表，并且把节点类型改为TreeNode
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);
}
}
resize()方法，用于实现数组初始化和数组的扩容。在扩容的过程中，和JDK1.7相比，JDK1.8不需要重新进行rehash。
发生扩容的状况有两种：
①链表长度大于8，并且数组的长度小于64。
②HashMap中的元素的个数超过阈值threshold。
扩容中有几个要点：
扩容之后数组下标只有以下两种情况（这也是为什么不用rehash）
扩容之后数组下标 = 扩容之前数组下标 + 老数组的大小
扩容之前数组下标 = 扩容之后数组下标
转移有三种情况：
单个元素转移：直接执行 e.hash & (newCap - 1)，从老数组转移到新数组中。
链表转移：链表拆分为两个链表，一个是高位链表，一个是低位链表。
红黑树转移：见后面split()方法的代码分析。
// resize()方法可以实现：数组初始化和扩容
final Node<K,V>[] resize() {
// 记录当前数组信息
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 当前的阈值
int oldThr = threshold;
// 计算新数组的数组⼤⼩、扩容阈值
int newCap, newThr = 0;
// 如果老数组⼤⼩⼤于0，则双倍扩容
if (oldCap > 0) {
// 如果当前容量已经到达上限
if (oldCap >= MAXIMUM_CAPACITY) {
// 则设置阈值是2的31次方-1
threshold = Integer.MAX_VALUE;
// 同时返回当前的哈希桶，不再扩容
return oldTab;
}
// 否则新的容量为旧的容量的两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 新的阈值也等于旧的阈值的两倍
newThr = oldThr << 1; // double threshold
}
// 表示要初始化数组，但是用户指定了初始化容量
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 表示要初始化数组，⽤默认值
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 用新数组的⼤⼩计算新数组的扩容阈值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 更新阈值
threshold = newThr;
// 生成新数组，并赋值给table属性
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 更新哈希桶引用
table = newTab;
// 如果是扩容，则把老数组上的元素转移到新数组上
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 遍历数组的每⼀个位置，j是老数组的下标
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 如果该位置只有⼀个元素，则直接转移到新数组上
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果该位置上的元素是TreeNode，则对这颗红⿊树进⾏转移
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;
// 加⼊低位链表
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;
}
split()⽅法中要点：
对于红黑树的转移，拆分后，红黑树可能转化成链表+红黑树，链表+链表，红黑树+红黑树，红黑树。
当红黑树的元素个数小于等于6，则退化成链表。
如果当前红黑树还是转化成一棵红黑树，则直接转移，不需要重新构造红黑树。
否则，在其他状况下转移，如果仍然存在红黑树，则是需要重新构造的。
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
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;
// 由于红黑树是有链表改造而成，所以链表其实还是存在的
// 对链表进行高低拆分
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) {
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;
}
}
// 拆分之后，如果存在低位链表，则看链表长度，如果⼩于等于UNTREEIFY_THRESHOLD
// 则把节点类型改为Node类型，红黑树退化成链表
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
// 红黑树退化成链表
tab[index] = loHead.untreeify(map);
else {
// 否则，把头结点转移到新节点（红黑树的根节点⼀定是链表的头节点）
tab[index] = loHead;
// 如果存在高位链表
if (hiHead != null) // (else is already treeified)
//红黑树结构改变，这里需要重新生成红黑树
loHead.treeify(tab);
//否则红黑树结构不变，直接照搬到指定的位置
}
}
// 同上分析
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
对于底层原理简单的分析过后，在JDK1.8中，HashMap底层的一个源码流程图如下。
补充这部分内容的HashMap在jdk1.7当中的一些源代码实现，更多关于jdk1.7的代码请读者自己查阅并分析，本文不过多讲述，已经快被源码绕晕了，HashMap结束准备向ConcurrentHashMap发起冲击！！！
// jdk1.7
方法一：
static int hash(int h) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode(); // 为第一步：取hashCode值
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
方法二：
static int indexFor(int h, int length) { //jdk1.7的源码，jdk1.8没有这个方法，但实现原理一样
return h & (length-1); //第三步：取模运算
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）