1 map（1.2）
1.1 分类
双列数据，存储key-value对的数据
- HashMap：map的主要实现类；1.2；线程不安全，效率高；可以存储null的key和value。底层：1.7及之前：数组+链表；1.8以后：数组+链表+红黑树
- LinkedHashMap：保证在遍历map元素时，可以按照添加的顺序实现遍历。原因：在原有的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。对于频繁的遍历操作，此类执行效率高于HashMap。
- TreeMap：保证按照添加的key-value对进行排序，实现排序遍历。考虑key的自然排序或定制排序。底层使用红黑树。
- HashTable：古老的实现类；1.0；线程安全，效率低；不能存储null的key和value
HashMap map = new HashMap();在实例化以后，底层创建了长度是16的一位数组Entry[ ] table。map.put(key, value);首先，调用hash() 计算key哈希值，此哈希值经过某种算法计算以后，得到在entry数组中的存放位置。- 如果此位置上的数据为空，此时key-value添加成功；
- 如果此位置上的数据不为空，意味着此位置上存在一个或多个数据（以链表形式存在），比较当前key和已经存在的一个或多个数据的哈希值：
- 如果key的哈希值与已经存在的数据的哈希值都不相同，此时key-value能够添加成功；
- 如果key的哈希值与某一个已经存在的哈希值相同，调用key所在类的equals方法，继续比较：
- 如果equals()返回false：此时key-value添加成功；
- 如果equals()返回的true，说明两个key是一样的，违背了key不能相同的准则，使用value去替换相同key的value值。
- 扩容问题：默认的扩容方式为扩容到原来的2倍，并将原有的数据复制过来。在超过临界值并且要存放的的位置上有数据就扩容（不再让其形成新的链表）。
- 在某个索引上添加新节点采用的是头插法。
- 数组+链表
2.1 jdk7 源码
https://www.cnblogs.com/red-code/p/6686738.html2.2 构造方法
注：jdk7中的构造方法只是验证，不会新建一个数组，只有在put方法时，才会新建数组。真正新建数组的方法是inflateTable方法（2.3.1）
带参数的构造方法：赋值和检验值是否合理。 ```java
/**
* 生成一个空HashMap，传入容量与负载因子* @param initialCapacity 初始容量* @param loadFactor 负载因子*/public HashMap(int initialCapacity, float loadFactor) {//初始容量不能小于0if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);//初始容量不能大于默认的最大容量if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;//负载因子不能小于0，且不能为“NaN”（NaN（“不是一个数字（Not a Number）”的缩写））if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);//将传入的负载因子赋值给属性this.loadFactor = loadFactor;//此时并不会创建容器，因为没有 传具体值// 没下次扩容大小/*** 此时并不会创建容器，因为没有传具体值。* 当下次传具体值的时候，才会“根据这次的初始容量”，创建一个内部数组。* 所以此次的初始容量只是作为下一次扩容（新建）的容量。*/threshold = initialCapacity;//该方法只在LinkedHashMap中有实现，主要在构造函数初始化和clone、readObject中有调用。init();}
不带参数的构造方法会调用带参数的构造方法（使用初始值）```java/*** 生成一个空hashmap，传入初始容量，负载因子使用默认值（0.75）* @param initialCapacity 初始容量*/public HashMap(int initialCapacity) {//生成空数组，并指定扩容值this(initialCapacity, DEFAULT_LOAD_FACTOR);}
2.3 hashmap中位运算的应用
2.3.1 计算初始容量
在新建（初始化）数组时进行：
/*** 新建一个空的内部数组* @param toSize 新数组容量*/private void inflateTable(int toSize) {//内部数组的大小必须是2的n次方，所以要找到“大于”toSize的“最小的2的n次方”。int capacity = roundUpToPowerOf2(toSize);// 在这里会产生新的临界值threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);table = new Entry[capacity];//根据数组长度初始化hashseedinitHashSeedAsNeeded(capacity);}
一定为2的幂次方数，1. 位置下标的与运算(计算位置下标用) 2.扩容时用
/*** 找到number的最小的2的n次方* @param number* @return*/private static int roundUpToPowerOf2(int number) {return number >= MAXIMUM_CAPACITY? MAXIMUM_CAPACITY: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;}public static int highestOneBit(int i) {// HD, Figure 3-1i |= (i >> 1);i |= (i >> 2);i |= (i >> 4);i |= (i >> 8);i |= (i >> 16);return i - (i >>> 1);}
- highestOneBit() 方法解读：找到一个不大于当前数的最大的2的幂次方数 （15结果为8、16结果为16）
以8位为例原始数据 0001 ****i |= (i >> 1);移动一位 0000 1***或操作 0001 1***i |= (i >> 2);移动两位 0000 11**或操作 0001 11**.....最后变成 0001 1111i - (i >>> 1);右移一位 0000 1111减之后得 0001 0000
- roundUpToPowerOf2计算初始容量方法解读：
Integer.highestOneBit((number - 1) << 1) ： 找到一个大于等于该number的最小的2的幂次方数。
- number-1之后扩大到原来的2倍，就可以按照扩大后的数去找不大于当前数的最大的2的幂次方数。（例如num为16 ，num-1之后为15，左移一位扩大为30，30调用highestOneBit方法为16，即找到了16）
- -1 是为了保证number本来就是2的幂次方数，如果左移扩大为2倍的话再调用该方方法得到的结果也是原来的2倍。（例如number为16，如果不-1的话左移扩大为32，32调用highestOneBit方法为32，而需要的结果为16，所以需要-1）
2.3.2 计算哈希值
增加散列次数的原因也是为了不让一个位置上的链表过长，多次散列可以使hashCode的值分布均匀，充分利用高位的值，使其参与到运算过程中而不是对结果没有影响。（因为计算数组中的位置下标只与数组长度的低位有关）
hashseed默认为0，改变方式参见2.4.2节
hash方法：
/*** 根据传入的key生成hash值* @param k 键值名* @return hash值*/final int hash(Object k) {int h = hashSeed;//如果key是字符串类型，就使用stringHash32来生成hash值if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}//一次散列h ^= k.hashCode();//二次散列h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}
2.3.3 计算在数组中的位置下标
indexFor方法
/*** 返回hash值的索引，采用除模取余法，h & (length-1)操作 等价于 hash % length操作， 但&操作性能更优*//*** 根据key的hash值与数组长度，找到该key在table数组中的下标* @param h hash值* @param length 数组长度* @return 下标*/static int indexFor(int h, int length) {//除模取余,相当于hash % length，&速度更快return h & (length-1);}
- 举例：
可以看出与2的幂次方数有关，2的幂次方数-1之后其二进制高位全是0，低位全部都是1，同这些个1进行&操作就行了，高位可以全部舍弃。长度为16，-1之后为1515: 0000 1111H : 1010 1010&操作：0000 1010结果其实就是hashcode的低4位，取值为0000-1111 （0-15）恰好长度就是16
2.4 扩容问题
2.4.1 什么时候扩容
在超过临界值并且要存放的的位置上有数据（jdk8没有）就扩容【即大于阈值，并且发生了碰撞】。扩容之后的位置坐标值在当前位置i或者是i+oldTable.length的位置（例如，hashmap数组位置为0，1，扩容之后为0，1，2，3，原先在1位置的值在扩容后有可能在1和3的位置出现，可以将其看成一半 （0，1），（1，3））
/*** 查看是否需要扩容，然后添加新节点* @param hash key的hash值* @param key 结点内key* @param value 结点内value* @param bucketIndex 结点所在的table下标*/void addEntry(int hash, K key, V value, int bucketIndex) {//如果当前键值对数量达到了临界值并且在新位置上加数据时发生了哈希碰撞，则扩容tableif ((size >= threshold) && (null != table[bucketIndex])) {//容量扩容一倍resize(2 * table.length);//由于数组扩容了，重新计算hash值hash = (null != key) ? hash(key) : 0;//重新计算存储位置bucketIndex = indexFor(hash, table.length);}//将键值对与他的hash值作为一个entry，插入table的指定下标中的链表头中createEntry(hash, key, value, bucketIndex);}
2.4.2 单线程扩容转移的过程
原来是正序，扩容之后由于是头插法会变成倒序。
*** 对数组扩容，即创建一个新数组，并将旧数组里的东西重新存入新数组* @param newCapacity 新数组容量*/void resize(int newCapacity) {Entry[] oldTable = table;int oldCapacity = oldTable.length;//如果当前数组容量已经达到最大值了，则将扩容的临界值设置为Integer.MAX_VALUE(Integer.MAX_VALUE是容量的临界点)if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return;}//创建一个扩容后的新数组Entry[] newTable = new Entry[newCapacity];//将当前数组中的键值对存入新数组transfer(newTable, initHashSeedAsNeeded(newCapacity));//用新数组替换旧数组table = newTable;//计算下一个扩容临界点threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);}
哈希种子：需要自己提供一个值（jdk.map.althashing.threshold，ALTERNATIVE_HASHING_THRESHOLD），当容量超过这个值时，哈希种子会被随机赋一个值，在计算哈希值时会提高散列性。如果不设置，默认该值就是int的最大值，容量一般不会超过这个值，即哈希种子的值为0。
//threshold的最大值static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;private static class Holder {/*** 容量阈值，初始化hashSeed的时候会用到该值*/static final int ALTERNATIVE_HASHING_THRESHOLD;static {//获取系统变量jdk.map.althashing.thresholdString altThreshold = java.security.AccessController.doPrivileged(new sun.security.action.GetPropertyAction("jdk.map.althashing.threshold"));int threshold;try {threshold = (null != altThreshold)? Integer.parseInt(altThreshold): ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;// jdk.map.althashing.threshold系统变量默认为-1，如果为-1，则将阈值设为Integer.MAX_VALUEif (threshold == -1) {threshold = Integer.MAX_VALUE;}//阈值需要为正数if (threshold < 0) {throw new IllegalArgumentException("value must be positive integer.");}} catch(IllegalArgumentException failed) {throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);}ALTERNATIVE_HASHING_THRESHOLD = threshold;}}
/*** 根据内部数组长度初始化hashseed* @param capacity 内部数组长度* @return hashSeed是否初始化*/final boolean initHashSeedAsNeeded(int capacity) {boolean currentAltHashing = hashSeed != 0;boolean useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);boolean switching = currentAltHashing ^ useAltHashing;//为true则赋初始化值，currentAltHashing为false，只有useAltHashing为true时，// switching才会为true，useAltHashing为true时需要手动设置jdk.map.althashing.threshold的值，// 那么ALTERNATIVE_HASHING_THRESHOLD就为这个值，否则为默认值，// 当前hashmap数组容量>这个值时，useAltHashing就为trueif (switching) {hashSeed = useAltHashing? sun.misc.Hashing.randomHashSeed(this): 0;}return switching;}
- 重新计算哈希值:
if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); }
如果设置jdk.map.althashing.threshold，扩容之后容量超过了这个值，那么哈希种子被改变了，rehash为true（默认为false），所以需要重新计算哈希值。主要还是为了扩容后，增加散列，使链表变短。
transfer方法，转移数据。两重循环，第一重循环的是数组，第二重循环的是每个位置上的链表。
/*** 将现有数组中的内容重新通过hash计算存入新数组* @param newTable 新数组* @param rehash*/void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;//遍历现有数组中的每一个单链表的头entryfor (Entry<K,V> e : table) {//查找链表里的每一个entrywhile(null != e) {Entry<K,V> next = e.next;if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}//根据新的数组长度，重新计算此entry所在下标iint i = indexFor(e.hash, newCapacity);// 链表的头插法//将entry放入下标i处链表的头部（将新数组此处的原有链表存入entry的next指针）e.next = newTable[i];//将链表存回下标inewTable[i] = e;//查看下一个entrye = next;}}}
扩容转移数据使用的是头插法，所以在扩容的时候原先的数据跟扩容后的数据顺序是相反的。
2.4.3 多线程在扩容时使用头插法会出现循环链表
参见这篇文章 https://mp.weixin.qq.com/s/VtIpj-uuxFj5Bf6TmTJMTw
- 线程1正常执行，扩容后数据与原来的数据是相反的，效果是这样的。
- 线程2此时开始执行，由于线程1对hashmap的操作，线程2的指向是不变的，会跟着他移动
- 线程2进行第一次扩容之后的结果
- 线程2进行第二次扩容后的结果
- 线程2进行第三次扩容后的结果
2.5 头插法（put方法）
put方法：
- 如果是第一次添加元素，初始化
- key为null，存在第0个位置
- 生成key对应的哈希值（增加散列）
- 根据哈希值找到对应的位置index
- 先判断该位置，是否有元素，没有则直接进行下一步。遍历该位置的链表，判断是否存在该key，如果存在，更新value，返回旧的value
- 否则，添加进链表中（头插法）。
inflateTable方法（参见2.3.1） hash方法（参见2.3.2）indexFor方法（参见2.3.3） 都与位运算有关
/*** 存入一个键值对，如果key重复，则更新value* @param key 键值名* @param value 键值* @return 如果存的是新key则返回null，如果覆盖了旧键值对，则返回旧value*/public V put(K key, V value) {//如果数组为空，则初始化数组if (table == EMPTY_TABLE) {inflateTable(threshold);}//如果key为null，则把value放在table[0]中if (key == null)return putForNullKey(value);//生成key所对应的hash值int hash = hash(key);//根据hash值和数组的长度找到：该key所属entry在table中的位置iint i = indexFor(hash, table.length);/*** 数组中每一项存的都是一个链表，* 先找到i位置，然后循环该位置上的每一个entry，* 如果发现存在key与传入key相等，则替换其value。然后结束该方法。* 如果没有找到相同的key，则继续执行下一条指令，将此键值对存入链表头*/for (Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;// linkedHashmap使用e.recordAccess(this);return oldValue;}}//map操作次数加一modCount++;// 没有找到相同的key，则新增// 查看是否需要扩容，并将该键值对存入指定下标的链表头中addEntry(hash, key, value, i);//如果是新存入的键值对，则返回nullreturn null;}
addEntry方法（具体内容参见2.4.1 ）：
void addEntry(int hash, K key, V value, int bucketIndex) {//如果当前键值对数量达到了临界值，或目标table下标不存在，则扩容tableif ((size >= threshold) && (null != table[bucketIndex])) {//容量扩容一倍resize(2 * table.length);//由于数组扩容了，重新计算hash值hash = (null != key) ? hash(key) : 0;//重新计算存储位置bucketIndex = indexFor(hash, table.length);}//将键值对与他的hash值作为一个entry，插入table的指定下标中的链表头中createEntry(hash, key, value, bucketIndex);}
createEntry方法（头插法）：
/*** 将键值对与他的hash值作为一个entry，插入table的指定下标中的链表头中* @param hash hash值* @param key 键值名* @param value 键值* @param bucketIndex 被插入的下标*/void createEntry(int hash, K key, V value, int bucketIndex) {// 取当前位置的头结点Entry<K,V> e = table[bucketIndex];// 新建一个节点，将新节点的next指针指向头结点e，并将新节点放在当前位置上table[bucketIndex] = new Entry<>(hash, key, value, e);size++;}
putForNullKey方法（如果key为null，则将其放在数组的0位置上）特例：
/*** 如果key为null，则将其value存入table[0]的链表中* @param value 键值* @return 如果覆盖了旧value，则返回value，否则返回null*/private V putForNullKey(V value) {//迭代table[0]中的链表里的每一个entryfor (Entry<K, V> e = table[0]; e != null; e = e.next) {//如果找到key为null的entry，则覆盖其value，并返回旧value// 0位置的链表不止存key为null的值，还要存计算出的index为0的值，因此null会在中间出现。需要遍历。if (e.key == null) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}//操作次数加一modCount++;//如果没有找到key为null的entry，则新增。//查看是否需要扩容，然后将entry插入table的指定下标中的链表头中，插入0的位置addEntry(0, null, value, 0);return null;}
2.6 modCount属性
记录hashmap的修改次数。fast-fail容错机制。
测试：
测试方法
public static void main(String[] args) {HashMap<Integer, Integer> map = new HashMap<>();map.put(1, 1);map.put(2, 2);for (Integer key : map.keySet()) {if (key.equals(1)) {map.remove(key);}}}
报错：在遍历时修改（并发）
Exception in thread "main" java.util.ConcurrentModificationExceptionat java.util.HashMap$HashIterator.nextNode(HashMap.java:1445)at java.util.HashMap$KeyIterator.next(HashMap.java:1469)at com.ll.ch3.Test111.main(Test111.java:14)
报错原因分析：看class文件
public static void main(String[] args) {HashMap<Integer, Integer> map = new HashMap();map.put(1, 1);map.put(2, 2);Iterator var2 = map.keySet().iterator();while(var2.hasNext()) {Integer key = (Integer)var2.next();if (key.equals(1)) {map.remove(key);}}}
第10行，使用的是map的remove方法，这个方法中有一个modCount++操作，会改变modCount值
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;elsep.next = node.next;++modCount;--size;afterNodeRemoval(node);return node;}
第8行执行的是hashmap的next方法 modCount与expectedModCount不相等时会抛出异常，modCount被修改了，expectedModCount没有被修改。
final Node<K,V> nextNode() {Node<K,V>[] t;Node<K,V> e = next;if (modCount != expectedModCount)throw new ConcurrentModificationException();if (e == null)throw new NoSuchElementException();if ((next = (current = e).next) == null && (t = table) != null) {do {} while (index < t.length && (next = t[index++]) == null);}return e;}
而iteratior的next方法修改了expectedModCount值，不会抛出异常（第10行）。
public final void remove() {Node<K,V> p = current;if (p == null)throw new IllegalStateException();if (modCount != expectedModCount)throw new ConcurrentModificationException();current = null;K key = p.key;removeNode(hash(key), key, null, false, false);expectedModCount = modCount;}
修改后的代码为：
public static void main(String[] args) {HashMap<Integer, Integer> map = new HashMap<>();map.put(1, 1);map.put(2, 2);Iterator var2 = map.keySet().iterator();while(var2.hasNext()) {Integer key = (Integer)var2.next();if (key.equals(1)) {var2.remove();}}}
3. ConcurrentHashmap原理（jdk7）
结构：ConcurrentHashMap的数据结构是由一个Segment数组和多个HashEntry组成，如下图所示：
ConcurrentHashMap在初始化时会要求初始化concurrencyLevel作为segment数组长度，即并发度，代表最多有多少个线程可以同时操作ConcurrentHashMap,默认是16，每个segment片段里面含有键值对HashEntry数组，是真正存放键值对的地方，这就是ConcurrentHashMap的数据结构。
3.1 构造方法
/*** ConcurrentHashMap* @param initialCapacity 初始化容量（总HashEntry容量，每一个HashEntry=initialCapacity/concurrencyLevel）* @param loadFactor 负载因子* @param concurrencyLevel 并发级别,也就是segments数组的长度*/public ConcurrentHashMap(int initialCapacity,float loadFactor, int concurrencyLevel) {if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)throw new IllegalArgumentException();if (concurrencyLevel > MAX_SEGMENTS)concurrencyLevel = MAX_SEGMENTS;// 根据concurrencyLevel计算出ssize为segments数组的长度//如果我们传入的concurrencyLevel不是2的n次幂，计算出的size是大于等于我们传入的数的2// 的幂次方数int sshift = 0;int ssize = 1;// 该方法与hashmap的中求个数的含义相同while (ssize < concurrencyLevel) {++sshift;ssize <<= 1;}this.segmentShift = 32 - sshift;this.segmentMask = ssize - 1;if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;// 计算每个segment中table的容量int c = initialCapacity / ssize;//判断如果传入initialCapacity不是2的n次幂，所做的操作相当于向上取整if (c * ssize < initialCapacity)++c;// HashEntry[]最小容量为2int cap = MIN_SEGMENT_TABLE_CAPACITY;// 保证cap是2^nwhile (cap < c)cap <<= 1;// create segments and segments[0]// 创建segments并初始化第一个segment数组,其余的segment延迟初始化，原型，// 相当于一个模板，别的segment为空时，就不用重复这些计算操作而可以直接用他的属性初始化新的segmentSegment<K,V> s0 =new Segment<K,V>(loadFactor, (int)(cap * loadFactor),(HashEntry<K,V>[])new HashEntry[cap]);Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];UNSAFE.putOrderedObject(ss, SBASE, s0); // 这里是unsafe操作，并发安全的为数组的第0个位置赋值this.segments = ss;}
3.1 HashEntry的结构
static final class HashEntry<K,V> {final int hash;final K key;volatile V value;volatile HashEntry<K,V> next;HashEntry(int hash, K key, V value, HashEntry<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}/*** Sets next field with volatile write semantics. (See above* about use of putOrderedObject.)*/final void setNext(HashEntry<K,V> n) {UNSAFE.putOrderedObject(this, nextOffset, n);}// Unsafe mechanicsstatic final sun.misc.Unsafe UNSAFE; //可以理解为一个指针static final long nextOffset;//偏移量，可以简单的理解为内存地址static {try {UNSAFE = sun.misc.Unsafe.getUnsafe();//获取这个节点对应的内存指针Class k = HashEntry.class;//nextOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("next")); //获取当前节点的next节点对于当前节点指针的偏移量//通过UNSAFE中有方法直接能够获取到当前引用变量的初始内存地址//通过初始内存地址和引用变量内部的局部变量的偏移量就可以通过Unsafe直接读取到对应的参数值} catch (Exception e) {throw new Error(e);}}}
4.HashMap底层原理（jdk 8）
与jdk7的区别：
HashMap map = new HashMap();在实例化以后，底层并没有创建一个长度为16的数组- jdk8底层的数组是：Node[ ]，并不是Entry[ ]
- 首次调用put( )方法时，底层创建长度为16的数组。
- 在某个索引上添加新节点采用的是尾插法。
- 数组+链表+红黑树。当数组的某一个索引位置上的元素以链表形式存在的数据个数>8且当前数组的长度>64时，此时此索引位置上的所有数据改为使用红黑树存储。
4.1 红黑树
有关课程可B站搜《数据结构-邓俊辉》4.1.1 红黑树的定义
- 每个节点是红色或黑色
- 根节点是黑色
- 每个叶节点是黑色（空叶子节点也算叶子节点）
- 如果一个节点是红的，则它的两个儿子都是黑的（即父子节点之间不能出现两个连续的红节点）
对每个节点，从该节点到其叶子节点的所有路径上包含相同数目的黑色节点（为满足此定义，新插入的节点一定是红色的）
4.1.2 红黑树的转换
4.1.3 插入操作
双红问题
情况1：x的叔叔节点u为黑色，重新染色即可（中间节点变黑，孩子节点变红）
- 情况2：x的叔叔节点u为红色，不满足B树条件，对应的B树发生上溢。
转换过程
结构变化为：O(1) ，红色变化为O(logN )
插入节点的所有情况分析（新插入的节点一定是红色）
情形1
新插入的节点为根节点，则直接变为黑色即可。
情形2
新节点的父节点为黑色，无需调整。
情形3
新节点的父节点为红色，叔叔节点存在且也为红色。将父节点和叔叔节点变为黑色，祖父节点变为红色即可。
情形4
新节点为父节点的右孩子，父节点为红色，叔叔节点为黑色或者为null。
①左旋。旋转父节点。就变成了情形5
②右旋。先变色，父节点和叔叔节点变黑色，祖父节点变红色。祖父节点右旋。
情形5
新节点为父节点的左孩子，父节点为红色，叔叔节点为黑色或者为null。调整规则同情形4中的第二步
4.1.4 删除操作
双黑问题
情况1
删除x节点
情况2：
- 情况3：
- 情况4：
4.1.5 HashMap中红黑树的调整代码
TreeNode结构：内部类，继承了Node结构，所以还有next，prev的属性
TreeNode<K,V> parent; // red-black tree linksTreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev; // needed to unlink next upon deletionboolean red;
1. 红黑树调整
balanceInsertion() 方法
// root为当前红黑树的根节点，x为新增节点static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,TreeNode<K,V> x) {// 新增节点默认为红节点x.red = true;// xp为x的父节点，xpp为x的祖父节点，xppl为xpp的左孩子节点（x的左叔叔节点），xppr为xpp的右孩子节点（x的右叔叔节点）for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {// 如果x的父节点为空、说明当前节点就是根节点。->L1// 那么把当前节点标为黑色，返回当前节点if ((xp = x.parent) == null) {x.red = false;return x;}// x的父节点是黑色，或者x的祖父节点为null（插入之后只有两层）->L2// 直接返回rootelse if (!xp.red || (xpp = xp.parent) == null)return root;// 如果x的父节点是祖父节点的左孩子，则祖父节点的右孩子为右叔叔节点 ->L3if (xp == (xppl = xpp.left)) {// 如果x的右叔叔节点存在且为红色 (RR-2) ->L3_1if ((xppr = xpp.right) != null && xppr.red) {xppr.red = false; // 右叔叔节点变黑xp.red = false; // 父节点变黑xpp.red = true; // 祖父节点变红x = xpp; // x变为祖父节点（祖父节点为起始节点），递归调整}else { // x的右叔叔节点为null或者为黑色 ->L3_2// 如果x为父节点的右孩子，先左旋后右旋 -> L3_2_1if (x == xp.right) {// 父节点左旋，此时x为xp节点了root = rotateLeft(root, x = xp);// 左旋过后xp与x的父子关系颠倒了，// 更换x与xp的父子关系，获取爷爷节点，如果xp节点为null，xpp也为nullxpp = (xp = x.parent) == null ? null : xp.parent;}// 如果xp节点不为空，直接右旋 -> L3_2_2if (xp != null) {xp.red = false; // 父节点变为黑色if (xpp != null) { // 爷爷节点不为空xpp.red = true; // 爷爷节点变红色，root = rotateRight(root, xpp); // 爷爷节点右旋}}}}else { // 如果x的父节点是祖父节点的右孩子 ->L4，过程基本与L3一样// 如果x的左叔叔节点存在空且是红色 ->L4_1if (xppl != null && xppl.red) {xppl.red = false; // 左叔叔节点变黑xp.red = false; // 父节点变黑xpp.red = true; // 祖父节点变红x = xpp; // x变为祖父节点（祖父节点为起始节点），递归调整}else { // 如果x的左叔叔为null或者是黑色 -> L4_2// 如果x节点是父节点xp的左孩子，先右旋后左旋 ->L4_2_1if (x == xp.left) {// 父节点右旋，此时x为xp节点了root = rotateRight(root, x = xp);// 右旋过后xp与x的父子关系颠倒了，// 更换x与xp的父子关系，获取爷爷节点，如果xp节点为null，xpp也为nullxpp = (xp = x.parent) == null ? null : xp.parent;}// 如果xp节点不为空，直接左旋 -> L4_2_2if (xp != null) {xp.red = false; // 父节点变为黑色if (xpp != null) { // 爷爷节点不为空xpp.red = true; // 爷爷节点变红色，root = rotateLeft(root, xpp); // 爷爷节点右旋}}}}}}
- 无旋转 L3_1 L4_1 L1
- L3_2_1 与 L3_2_2的变化
- L4_2_1与L4_2_2
2 左旋
左旋代码 ```java x节点与x的父节点xp交换位置，即xp为左孩子节点，x为父节点 root 根节点，p为x的父节点。 static
TreeNode<K,V> p) {
TreeNode
if ((rl = p.right = r.left) != null) // 要左旋的节点p的右孩子r的左节点rl不为null， 将其赋给 要左旋的节点p的右孩子 节点为：rlrl.parent = p; // 设置rl和要左旋的节点p的父子关系【之前只是爹认了孩子，孩子还没有答应，这一步孩子也认了爹】// 将要左旋的节点p的右孩子l的父节点 指向 要左旋的节点的父节点，相当于右孩子提升了一层，// 此时如果父节点为空， 说明r 已经是顶层节点了，应该作为root 并且标为黑色if ((pp = r.parent = p.parent) == null)(root = r).red = false;else if (pp.left == p) // 如果父节点pp不为空 并且 要左旋的节点p是个左孩子pp.left = r; // 设置r和父节点的父子关系【之前只是孩子认了爹，爹还没有答应，这一步爹也认了孩子】else // 要左旋的节点是个右孩子pp.right = r;r.left = p; // 要左旋的节点 作为 他的右孩子的左节点p.parent = r; // 要左旋的节点的右孩子 作为 他的父节点
} return root; // 返回根节点 }
- 第一种情况，p为pp的左孩子- 第二种情况，16行p为pp的右孩子<a name="V6p9l"></a>#### 3 右旋```javax节点与x的父节点xp交换位置，即xp为左孩子节点，x为父节点root 根节点，p为x的父节点。static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,TreeNode<K,V> p) {TreeNode<K,V> l, pp, lr;if (p != null && (l = p.left) != null) { // 要右旋的节点不为空以及要右旋的节点的左孩子不为空if ((lr = p.left = l.right) != null) // 要右旋的节点的左孩子的右节点 赋给 要右旋节点的左孩子 节点为：lrlr.parent = p; // 设置lr和要右旋的节点的父子关系【之前只是爹认了孩子，孩子还没有答应，这一步孩子也认了爹】// 将要右旋的节点的左孩子的父节点 指向 要右旋的节点的父节点，相当于左孩子提升了一层，// 此时如果父节点为空， 说明l 已经是顶层节点了，应该作为root 并且标为黑色if ((pp = l.parent = p.parent) == null)(root = l).red = false;else if (pp.right == p) // 如果父节点不为空 并且 要右旋的节点是个右孩子pp.right = l; // 设置l和父节点的父子关系【之前只是孩子认了爹，爹还没有答应，这一步爹也认了孩子】else // 要右旋的节点是个左孩子pp.left = l; // 同上l.right = p; // 要右旋的节点 作为 他左孩子的右节点p.parent = l; // 要右旋的节点的父节点 指向 他的左孩子}return root;}
4.2 Node结构及相关参数
4.2.1 Node结构
static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;//...省略}
4.2.2 相关参数
常量
// 默认table大小：16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;// 数组最大容量static final int MAXIMUM_CAPACITY = 1 << 30;// 默认负载因子，默认0.75，平衡空间开销和查找成本。过大容易发生哈希碰撞降低速度，过低容易引起频繁扩容，浪费空间static final float DEFAULT_LOAD_FACTOR = 0.75f;// 树化链表个数阈值 8，符合泊松分布static final int TREEIFY_THRESHOLD = 8;// 树降级成为链表的阈值 6static final int UNTREEIFY_THRESHOLD = 6;// 树化数组长度阈值64static final int MIN_TREEIFY_CAPACITY = 64;
属性
// 哈希表transient Node<K,V>[] table;// 当前哈希表的元素（键值对）个数transient int size;// 当前哈希表的结构修改次数transient int modCount;// 扩容阈值int threshold;// 负载因子final float loadFactor;
4.3 构造方法
public HashMap(int initialCapacity, float loadFactor) {// 参数校验if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;// 找一个大于等于当前数组容量的最小的2的次方数this.threshold = tableSizeFor(initialCapacity);}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);}
static final int tableSizeFor(int cap) {int n = cap - 1;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;}
4.4 put方法
put方法
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}
putVal方法
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;// tab为null 或者长度为0，调用resize方法。创建数组表。延迟初始化。// 第一次调用put方法会初始化hashmap对象的散列表，防止浪费内存if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 如果当前数组位置为null，就创建一个节点放进去，没有发生碰撞if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {// 这个位置不是null，发生碰撞了// e:临时node元素 k：表示临时的keyNode<K,V> e; K k;// 如果当前位置的第一个节点与新节点的哈希值相等，key也相等，则后续会覆盖当前位置的该节点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 { // 不是覆盖操作，则插入一个普通链表节点，// binCount是当前链表的长度，如果为8，转化为红黑树for (int binCount = 0; ; ++binCount) {// 没找到这个值if ((e = p.next) == null) {// 就加新节点进去，尾插法p.next = newNode(hash, key, value, null);// 临界值binCount为7（从0开始计算）// 因为是先插入后判断，当第9个节点插入后，binCount为7，转换为红黑树if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}// 在链表上找到这个值了，就中断，进行修改if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;// 节点下移p = e;}}// 如果e不是null，说明找到了节点有需要覆盖的节点，修改if (e != null) { // existing mapping for key//则覆盖节点值，并返回原oldValueV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}// 散列表修改结构的次数+1++modCount;// 如果size自增过后的值>扩容阈值，则进行扩容if (++size > threshold)// 扩容resize();afterNodeInsertion(evict);return null;}
4.4.1 计算hash值
与 jdk7中的hash方法(2.3.2) 不一样，简化了。因为加了红黑树，就不用那么复杂了。
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
4.4.2 treeifyBin()方法
将单向链表改成双向链表（4.3扩容时操作链表更方便），并构建红黑树。
final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;// 如果数组为null，或者数组长度<MIN_TREEIFY_CAPACIT(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节点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);}}
replacementTreeNode方法
将hashmap的node节点，转换为红黑树的TreeNode节点。
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {return new TreeNode<>(p.hash, p.key, p.value, next);}
treeify方法
构建红黑树
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;// 从根节点开始找要插入的节点的位置，BST思想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;// 如果hash相等，看key所在的类是否实现了Comparable接口，如果实现了，再用Comparable比较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;elsexp.right = x;// 红黑树平衡调整root = balanceInsertion(root, x);break;}}}}// 把树的根移到那个位置上moveRootToFront(tab, root);}
tieBreakOrder方法
static int tieBreakOrder(Object a, Object b) {int d;if (a == null || b == null ||(d = a.getClass().getName().compareTo(b.getClass().getName())) == 0)d = (System.identityHashCode(a) <= System.identityHashCode(b) ?-1 : 1);return d;}
moveRootToFront方法
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {int n;if (root != null && tab != null && (n = tab.length) > 0) {int index = (n - 1) & root.hash;TreeNode<K,V> first = (TreeNode<K,V>)tab[index];if (root != first) {Node<K,V> rn;// 将根节点放到那个位置上tab[index] = root;// 找到双向链表中根节点的位置放到头节点上TreeNode<K,V> rp = root.prev;if ((rn = root.next) != null)((TreeNode<K,V>)rn).prev = rp;if (rp != null)rp.next = rn;if (first != null)first.prev = root;root.next = first;root.prev = null;}assert checkInvariants(root);}}
红黑树插入位置的比较过程
hash()
- key所在的类实现了Comparable接口的CompareTo()
- getClass().getName()
System.identityHashCode() 获取该对象没有被重写的hash值
4.5 扩容
与1.7不同，8中的扩容仅仅是大于阈值即可，7中还有一个发生哈希碰撞的条件。
if (++size > threshold)// 扩容resize();
4.5.1 扩容方法
```java final Node
Node<K,V>[] oldTab = table;// oldCap 扩容之前哈希表的数组长度int oldCap = (oldTab == null) ? 0 : oldTab.length;// 扩容之前的阈值int oldThr = threshold;// 扩容之后的数组大小和阈值大小int newCap, newThr = 0;// 给扩容后的两个变量赋值// hashmap已经初始化过了，正常扩容if (oldCap > 0) {// 达到最大值，赋给Integer最大值if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}// 否则，正常扩容// 老容量翻倍之后依然小于最大值 且老容量>=16，则容量翻倍，扩容阈值也翻倍。// 注意此时如果不满足这个条件也不会给newThr赋值（情况1）else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}// oldCap = 0,散列表没有初始化// 1.new HashMap(initCap, loadFactory)// 2.new HashMap(initCap)// 3.new HashMap(map) 且map有数据else if (oldThr > 0) // initial capacity was placed in threshold// 第一次初始化将 老阈值 赋给 新容量。注意此时并没有给newThr赋值（情况2）newCap = oldThr;else {// zero initial threshold signifies using defaults// oldCap oldThr全部都为0，赋默认值// new HashMap();newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 上面有两种情况会导致newThr为0if (newThr == 0) {// 为newThr赋值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];table = newTab;// 扩容部分if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {// 置空，方便jvm回收，释放内存oldTab[j] = null;if (e.next == null)// 单个节点扩容，重新计算位置即可newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)// 红黑树扩容((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // 链表扩容// 将原先的一个链表拆成两个链表// 一部分放重新计算index为0的节点 lo 当前位置// 一部分放重新计算不为0的节点 hi 当前位置+老数组长度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;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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;
}
<a name="OrtbP"></a>#### 链表扩容链表扩容部分与1.7不同，第40行到58行。将原先数组上的一个链表拆分成两个链表，挨个计算e的哈希值与老数组容量的与运算，结果为0表示低位部分loHead，连接到lo链表中；结果不为0表示高位部分hiHead，连接到hi链表中。之后lo链表重新放到到新数组中的原来的index位置，hi链表重新放到新数组中index+oldCap的位置。<a name="zWdBS"></a>#### 红黑树扩容（split方法）红黑树部分含有一个双向链表（树化过程之前会将其变成双向链表），也是将一个链表拆成两个链表(要记录两个链表的个数)。低位放到原先的index位置，高位放到index+oldCap位置。同时判断两个新链表的个数是否达到_UNTREEIFY_THRESHOLD=6_，如果是6则退化成链表（Node类型，单向链表）；否则，判断是否需要树化，如果低位链表存在而高位链表不存在（高位存在地位不存在），那还是原来的那棵树直接移走就行了不用树化，否则需要树化。```javafinal 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 orderTreeNode<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;elseloTail.next = e;loTail = e;// 记录个数++lc;}else {if ((e.prev = hiTail) == null)hiHead = e;elsehiTail.next = e;hiTail = e;++hc;}}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);}}}
4.6 Get方法
final Node<K,V> getNode(int hash, Object key) {// tab 引用当前hashmap的散列表// first 数组中的头元素// n 数组长度// k keyNode<K,V>[] tab; Node<K,V> first, e; int n; K k;// 数组当前位置不为空才去getif ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {// 只有一个节点比较值if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return 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;}
红黑树的查找方法
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {TreeNode<K,V> p = this;do {int ph, dir; K pk;TreeNode<K,V> pl = p.left, pr = p.right, q;if ((ph = p.hash) > h)p = pl;else if (ph < h)p = pr;else if ((pk = p.key) == k || (k != null && k.equals(pk)))return p;else if (pl == null)p = pr;else if (pr == null)p = pl;else if ((kc != null ||(kc = comparableClassFor(k)) != null) &&(dir = compareComparables(kc, k, pk)) != 0)p = (dir < 0) ? pl : pr;else if ((q = pr.find(h, k, kc)) != null)return q;elsep = pl;} while (p != null);return null;}
4.7 remove方法
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);}}// node不为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;}
红黑树删除
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,boolean movable) {int n;if (tab == null || (n = tab.length) == 0)return;int index = (n - 1) & hash;TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;if (pred == null)tab[index] = first = succ;elsepred.next = succ;if (succ != null)succ.prev = pred;if (first == null)return;if (root.parent != null)root = root.root();// 这里并没有采用与常量比较的方式，而是判断节点存不存在6个，提高性能if (root == null|| (movable&& (root.right == null|| (rl = root.left) == null|| rl.left == null))) {tab[index] = first.untreeify(map); // too smallreturn;}TreeNode<K,V> p = this, pl = left, pr = right, replacement;if (pl != null && pr != null) {TreeNode<K,V> s = pr, sl;while ((sl = s.left) != null) // find successors = sl;boolean c = s.red; s.red = p.red; p.red = c; // swap colorsTreeNode<K,V> sr = s.right;TreeNode<K,V> pp = p.parent;if (s == pr) { // p was s's direct parentp.parent = s;s.right = p;}else {TreeNode<K,V> sp = s.parent;if ((p.parent = sp) != null) {if (s == sp.left)sp.left = p;elsesp.right = p;}if ((s.right = pr) != null)pr.parent = s;}p.left = null;if ((p.right = sr) != null)sr.parent = p;if ((s.left = pl) != null)pl.parent = s;if ((s.parent = pp) == null)root = s;else if (p == pp.left)pp.left = s;elsepp.right = s;if (sr != null)replacement = sr;elsereplacement = p;}else if (pl != null)replacement = pl;else if (pr != null)replacement = pr;elsereplacement = p;if (replacement != p) {TreeNode<K,V> pp = replacement.parent = p.parent;if (pp == null)root = replacement;else if (p == pp.left)pp.left = replacement;elsepp.right = replacement;p.left = p.right = p.parent = null;}TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);if (replacement == p) { // detachTreeNode<K,V> pp = p.parent;p.parent = null;if (pp != null) {if (p == pp.left)pp.left = null;else if (p == pp.right)pp.right = null;}}if (movable)moveRootToFront(tab, r);}
若有收获，就点个赞吧
0 人点赞
