提供做网站企业,阿里云4核8g云服务器多少钱,淄博网站营销与推广,优质高等职业院校建设申报网站目录 HashMap1、HashMap的继承体系2、HashMap底层数据结构3、HashMap的构造函数①、无参构造②、有参构造1 和 有参构造2 (可以自定义初始容量和负载因子)③、有参构造3(接受一个Map参数)JDK 8之前版本的哈希方法#xff1a;JDK 8版本的哈希方法 4、拉链法解决哈希冲突什么是拉… 目录 HashMap1、HashMap的继承体系2、HashMap底层数据结构3、HashMap的构造函数①、无参构造②、有参构造1 和 有参构造2 (可以自定义初始容量和负载因子)③、有参构造3(接受一个Map参数)JDK 8之前版本的哈希方法JDK 8版本的哈希方法 4、拉链法解决哈希冲突什么是拉链法动画演示拉链法解决哈希冲突拉链法有哪些好处 还有其他解决哈希冲突的方式吗 5、HashMap的put方法HashMap的属性注释put方法putVal方法putTreeVal方法treeifyBin 方法NodeK,V静态内部类resize方法split方法afterNodeAccess方法afterNodeInsertion方法HashMap的put方法执行流程图示 6、HashMap如何计算key的索引位置为什么HashMap的容量设计成总是2的整数倍 7、HashMap的get方法8、HashMap的remove方法9、HashMap的迭代器10、HashMap的一些常见问题①、JDK8为什么引入红黑树②、红黑树的数据结构有什么特点 ③、负载因子为什么是0.75④、为什么数组长度≥64且链表长度 ≥8才树化⑤、多线程下HashMap写操作可能出现哪些问题JDK1.8之前并发扩容死链问题动画演示丢失数据问题代码演示 ⑥、JDK8之前的put方法和之后的put方法有什么区别 ⑦、HashMap的红黑树什么情况下会退化成链表 HashMap
基于JDK8。 HashMap在我们的日常开发中是十分常用的键值对集合,我们来深入探究下HashMap的设计。
1、HashMap的继承体系
public class HashMapK,V extends AbstractMapK,Vimplements MapK,V, Cloneable, Serializable2、HashMap底层数据结构
这里先把答案给出。 稍后再去探究为什么使用链表处理哈希冲突JDK8为什么引入红黑树红黑树的数据结构有什么特点为什么会用64, 8, 6这几个数字作为阈值为什么元素个数达到容量的0.75倍时就扩容
JDK8之前 是数组 链表 。
JDK8 是数组 链表|红黑树。
链表的主要目的是解决哈希冲突hash collision问题。
JDK8的HashMap链表转换为红黑树的条件 链表长度 8 数组容量 64
红黑树转换回链表的条件 红黑树节点数 6
3、HashMap的构造函数
①、无参构造
// 加载因子用于控制哈希表的扩容频率
final float loadFactor;// 默认的加载因子
static final float DEFAULT_LOAD_FACTOR 0.75f;
public HashMap() {// 使用默认的加载因子this.loadFactor DEFAULT_LOAD_FACTOR; // all other fields defaulted}②、有参构造1 和 有参构造2 (可以自定义初始容量和负载因子)
// 加载因子用于控制哈希表的扩容频率
final float loadFactor;// 默认的加载因子
static final float DEFAULT_LOAD_FACTOR 0.75f;// 哈希表的最大容量 2的30次方 1,073,741,824 10亿多
static final int MAXIMUM_CAPACITY 1 30;// 扩容阈值当哈希表中元素个数超过这个值时会触发扩容
int threshold;/*** 有参构造函数1只接受初始容量参数* param initialCapacity 初始容量*/
public HashMap(int initialCapacity) {// 调用另一个构造函数使用默认加载因子this(initialCapacity, DEFAULT_LOAD_FACTOR);
}/*** 有参构造函数2接受初始容量和加载因子参数* param initialCapacity 初始容量* param loadFactor 加载因子*/
public HashMap(int initialCapacity, float loadFactor) {// 检查初始容量是否为负数如果是负数抛出非法参数异常if (initialCapacity 0)throw new IllegalArgumentException(Illegal initial capacity: initialCapacity);// 如果初始容量超过最大容量则将初始容量设置为最大容量if (initialCapacity MAXIMUM_CAPACITY)initialCapacity MAXIMUM_CAPACITY;// 检查加载因子是否有效如果小于等于0或不是一个有效数字则抛出非法参数异常if (loadFactor 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException(Illegal load factor: loadFactor);// 设置实例的加载因子this.loadFactor loadFactor;// 根据初始容量计算扩容阈值this.threshold tableSizeFor(initialCapacity);
}/*** 计算大于等于给定容量的最小2的幂次方值* param cap 给定的容量值* return 大于等于cap的最小2的幂次方值*/
static final int tableSizeFor(int cap) {int n cap - 1;// 将所有位置为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;
}
这里再抛一个问题为什么我们传自定义大小的容量HashMap要调用tableSizeFor方法取大于等于自定义容量的最小2的幂次方值。 比如我们传入35tableSizeFor计算得出36 HashMap就使用36作为容量。这个问题也在后面进行探究。
③、有参构造3(接受一个Map参数)
这个构造方法就比较复杂了涉及添加元素和扩容等操作暂时就不展开了后面单独去看添加元素和扩容操作。
// 加载因子用于控制哈希表的扩容频率
final float loadFactor;// 默认的加载因子
static final float DEFAULT_LOAD_FACTOR 0.75f;// 哈希表的最大容量2的30次方即1,073,741,82410亿多
static final int MAXIMUM_CAPACITY 1 30;// 哈希表的底层数组存储键值对
transient NodeK,V[] table;// 扩容阈值当哈希表中元素个数超过这个值时会触发扩容
int threshold;/*** 有参构造函数3接受一个Map参数* param m 初始化时用的Map*/
public HashMap(Map? extends K, ? extends V m) {// 使用默认加载因子this.loadFactor DEFAULT_LOAD_FACTOR;// 将传入的Map中的所有元素添加到当前HashMap中putMapEntries(m, false);
}/*** 将指定的Map中的所有元素添加到当前HashMap中* param m 指定的Map* param evict 是否驱逐旧元素此参数在其他上下文中使用这里传入false*/
final void putMapEntries(Map? extends K, ? extends V m, boolean evict) {// 获取指定Map的大小int s m.size();if (s 0) {// 如果当前哈希表还未初始化即底层数组为空if (table null) { // 预先调整大小// 计算预期的扩容阈值公式为(指定Map的大小 / 加载因子) 1float ft ((float)s / loadFactor) 1.0F;// 如果计算结果小于最大容量则取计算结果否则取最大容量int t ((ft (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);// 如果计算结果大于当前的扩容阈值则更新扩容阈值if (t threshold)threshold tableSizeFor(t);}// 如果当前哈希表已初始化并且指定Map的大小超过了当前的扩容阈值else if (s threshold)// 扩容哈希表resize();// 将指定Map中的每个键值对添加到当前哈希表中for (Map.Entry? extends K, ? extends V e : m.entrySet()) {K key e.getKey();V value e.getValue();// 使用putVal方法添加键值对putVal(hash(key), key, value, false, evict);}}
}/*** 计算给定键的哈希值* param key 给定的键* return 哈希值*/
final int hash(Object key) {int h;// 计算哈希值并进行哈希扰动增加哈希分布的随机性return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
}
可以看到这里的final int hash(Object key)方法是对键的hashCode进行二次hash的方法。
JDK 8之前版本的哈希方法
static int hash(int h) {h ^ (h 20) ^ (h 12);return h ^ (h 7) ^ (h 4);
}JDK 7的hash方法通过异或操作 (^) 和右移操作 () 对原始哈希码进行扰动以减少冲突。
JDK 8版本的哈希方法
/*** 计算给定键的哈希值* param key 给定的键* return 哈希值*/
final int hash(Object key) {int h;// 计算哈希值并进行哈希扰动增加哈希分布的随机性return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
}
JDK 8 通过将哈希码右移16位并与原始哈希码异或 (h key.hashCode() ^ (key.hashCode() 16)) 来扰动哈希码提高哈希分布的随机性。
JDK 8的扰动方式计算步骤更简单高效有助于减少哈希冲突提高哈希表的性能。
4、拉链法解决哈希冲突
什么是拉链法
拉链法就是数组和链表结合每个数组的元素存储的是一个链表或在JDK 8中链表长度超过一定阈值时使用红黑树。当发生哈希冲突时只需要将新的元素插入链表或树中。 上图中a,c,d元素由于哈希冲突就组成了一个链表当我们查找d时先计算出下标index是1发现链表的头是a不是d就继续向下遍历链表直到找到d为止。
动画演示拉链法解决哈希冲突 拉链法有哪些好处 还有其他解决哈希冲突的方式吗
拉链法解决哈希冲突的优点 ①.简单高效拉链法实现起来相对简单每个数组元素存储的是一个链表。当发生哈希冲突时只需要将新的元素插入链表中插入和查找操作的平均时间复杂度较低。 ②、空间利用率高拉链法在冲突发生时不需要额外的数组空间只需在链表中插入新节点节省空间。 ③、动态扩展JDK8使用的链表和红黑树都能动态地扩展不需要预先分配大量内存并且在元素很多时可以通过扩容数组(哈希表)来降低每个链表的长度维持高效的查找性能。 ④、易于实现的扩容机制在拉链法中扩容只需重新分配一个更大的数组然后重新哈希现有的元素。这一过程较为简单(实际上JDK通过特殊的手段让重新计算扩容后的元素位置变得简单这个手段就是数组(哈希表)的容量永远都是2的整数倍)不需要处理复杂的元素迁移问题。
其他解决哈希冲突的方式(了解下)
再哈希法Rehashing 使用不同的哈希函数重新计算发生冲突的元素的位置。再哈希法会在原哈希函数发生冲突时使用一个新的哈希函数重新计算索引,需要再次计算哈希值性能较低特别是多次哈希冲突的情况下。
Cuckoo Hashing布谷鸟哈希 使用两个或更多的哈希函数和两个或更多的哈希表。当一个位置发生冲突时将现有元素移到它的另一个可能位置类似于布谷鸟在鸟巢中下蛋如果新位置也有冲突则继续迁移直到找到一个空位或达到迁移限制。
开放地址法Open Addressing
线性探测Linear Probing当发生冲突时按固定步长通常为1向前探测下一个位置直到找到一个空位或回到原位置。二次探测Quadratic Probing探测步长按平方序列增长如1, 4, 9, 16…以减少聚集效应。双重散列Double Hashing使用两个不同的哈希函数当第一个哈希函数发生冲突时用第二个哈希函数计算探测步长。
线性散列法Linear Hashing 一种动态哈希方法通过渐进式地扩展哈希表来处理冲突。在需要扩展时不是一次性重新分配整个哈希表而是渐进地调整部分元素的位置。
Hopscotch Hashing跳跃哈希 结合开放地址法和链表法的优点。当冲突发生时在一定范围内探测并交换元素使得链表的元素能保持接近原位置减少查找路径长度。
5、HashMap的put方法
涉及到扩容、树化、反树化等操作
HashMap的属性注释
HashMap的属性太多了每次都在方法上面加上一些类的属性比较麻烦这里把所有的属性都注释下。
public class HashMapK,V extends AbstractMapK,Vimplements MapK,V, Cloneable, Serializable { // 默认初始容量即2的4次方即哈希表的默认大小为16static final int DEFAULT_INITIAL_CAPACITY 1 4;// 哈希表的最大容量即2的30次方即1073741824static final int MAXIMUM_CAPACITY 1 30;// 默认的加载因子即哈希表的装填因子默认为0.75static final float DEFAULT_LOAD_FACTOR 0.75f;// 树化阈值当链表长度 8且 容量64时链表转为红黑树static final int TREEIFY_THRESHOLD 8;// 反树化阈值当红黑树节点数量小于等于6时红黑树转为链表static final int UNTREEIFY_THRESHOLD 6;// 最小树化容量即哈希表的最小容量为64时链表可以转为红黑树static final int MIN_TREEIFY_CAPACITY 64;// 哈希表的底层数组存储键值对也就是HashMap底层的数组类型是NodeK,V transient NodeK,V[] table;// 键值对集合的视图用于遍历哈希表中的所有键值对transient SetMap.EntryK,V entrySet;// 哈希表中元素的数量transient int size;// 哈希表结构修改的次数用于迭代器快速失败机制transient int modCount;// 哈希表扩容阈值当哈希表中元素个数超过这个值时会触发扩容int threshold;// 加载因子用于控制哈希表的扩容频率final float loadFactor;}
put方法
public V put(K key, V value) {// 调用putVal方法将键值对插入到哈希表中return putVal(hash(key), key, value, false, true);
}
putVal方法
boolean evict,该参数指示当前的操作是否在创建模式下。如果为 false表示哈希表处于创建模式如果为 true表示哈希表处于正常操作模式。此参数通常在调整哈希表大小时使用以避免在创建模式中触发删除操作。
evict 参数为 false 的情况 在哈希表初始化或扩容时通过 putMapEntries 方法调用 putVal设置 evict 为 false。
evict 参数为 true 的情况 正常操作非创建模式下插入或更新元素时evict 为 true允许执行淘汰策略。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {NodeK,V[] tab; // 哈希表(数组)NodeK,V p; // 当前处理的节点int n, i; // n为表的长度i为计算出的索引// 如果哈希表为空或哈希表的长度为0则进行扩容操作if ((tab table) null || (n tab.length) 0)n (tab resize()).length;// 计算哈希值对应的索引如果该索引处没有节点则创建新节点if ((p tab[i (n - 1) hash]) null)tab[i] newNode(hash, key, value, null);else {NodeK,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 ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);else {// 如果当前节点不是树节点 遍历链表进行插入操作for (int binCount 0; ; binCount) {if ((e p.next) null) {// 如果当前节点的下一个节点为空表示到达链表末端p.next newNode(hash, key, value, null); // 在链表末尾插入新的节点// 如果链表长度超过树化阈值 8 则 调用treeifyBin // 在 treeifyBin 中会判断 哈希表容量是否 64 如果 哈希表容量64 则树化否则先扩容 // 注意 binCount 从 0 开始计数表示遍历链表时访问的节点数但插入新节点时实际的节点总数是 binCount 1// TREEIFY_THRESHOLD - 1 8-1 7 所以binCount7时 节点总数是 8 正好达到了阈值if (binCount TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash);break;}// 如果找到哈希值相同并且键相同的节点if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break; // 结束循环// 移动到链表的下一个节点,继续下一次循环p e; }}// 如果找到了相同的键则更新值if (e ! null) {V oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;// 插入后进行后续处理 可以给HashMap的子类做扩展 afterNodeAccess(e);return oldValue;}}// 增加修改次数modCount;// 如果当前元素个数超过阈值则进行扩容操作if (size threshold)resize();// 插入后进行后续处理 可以给HashMap的子类做扩展 afterNodeInsertion(evict);return null;
}putTreeVal方法
添加红黑树节点
// 在红黑树中插入一个新的节点或者返回已存在的节点
final TreeNodeK,V putTreeVal(HashMapK,V map, NodeK,V[] tab,int h, K k, V v) {// kc是用于比较的类Class? kc null;// searched表示是否已经搜索过树boolean searched false;// 如果当前节点有父节点则获取树的根节点否则使用当前节点TreeNodeK,V root (parent ! null) ? root() : this;// 从根节点开始遍历树for (TreeNodeK,V p root;;) {// dir表示比较方向ph是当前节点的哈希值pk是当前节点的键int dir, ph; K pk;// 如果当前节点的哈希值大于待插入节点的哈希值dir设为-1左子树if ((ph p.hash) h)dir -1;// 如果当前节点的哈希值小于待插入节点的哈希值dir设为1右子树else if (ph h)dir 1;// 如果当前节点的哈希值等于待插入节点的哈希值比较键else if ((pk p.key) k || (k ! null k.equals(pk)))// 键相同返回当前节点return p;// 如果kc为null尝试获取k的可比较类else if ((kc null (kc comparableClassFor(k)) null) ||// 使用可比较类比较键结果为0表示键相同(dir compareComparables(kc, k, pk)) 0) {// 如果还没有搜索过子树if (!searched) {TreeNodeK,V q, ch;// 标记为已搜索searched true;// 在左子树和右子树中查找if (((ch p.left) ! null (q ch.find(h, k, kc)) ! null) ||((ch p.right) ! null (q ch.find(h, k, kc)) ! null))// 找到节点则返回return q;}// 使用tie-break规则决定插入方向dir tieBreakOrder(k, pk);}// 保存当前节点为xpTreeNodeK,V xp p;// 根据dir决定向左还是向右if ((p (dir 0) ? p.left : p.right) null) {// 创建一个新节点NodeK,V xpn xp.next;TreeNodeK,V x map.newTreeNode(h, k, v, xpn);// 插入到左子树或者右子树if (dir 0)xp.left x;elsexp.right x;// 更新链表结构xp.next x;x.parent x.prev xp;if (xpn ! null)((TreeNodeK,V)xpn).prev x;// 平衡树并将根节点移动到数组前端moveRootToFront(tab, balanceInsertion(root, x));// 返回null表示插入成功return null;}}
}treeifyBin 方法
将哈希桶中的链表转换为红黑树
final void treeifyBin(NodeK,V[] tab, int hash) {int n, index; NodeK,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) {// 如果计算出的索引处的桶不为空则进行树化操作// 初始化树节点列表的头和尾TreeNodeK,V hd null, tl null;do {// 将当前链表节点转换为树节点TreeNodeK,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);}
}
NodeK,V静态内部类
HashMap的数组中保存的就是NodeK,V
static class NodeK,V implements Map.EntryK,V {final int hash; // 键的哈希值final K key; // 键V value; // 值NodeK,V next; // 指向下一个节点 这里可以看出 是单向链表结构Node(int hash, K key, V value, NodeK,V next) {this.hash hash;this.key key;this.value value;this.next next;}
}
resize方法
扩容方法
final NodeK,V[] resize() {NodeK,V[] oldTab table; // 获取当前哈希表int oldCap (oldTab null) ? 0 : oldTab.length; // 获取当前哈希表的容量如果为空则为0int oldThr threshold; // 获取当前的扩容阈值int newCap, newThr 0; // 声明新的容量和新的扩容阈值// 如果当前哈希表的容量大于0if (oldCap 0) {// 如果当前容量已经达到最大值则将扩容阈值设为最大整数值并返回当前表if (oldCap MAXIMUM_CAPACITY) {threshold Integer.MAX_VALUE; // 将阈值设为最大整数值return oldTab; // 返回当前表}// 如果当前容量未达到最大值else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)newThr oldThr 1; // 将容量和扩容阈值翻倍}// 如果当前容量为0但扩容阈值大于0即初始化时的情况else if (oldThr 0) // initial capacity was placed in thresholdnewCap oldThr; // 将新容量设为当前的阈值else { // 否则使用默认初始值newCap DEFAULT_INITIAL_CAPACITY; // 使用默认初始容量newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 根据默认负载因子和默认初始容量计算新的扩容阈值}// 如果新的扩容阈值为0根据负载因子和新容量计算新的扩容阈值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})NodeK,V[] newTab (NodeK,V[])new Node[newCap]; // 创建新的哈希表table newTab; // 更新哈希表引用// 如果旧表不为空将旧表中的元素重新散列到新表中if (oldTab ! null) {for (int j 0; j oldCap; j) { // 遍历旧表NodeK,V e;if ((e oldTab[j]) ! null) { // 如果旧表的当前桶不为空oldTab[j] null; // 释放旧表的当前桶if (e.next null) // 如果桶中只有一个节点newTab[e.hash (newCap - 1)] e; // 重新计算索引并放入新表else if (e instanceof TreeNode) // 如果桶中是红黑树节点((TreeNodeK,V)e).split(this, newTab, j, oldCap); // 拆分红黑树else { // 否则是链表节点NodeK,V loHead null, loTail null; // 定义低位链表的头尾节点NodeK,V hiHead null, hiTail null; // 定义高位链表的头尾节点NodeK,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; // 返回新的哈希表
}
split方法
split 方法用于在哈希表扩容时重新分配红黑树节点到新的哈希表桶中。 在拆分过程中原桶中的红黑树节点被分配到两个链表中。 低位链表和高位链表分别表示原桶和新桶中的元素。 这是为了保证新哈希表的负载均匀性并且避免在扩容过程中造成哈希冲突过多。
final void split(HashMapK,V map, NodeK,V[] tab, int index, int bit) {TreeNodeK,V b this; // 当前树节点// 初始化低位和高位链表的头尾节点TreeNodeK,V loHead null, loTail null;TreeNodeK,V hiHead null, hiTail null;int lc 0, hc 0; // 低位和高位链表的节点计数// 遍历当前树节点的所有节点for (TreeNodeK,V e b, next; e ! null; e next) {next (TreeNodeK,V)e.next; // 暂存下一个节点e.next null; // 断开当前节点的 next 引用// 根据 bit 的值决定节点放入低位链表还是高位链表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) // 如果高位链表不为空说明原来是红黑树结构loHead.treeify(tab); // 将低位链表重新组织为红黑树结构}}// 如果高位链表不为空if (hiHead ! null) {// 如果高位链表的节点数小于等于阈值 默认是6转换为链表结构if (hc UNTREEIFY_THRESHOLD)tab[index bit] hiHead.untreeify(map); // 将高位链表转换为普通链表并放入新表else {tab[index bit] hiHead; // 否则直接将高位链表放入新表if (loHead ! null) // 如果低位链表不为空说明原来是红黑树结构hiHead.treeify(tab); // 将高位链表重新组织为红黑树结构}}
}// 树转化为链表
final NodeK,V untreeify(HashMapK,V map) {NodeK,V hd null, tl null; // 初始化新的链表头节点和尾节点// 遍历当前的树节点将其转换为链表节点for (NodeK,V q this; q ! null; q q.next) {NodeK,V p map.replacementNode(q, null); // 将树节点转换为普通链表节点if (tl null) // 如果链表尾节点为空说明是第一个节点hd p; // 设置链表头节点elsetl.next p; // 否则将当前节点连接到尾节点的 next 引用tl p; // 更新链表尾节点}return hd; // 返回新的链表头节点
}
afterNodeAccess方法
// 在节点访问后进行的回调方法
void afterNodeAccess(NodeK,V p) {// 此方法在访问节点后被调用具体的实现可以在子类中覆盖 // 体现了面向对象设计原则中的 开闭原则对修改关闭对扩展开放
}
afterNodeInsertion方法
// 在节点插入后进行的回调方法
void afterNodeInsertion(boolean evict) {// 此方法在插入节点后被调用具体的实现可以在子类中覆盖// 体现了面向对象设计原则中的 开闭原则对修改关闭对扩展开放
}
HashMap的put方法执行流程图示 这里有个点需要注意下
// 如果onlyIfAbsent是false 或者 oldValue 是null 就会新值替换旧值
if (!onlyIfAbsent || oldValue null)e.value value;所以调用HashMap的 putIfAbsent方法时要注意如果key已存在且旧值是null 那么即使key存在也会替换旧值。 代码示例
public static void main(String[] args) {MapString, String hashMap new HashMap(0);hashMap.put(a,null);hashMap.put(b,b);System.out.println(putIfAbsent之前hashMap);// 之前的 key a 对应的 value 是null 所以仍然会替换hashMap.putIfAbsent(a,123);// 之前的 key b 对应的 value 是b 所以不会替换hashMap.putIfAbsent(b,123);System.out.println(putIfAbsent之后hashMap);}执行结果
putIfAbsent之前{anull, bb}
putIfAbsent之后{a123, bb}6、HashMap如何计算key的索引位置
下面是putVal方法内的一段源码可以看到 索引 i (n - 1) hash, 也就是索引等于 哈希表(数组)的长度 key调用 hash(key)方法得到的值。 int n, i; // n为表的长度i为计算出的索引// 如果表为空或表的长度为0则进行扩容操作
if ((tab table) null || (n tab.length) 0)n (tab resize()).length;// 计算哈希值对应的索引如果该索引处没有节点则创建新节点
if ((p tab[i (n - 1) hash]) null)tab[i] newNode(hash, key, value, null);这里我们再来探讨上面提过的哈希表容量的问题。
为什么HashMap的容量设计成总是2的整数倍
①、更高效的计算索引 我们一般计算索引都是使用 key的哈希值对容量求余数也就是 hash%容量 在计算机内部直接使用%求余性能比较低就像我们直接使用乘法符号计算2乘2 (2*2) 和使用移位运算符 2 1 得到的结果是一致的但是移位运算比直接 使用乘法符号计算快的多这是由计算机操作系统本身对算术运算的设计规则决定的。
由于 table.length 总是 2 的幂次方那么 table.length - 1 就是一个全为 1 的二进制数这样可以高效地与哈希值进行按位与运算快速得到索引。
当容量n 是2的整数倍时 计算 索引 i (n - 1) hash 和 i hash%n 结果是一样的。这也就解释了 HashMap的容量设计成2的整数倍的第一个好处。 比如 容量 n 16 hash 3 索引 i (16-1) 3 3; 索引 i 3%16 也等于3。 ②、更好的哈希分布 将容量设置为 2 的幂次方有助于避免哈希碰撞并使得哈希值的低位和高位都能有效参与到索引计算中。因为使用按位与运算时所有位都能参与到索引的计算中如果容量不是 2 的幂次方那么某些位可能永远不会参与到计算中这会导致哈希分布不均匀增加哈希冲突的概率。 ③、高效的扩容操作: 这点设计是真的厉害在扩容时新的容量也是 2 的幂次方这样可以保持上述优点。而且扩容后旧表中的元素可以很容易地重新分配到新表中只需根据元素的哈希值和新表的容量重新计算索引即可。这使得扩容操作更加高效。
扩容时只需要检查元素的哈希值的新增位是 0 还是 1 来决定它是留在原索引位置还是移动到新索引位置
if ((e.hash oldCap) 0) {// 留在原索引位置
} else {// 移动到新索引位置// 新索引的位置 旧索引位置 旧容量
}更精妙的是新索引的位置直接就等于 旧位置 旧容量。 这里举个例子计算一下
1.如果 (e.hash oldCap) 0元素留在原索引位置。
2.如果 (e.hash oldCap) ! 0元素移动到新索引位置旧索引位置 旧容量。假设扩容前哈希表长度为8 , 扩容后哈希表长度为16情况2举例说明假设 a的hash值为10扩容前a的索引位置 i 10(8-1) 10%8 2扩容后a的索引位置
先计算 108 2 ! 0 , 新索引位置 i 旧索引位置(2) 旧容量(8) 10如果我们直接计算新索引位置 i 10(16-1) 10%16 10 和上面计算结果一致情况2举例说明
假设 b的hash值为2扩容前b的索引位置 i 2(8-1) 2%8 2扩容后b的索引位置
先计算 28 0 0 , 新索引位置 i 旧索引位置(2)如果我们直接计算新索引位置 i 2(16-1) 2%16 2 和上面计算结果一致还有一些其他好处 容量总是 2 的幂次方使得很多实现细节变得简单而高效。比如计算容量、计算阈值、扩容等操作都可以利用位运算来实现减少了代码的复杂度和运行时的开销。 由于哈希表的负载因子通常设定为 0.75当容量为 2 的幂次方时可以保证在触发扩容时哈希表的装载程度接近于最佳状态避免了过度扩容或者装载过高导致的性能问题。
7、HashMap的get方法
// 获取指定键的值
public V get(Object key) {// 调用 getNode 方法查找键对应的节点如果找到则返回节点的值否则返回 nullNodeK,V e;return (e getNode(hash(key), key)) null ? null : e.value;
}// 根据 hash 值和键查找节点
final NodeK,V getNode(int hash, Object key) {// 定义一些局部变量NodeK,V[] tab; // 哈希表NodeK,V first, e; // 链表中的节点int n; // 哈希表的长度K k; // 节点中的键// 如果哈希表不为空并且长度大于 0并且对应哈希桶中第一个节点不为空if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) {// 检查第一个节点if (first.hash hash // 比较键是否相等引用相等或者内容相等((k first.key) key || (key ! null key.equals(k))))// 如果第一个节点就是我们要找的直接返回return first;// 如果第一个节点不是我们要找的并且有后续节点if ((e first.next) ! null) {// 如果是树节点红黑树if (first instanceof TreeNode)// 在树中查找节点return ((TreeNodeK,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); // 遍历链表}}// 如果没有找到返回 nullreturn null;
}
红黑树的查找 getTreeNode 方法就不看了感兴趣的可以自己到源码里看。 后续写数据结构和算法之类的文章会再看这类实现特定数据结构的源码。
8、HashMap的remove方法
/*** 根据指定的键从HashMap中移除键值对。* 如果键存在则移除该键值对并返回其对应的值否则返回null。** param key 要移除的键* return 被移除的值如果键不存在则返回null*/
public V remove(Object key) {// 调用removeNode方法执行移除操作并返回被移除节点的值NodeK,V e;return (e removeNode(hash(key), key, null, false, true)) null ?null : e.value;
}/*** 从HashMap中移除指定哈希值和键的节点并可选择性匹配值。* 此方法是HashMap移除元素的核心实现。** param hash 键的哈希值* param key 要移除的键* param value 要匹配的值如果为null则不匹配值* param matchValue 是否进行值匹配* param movable 是否允许节点移动* return 如果成功移除则返回被移除的节点否则返回null*/
final NodeK,V removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {// 定义局部变量NodeK,V[] tab; NodeK,V p; int n, index;// 如果HashMap的表不为空并且长度大于0并且在计算的索引位置有节点if ((tab table) ! null (n tab.length) 0 (p tab[index (n - 1) hash]) ! null) {NodeK,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 ((TreeNodeK,V)p).getTreeNode(hash, key);} else {// 在链表中查找节点do {if (e.hash hash ((k e.key) key ||(key ! null key.equals(k)))) {node e;break;}p e;} while ((e e.next) ! null);}}// 如果找到了节点并且不需要匹配值或值匹配成功if (node ! null (!matchValue || (v node.value) value ||(value ! null value.equals(v)))) {if (node instanceof TreeNode) {// 如果是红黑树节点移除树节点((TreeNodeK,V)node).removeTreeNode(this, tab, movable);} else if (node p) {// 如果节点是链表的头节点直接更新表的索引位置tab[index] node.next;} else {// 否则更新前驱节点的next引用跳过当前节点p.next node.next;}// 更新HashMap的结构修改计数和大小modCount;--size;// 调用节点移除后的处理方法afterNodeRemoval(node);// 返回被移除的节点return node;}}// 如果没有找到匹配的节点返回nullreturn null;
}
9、HashMap的迭代器 由于HashMap是数组链表的数据结构所以HashMap的迭代器只能循环数组从0索引位置开始循环找到第一个非空的Node节点如果该节点的next不会空就继续使用Node节点的next去一个一个遍历元素如果next为空了再往下循环数组直到找到下一个非空的Node节点继续使用next遍历。 所以HashMap的迭代器会循环遍历所有的数组Node节点以及Node节点链接的链表或红黑树的全部元素。
abstract class HashIterator {// 下一个要返回的节点NodeK,V next; // 当前的节点NodeK,V current; // 用于快速失败的期望修改计数int expectedModCount; // 当前槽的索引int index; // 构造方法HashIterator() {// 初始化期望的修改计数等于当前的修改计数expectedModCount modCount;// 获取哈希表NodeK,V[] t table;// 初始化当前节点和下一个节点为nullcurrent next null;// 初始化索引为0index 0;// 如果哈希表不为空并且大小大于0推进到第一个非空的槽if (t ! null size 0) { // 循环直到找到第一个非空的槽do {} while (index t.length (next t[index]) null);}}// 判断是否有下一个元素public final boolean hasNext() {return next ! null;}// 获取下一个节点final NodeK,V nextNode() {// 临时变量t用于存储哈希表NodeK,V[] t;// e用于存储当前的下一个节点NodeK,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;}}
10、HashMap的一些常见问题
①、JDK8为什么引入红黑树
HashMap采用哈希表的结构存储键值对键通过哈希函数被映射到数组的某个索引位置。理想情况下哈希函数将键均匀地分布在数组的各个位置上但在实际应用中不同的键可能会被映射到同一个索引位置导致哈希冲突。
在JDK8之前HashMap在处理哈希冲突时使用的是链表。即在同一个索引位置上存储多个键值对时这些键值对会被存储在一个链表中。这意味着当多个键被映射到同一个位置时查询、插入或删除操作的时间复杂度会随着链表长度的增加而增加最坏情况下达到O(n)其中n是链表中的元素数量。
为了优化在哈希冲突严重情况下的性能JDK8引入了红黑树。当链表长度大于等于8时且哈希表容量大于等于64时。链表会转换为红黑树。
红黑树是一种自平衡二叉搜索树具有以下特点 平衡性红黑树通过一系列的旋转和颜色变化来保持树的平衡使得树的高度始终保持在O(log n)。 查询效率由于红黑树的高度是O(log n)因此在红黑树中的查询、插入和删除操作的时间复杂度是O(log n)比链表的O(n)更高效。
②、红黑树的数据结构有什么特点
树结构有以下特点 查找效率高 通过树形结构如二叉查找树、红黑树、B树等可以在O(log n)时间内完成查找操作比线性结构如数组、链表高效。
保持数据有序 树结构能够在插入和删除操作后保持数据的有序性适用于需要频繁更新和检索的数据集。
表示层次结构 树结构用于表示具有层次关系的数据如XML/HTML文档、组织结构图、文件系统等。
高效插入和删除 树结构支持高效的插入和删除操作特别是自平衡树通过旋转和重新平衡操作能够在O(log n)时间内完成插入和删除。
红黑树的特点
节点颜色每个节点都被标记为红色或黑色。根节点根节点始终是黑色。叶子节点所有叶子节点即空节点都是黑色。红色规则红色节点不能有两个连续的红色父节点和子节点。黑色规则从任一节点到其每个叶节点的所有路径都包含相同数量的黑色节点。 这些规则确保红黑树在最坏情况下也能保持O(log n)的时间复杂度。通过插入和删除操作后的旋转和重新着色红黑树能够保持平衡避免退化成线性结构。
二叉查找树BST与红黑树Red-Black Tree的区别:
特点普通二叉查找树BST红黑树Red-Black Tree基本定义每个节点最多有两个子节点左子节点小于父节点右子节点大于父节点一种自平衡的二叉查找树附加了红黑节点的颜色属性平衡性不保证平衡可能会退化成线性结构保持平衡通过颜色和旋转操作维持最坏情况时间复杂度O(n)退化成链表时O(log n)平均情况时间复杂度O(log n)O(log n)插入复杂度O(log n)平均情况O(n)最坏情况O(log n)删除复杂度O(log n)平均情况O(n)最坏情况O(log n)查询复杂度O(log n)平均情况O(n)最坏情况O(log n)结构维护插入和删除不涉及复杂的维护操作插入和删除需要进行旋转和重新着色来维持平衡使用场景简单的插入、查找操作数据相对有序时性能较好需要频繁插入、删除和查找操作时性能稳定退化情况当插入数据按顺序升序或降序时会退化成线性结构通过自平衡机制避免退化
普通的二叉查找树BST会在以下情况下退化成线性结构 当节点按顺序升序或降序插入时每个节点都只有一个子节点导致树变成一条“链”。 例如插入序列为1, 2, 3, 4, 5时BST会退化成
③、负载因子为什么是0.75
在空间占用与查询时间之间取得较好的权衡。 大于这个值空间节省了但链表可能就会比较长影响性能。 小于这个值冲突减少了但扩容就会更频繁空间占用多。 综合考虑实际使用场景和对性能的要求0.75加载因子是经验上比较成熟和常用的选择。 这个值在大多数情况下能够保证HashMap在性能和空间利用率之间取得合理的平衡。
数学概率方面 hash 值如果足够随机则在 hash 表内按泊松分布在负载因子 0.75 的情况下长度超过8的链表出现概率是0.00000006选择8就是为了让树化几率足够小。
添加第一个元素时默认情况下HashMap容量是16负载因子是0.75 。 16*0.7512 也就是第一次扩容的阈值为12。 当添加第13个元素的时候1312HashMap容量扩容为32
public static void main(String[] args) throws Exception {HashMapString, String map new HashMap();// 获取 HashMap 内部的 table 数组长度Field tableField HashMap.class.getDeclaredField(table);tableField.setAccessible(true); // 设置可访问私有字段map.put(1,123);Object[] table (Object[]) tableField.get(map);System.out.println(table.length); // 16map.put(2,123);map.put(3,123);map.put(4,123);map.put(5,123);map.put(6,123);map.put(7,123);map.put(8,123);map.put(9,123);map.put(10,123);map.put(11,123);map.put(12,123);Object[] table1 (Object[]) tableField.get(map);System.out.println(table1.length); // 16map.put(13,123);Object[] table2 (Object[]) tableField.get(map);System.out.println(table2.length); // 32}④、为什么数组长度≥64且链表长度 ≥8才树化
空间和时间的折中考虑 红黑树比链表占用更多的内存空间因为树节点通常比链表节点大。因此在选择将链表转换成树时需要权衡空间和时间效率。 只有在链表长度较大时大于等于阈值8才值得为了提升时间效率而牺牲一定的空间。
并不是所有长度大于等于8的链表都会立即树化只有当链表长度大于等于8且数组(哈希表)长度大于等于64时才会树化。如果链表长度大于等于8但是数组长度小于64此时会进行扩容重新散列而不是树化。 因为数组长度小于64说明此时的数组容量还很小此时应该考虑扩容把元素重新散列到更大的哈希表中以减少哈希冲突来提升性能。
⑤、多线程下HashMap写操作可能出现哪些问题
JDK8之前可能会出现 扩容死链(头插法导致)丢失数据。
JDK8的HashMap的链表采用了尾插法不会出现扩容死链问题仍然可能会出现丢失数据问题。
JDK1.8之前并发扩容死链问题动画演示
这个动画我画了快3小时 ┭┮﹏┭┮ 多看几遍 我相信就能很容易理解扩容死链形成的过程了。 最终形成了 a.nextb, b.nexta 的这种死链 此时当我们再调用查找方法比如 key c 的索引也是1 HashMap就会遍历这个死链发现a不是b不是 再往下遍历又到了a、bab 无线循环下去就会导致 本次 get©的调用陷入死循环。
丢失数据问题代码演示
public static void main(String[] args) throws Exception {HashMapString, String map new HashMap();// 默认容量16Thread t1 new Thread(() - {map.put(a,a); // hash值 97 索引位置 i (16-1) 97 1map.put(b,b); // hash值 98 索引位置 i (16-1) 98 2},t1);Thread t2 new Thread(() - {map.put(1,1); // hash值 49 索引位置 i (16-1) 49 1map.put(2,2); // hash值 50 索引位置 i (16-1) 50 2},t2);t2.setName(t2);t1.start();t2.start();t1.join();t2.join();System.out.println(map);}可以看到 key “a” 和 “1” 会出现哈希冲突key “b” 和 “2” 会出现哈希冲突。 正常情况下应该得到的结果是
{11, aa, 22, bb}现在我们演示下出问题的情况 首先打断点断点的条件设置为 线程名称是 t1或者t2才走断点。(因为JVM启动的时候也会调用putVal方法不加条件可能会断点到很多其他线程的调用)
断点条件代码Thread.currentThread().getName().equals(t1)||Thread.currentThread().getName().equals(t2) ①、debug运行代码先走t1线程的断点 map.put(a,a); // hash值 97 索引位置 i (16-1) 97 1 注意让t1只走到判断 索引位置为空的if条件里先不给数组赋值 ②、此时选t2线程此时由于 key 1的索引位置也是1 而t1线程 还没来得及给数组的这个1位置赋值 所以t2线程也进入了if代码块内 。 此时让t2线程继续往下走一步赋值 map.put(1,1); // hash值 49 索引位置 i (16-1) 49 1 , 数组的 tab[1] (“1”,“1”)了 ③、再返回t1线程此时的tab[1] 已经有值了是上面 t2线程赋的值。 这个时候让t1线程继续赋值就把 t2 线程在索引位置1 处赋的值覆盖掉了。 ④、我们再重复上面的操作再走t1进if语句内不赋值然后等t2赋值后t1再赋值。 最终就能得到丢失数据的结果。
{aa, bb}可以看到 和正常情况的 {11, aa, 22, bb} 相比 丢失了t2线程put的数据。
⑥、JDK8之前的put方法和之后的put方法有什么区别
1、链表插入行为不同链表插入节点时JDK8之前是头插法JDK8是尾插法。2、扩容行为不同JDK8之前是大于等于阈值且没有空位时才扩容而JDK8是大于阈值就扩容.3、链表和红黑树转化JDK8之前只有链表JDK8引入红黑树。
⑦、HashMap的红黑树什么情况下会退化成链表
退化情况1: 在扩容时如果拆分树时树元素个数6则会退化为链表。
在HashMap进行扩容时会对现有的桶进行重新分配元素。如果一个桶中原本是红黑树节点TreeNode而在进行扩容时树中节点的数量少于等于6个HashMap会选择将这些节点转换为链表形式。这是因为对于数量较少的节点来说使用链表而不是红黑树可能会更节省空间和操作成本。 对应代码
if (loHead ! null) {// 如果低位链表头结点不为空if (lc UNTREEIFY_THRESHOLD)// 如果低位链表的节点数小于等于UNTREEIFY_THRESHOLD (默认是6)将其退化成链表tab[index] loHead.untreeify(map);else {// 否则保持为红黑树tab[index] loHead;if (hiHead ! null) // 如果高位链表头结点也不为空保持红黑树结构loHead.treeify(tab);}
}if (hiHead ! null) {// 如果高位链表头结点不为空if (hc UNTREEIFY_THRESHOLD)// 如果高位链表的节点数小于等于UNTREEIFY_THRESHOLD (默认是6)将其退化成链表tab[index bit] hiHead.untreeify(map);else {// 否则保持为红黑树tab[index bit] hiHead;if (loHead ! null) // 如果低位链表头结点也不为空保持红黑树结构hiHead.treeify(tab);}
}
退化情况2: remove 树节点时若 root、root.left、root.right、root.left.left有一个为 null也会退化为链表。
在HashMap中删除树节点时如果根节点或其子节点的左右子节点为null则树节点会退化为链表形式。 这是因为在红黑树中根节点的左右子节点为null意味着红黑树的结构不再成立因此HashMap选择将这部分节点转换为链表以保持结构的一致性和简单性。
对应代码
final void removeTreeNode(HashMapK,V map, NodeK,V[] tab, boolean movable) {int n;if (tab null || (n tab.length) 0)return; // 如果哈希表为空或长度为零直接返回int index (n - 1) hash; // 计算节点所在的桶索引TreeNodeK,V first (TreeNodeK,V)tab[index], root first, rl;TreeNodeK,V succ (TreeNodeK,V)next, pred prev;if (pred null)tab[index] first succ; // 如果没有前驱节点将桶头设置为后继节点elsepred.next succ; // 否则将前驱节点的 next 指向后继节点if (succ ! null)succ.prev pred; // 如果有后继节点将其 prev 指向前驱节点if (first null)return; // 如果桶头为空直接返回if (root.parent ! null)root root.root(); // 获取红黑树的根节点if (root null || root.right null || (rl root.left) null || rl.left null) {tab[index] first.untreeify(map); // 如果红黑树的结构不再平衡将其退化为链表return;}TreeNodeK,V p this, pl left, pr right, replacement;if (pl ! null pr ! null) {TreeNodeK,V s pr, sl;while ((sl s.left) ! null)s sl; // 找到后继节点boolean c s.red; s.red p.red; p.red c; // 交换颜色TreeNodeK,V sr s.right;TreeNodeK,V pp p.parent;if (s pr) {p.parent s;s.right p; // 如果后继节点是右子节点调整关系} else {TreeNodeK,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; // 调整右子节点与 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; // 调整后继节点与 p 父节点的关系if (sr ! null)replacement sr;elsereplacement p; // 确定替代节点} else if (pl ! null)replacement pl; // 如果只有左子节点替代节点为左子节点else if (pr ! null)replacement pr; // 如果只有右子节点替代节点为右子节点elsereplacement p; // 如果没有子节点替代节点为 pif (replacement ! p) {TreeNodeK,V pp replacement.parent p.parent;if (pp null)root replacement;else if (p pp.left)pp.left replacement;elsepp.right replacement; // 调整替代节点与 p 父节点的关系p.left p.right p.parent null; // 清空 p 的引用}TreeNodeK,V r p.red ? root : balanceDeletion(root, replacement); // 平衡删除操作if (replacement p) { // 断开 p 与其父节点的关系TreeNodeK,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); // 如果可移动将根节点移动到桶头
} 文章转载自： http://www.morning.pudejun.com.gov.cn.pudejun.com http://www.morning.fnpmf.cn.gov.cn.fnpmf.cn http://www.morning.hghhy.cn.gov.cn.hghhy.cn http://www.morning.qftzk.cn.gov.cn.qftzk.cn http://www.morning.mlhfr.cn.gov.cn.mlhfr.cn http://www.morning.tjsxx.cn.gov.cn.tjsxx.cn http://www.morning.pqkrh.cn.gov.cn.pqkrh.cn http://www.morning.lwlnw.cn.gov.cn.lwlnw.cn http://www.morning.nkllb.cn.gov.cn.nkllb.cn http://www.morning.fgwzl.cn.gov.cn.fgwzl.cn http://www.morning.lcbnb.cn.gov.cn.lcbnb.cn http://www.morning.sfwcx.cn.gov.cn.sfwcx.cn http://www.morning.rxwfg.cn.gov.cn.rxwfg.cn http://www.morning.qsctt.cn.gov.cn.qsctt.cn http://www.morning.wnywk.cn.gov.cn.wnywk.cn http://www.morning.hslgq.cn.gov.cn.hslgq.cn http://www.morning.qhkdt.cn.gov.cn.qhkdt.cn http://www.morning.crrmg.cn.gov.cn.crrmg.cn http://www.morning.kyytt.cn.gov.cn.kyytt.cn http://www.morning.rkdzm.cn.gov.cn.rkdzm.cn http://www.morning.dnwlb.cn.gov.cn.dnwlb.cn http://www.morning.lznqb.cn.gov.cn.lznqb.cn http://www.morning.fphbz.cn.gov.cn.fphbz.cn http://www.morning.zkqsc.cn.gov.cn.zkqsc.cn http://www.morning.qkqgj.cn.gov.cn.qkqgj.cn http://www.morning.hrtfz.cn.gov.cn.hrtfz.cn http://www.morning.bcdqf.cn.gov.cn.bcdqf.cn http://www.morning.bchfp.cn.gov.cn.bchfp.cn http://www.morning.gbljq.cn.gov.cn.gbljq.cn http://www.morning.lrybz.cn.gov.cn.lrybz.cn http://www.morning.xzsqb.cn.gov.cn.xzsqb.cn http://www.morning.xjwtq.cn.gov.cn.xjwtq.cn http://www.morning.ymjgx.cn.gov.cn.ymjgx.cn http://www.morning.bgzgq.cn.gov.cn.bgzgq.cn http://www.morning.cxryx.cn.gov.cn.cxryx.cn http://www.morning.njpny.cn.gov.cn.njpny.cn http://www.morning.yfffg.cn.gov.cn.yfffg.cn http://www.morning.rxwfg.cn.gov.cn.rxwfg.cn http://www.morning.pfjbn.cn.gov.cn.pfjbn.cn http://www.morning.krxzl.cn.gov.cn.krxzl.cn http://www.morning.qwzpd.cn.gov.cn.qwzpd.cn http://www.morning.jzkqg.cn.gov.cn.jzkqg.cn http://www.morning.ywtbk.cn.gov.cn.ywtbk.cn http://www.morning.ltdxq.cn.gov.cn.ltdxq.cn http://www.morning.dspqc.cn.gov.cn.dspqc.cn http://www.morning.tnbsh.cn.gov.cn.tnbsh.cn http://www.morning.yqrgq.cn.gov.cn.yqrgq.cn http://www.morning.wlxfj.cn.gov.cn.wlxfj.cn http://www.morning.mfjfh.cn.gov.cn.mfjfh.cn http://www.morning.mrqwy.cn.gov.cn.mrqwy.cn http://www.morning.mljtx.cn.gov.cn.mljtx.cn http://www.morning.brwwr.cn.gov.cn.brwwr.cn http://www.morning.aswev.com.gov.cn.aswev.com http://www.morning.rfwrn.cn.gov.cn.rfwrn.cn http://www.morning.gklxm.cn.gov.cn.gklxm.cn http://www.morning.nlrp.cn.gov.cn.nlrp.cn http://www.morning.nwgkk.cn.gov.cn.nwgkk.cn http://www.morning.jpnfm.cn.gov.cn.jpnfm.cn http://www.morning.mnkz.cn.gov.cn.mnkz.cn http://www.morning.rrms.cn.gov.cn.rrms.cn http://www.morning.klyyd.cn.gov.cn.klyyd.cn http://www.morning.kjrp.cn.gov.cn.kjrp.cn http://www.morning.nyqxy.cn.gov.cn.nyqxy.cn http://www.morning.zlwg.cn.gov.cn.zlwg.cn http://www.morning.kkrnm.cn.gov.cn.kkrnm.cn http://www.morning.mgmyt.cn.gov.cn.mgmyt.cn http://www.morning.gdpai.com.cn.gov.cn.gdpai.com.cn http://www.morning.qlxgc.cn.gov.cn.qlxgc.cn http://www.morning.hmqwn.cn.gov.cn.hmqwn.cn http://www.morning.gnlyq.cn.gov.cn.gnlyq.cn http://www.morning.pgzgy.cn.gov.cn.pgzgy.cn http://www.morning.bqmhm.cn.gov.cn.bqmhm.cn http://www.morning.diuchai.com.gov.cn.diuchai.com http://www.morning.sgmgz.cn.gov.cn.sgmgz.cn http://www.morning.trsfm.cn.gov.cn.trsfm.cn http://www.morning.fjglf.cn.gov.cn.fjglf.cn http://www.morning.rnnts.cn.gov.cn.rnnts.cn http://www.morning.nqbs.cn.gov.cn.nqbs.cn http://www.morning.hqwxm.cn.gov.cn.hqwxm.cn http://www.morning.glnxd.cn.gov.cn.glnxd.cn
