位置: IT常识 - 正文

HashMap详解(hashmap教程)

编辑:rootadmin
什么是HashMap容器 【1】HashMap是使用频率最高的用于映射(键值对)处理的数据类型。随着JDK(Java Developmet Kit)版本的更新,JDK1.8对HashMap底层的实现进行了优化,例如引入红黑树的数据结构和扩容的优化等。 【2】jdk1.8 之前 HashMap 由 数 ... 什么是HashMap容器

推荐整理分享HashMap详解(hashmap教程),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:hashmap理解,hashmap介绍,hashmap isempty,hashmap中常用的方法总结,hashmap详细讲解,hashmap使用方法,hashmap理解,hashmap entry,内容如对您有帮助,希望把文章链接给更多的朋友!

【1】HashMap是使用频率最高的用于映射(键值对)处理的数据类型。随着JDK(Java Developmet Kit)版本的更新,JDK1.8对HashMap底层的实现进行了优化,例如引入红黑树的数据结构和扩容的优化等。

【2】jdk1.8 之前 HashMap 由 数组 + 链表 组成,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突(两个对象调用的 hashCode 方法计算的哈希值经哈希函数算出来的地址被别的元素占用)而存在的(“拉链法”解决冲突)。jdk1.8 以后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(或者红黑树的边界值,默认为 8 )并且当前数组的长度大于 64 时,此时此索引位置上的所有数据改为使用红黑树存储。

【3】HashMap:它根据键的hashCode值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null,允许多条记录的值为null。HashMap非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap。

HashMap的疑难问题

【1】为什么转成树结构的阈值是8,而由树转回为链表结构的阈值是6?

  在源码中有这么一段注释:

Implementation notes.实现注意事项This map usually acts as a binned (bucketed) hash table, but when bins get too large, they are transformed into bins of TreeNodes, each structured similarly to those in java.util.TreeMap. Most methods try to use normal bins, but relay to TreeNode methods when applicable (simply by checking instanceof a node). Bins of TreeNodes may be traversed and used like any others, but additionally support faster lookup when overpopulated. However, since the vast majority of bins in normal use are not overpopulated, checking for existence of tree bins may be delayed in the course of table methods.这个映射通常充当一个分箱(桶)哈希表,但是当容器太大时,它们被转换为TreeNodes的容器,每个容器的结构类似于java.util.TreeMap中的容器。大多数方法尝试使用普通的bin,但在适用的情况下中继到TreeNode方法(简单地通过检查节点的实例)。TreeNodes的容器可以像其他容器一样被遍历和使用,但是在过度填充时还支持更快的查找。然而,由于正常使用的绝大多数容器都没有过度填充,所以在表方法的过程中可能会延迟检查树容器的存在。....Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins. In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75,although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The first values are:因为TreeNodes大约是常规节点的两倍大,所以我们只在容器包含足够的节点以保证使用时才使用它们(参见TREEIFY_THRESHOLD)。当它们变得太小(由于删除或调整大小)时,它们会被转换回普通的容器。在分布良好的用户hashCodes的用法中,很少使用树容器。理想情况下,在随机hashCodes下,容器中节点的频率遵循泊松分布(http://en.wikipedia.org/wiki/Poisson_distribution),对于默认的调整大小阈值0.75,该分布的参数平均约为0.5,尽管由于调整大小粒度的差异很大。忽略方差,列表大小k的期望出现次数为(exp(-0.5) * pow(0.5, k) / factorial(k))。第一个值是:0: 0.606530661: 0.303265332: 0.075816333: 0.012636064: 0.001579525: 0.000157956: 0.000013167: 0.000000948: 0.00000006 千万分之6more: less than 1 in ten million如果是更多的话,会低于千万分之一...

【2】为什么HashMap要保证数组长度是2的倍数呢?

主要原因是在于为了扩容时候的数据迁移,因为在源码中,HashMap是一个一个槽位的将数据迁移。如果限制了是2的倍数是怎么样的呢?如4个槽位各有四个数据【1】 5,9,13,17【2】 6,10,14,18【3】 7,11,15,19【4】 8,12,16,20扩容成了8个槽位,则数据必然散落在原本的槽位和与之倍数的槽位上【1】 9,17【2】 10,18【3】 11,19【4】 12,20【5】 5,13【6】 6,14【7】 7,15【8】 8,16这也是为什么扩容的时候只用设置两个链表结构的原因:Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;反之如果是1.5倍,那么散落在的槽位就不确定了,那么我们就要面对更复杂的情况,必然要按照槽位设置多个链表结构如8个槽位就要8个链表结构,槽位越多,对应的花销更多,所以显得不划算源码分析HashMap的实现(我这里是拿JDK14的源码展示的)

【0】继承关系

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, SerializableHashMap详解(hashmap教程)

【1】节点的类型分析

//明显是单链表的节点static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; }}//LinkedHashMap类的Entry结构,将单链表节点包装之后具备双向链表节点的功能static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); }}//所以TreeNode其实只是在Node节点上做了包装,所以这个树节点其实是包含了树和双向链表节点两者的功能static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } /** * Returns root of tree containing this node. */ final TreeNode<K,V> root() { for (TreeNode<K,V> r = this, p;;) { if ((p = r.parent) == null) return r; r = p; } }...}

【2】属性值

//默认初始容量static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16//默认最大容量static final int MAXIMUM_CAPACITY = 1 << 30;//即536,870,912//默认加载因子static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认转成树结构的阈值static final int TREEIFY_THRESHOLD = 8;//由树转回为链表结构的阈值static final int UNTREEIFY_THRESHOLD = 6;//默认转成树时候数组的最小容量static final int MIN_TREEIFY_CAPACITY = 64;/* ---------------- Fields -------------- *///存放数据的集合transient Node<K,V>[] table;//用于迭代器使用的transient Set<Map.Entry<K,V>> entrySet;//数据个数transient int size;//修改次数记录transient int modCount;//扩容的阈值,默认是(容量*加载因子)int threshold;//哈希表的加载因子final float loadFactor;

【3】构造方法

//指定容量和负载因子public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException(...); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException(...); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity);}//这个方法保证得出来的容量是2的N次方,把不足2的N次方的向上取到2的N次方//如3得4,5得8,10得16//设计的巧妙点在于使用了>>>表示无符号右移,也叫逻辑右移与异或方法//减1,是为了让二进制尽可能多的出现1,如1000000,减一后变为0111111。当然如果是1000001,这种会变为1000000【但影响并不大】。//就以1000001为例子,减一后为1000000//其次当右移一位之后再异或就会保证前两位是1,即1000000|100000=1100000//所以第二次直接右移两位再异或,即1100000|11000=1111000//第三次就右移四位,即1111000|111=1111111//所以最后+1,是会变成10000000即128static 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;}//指定容量,默认负载因子为0.75public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR);}//容量使用默认值16,负载因子也为默认值0.75public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}//传入有数据的Mappublic HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false);}final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { int s = m.size(); if (s > 0) { //初始化容器 if (table == null) { // pre-size //使得计算出来的容量不大于阈值,+1是为了向上取整,因为整除是会舍弃小数点后面的 float ft = ((float)s / loadFactor) + 1.0F; //限制不大于最大容量 int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); //因为有可能是上面那种设置了容量但是没有初始化table的情况 if (t > threshold) threshold = tableSizeFor(t); } //说明table已经初始化过了;判断传入map的size是否大于当前map的threshold,如果是,必须要resize,预先扩大容量,再put元素 else if (s > threshold) resize(); for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); //塞入数据 putVal(hash(key), key, value, false, evict); } }}

【4】核心方法分析

【4.1】添加方法put()分析

//加入元素public V put(K key, V value) { return putVal(hash(key), key, value, false, true);}//生成的hash是key的hashCode的高16位与低16位相与static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { 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) tab[i] = newNode(hash, key, value, null); else { //如果数组中已经有节点了 Node<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 { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { //放置于链表末尾 p.next = newNode(hash, key, value, null); //判断是否满足转成树节点的条件【链表长度为8】 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } //如果当前遍历到的数据和要插入的数据的 key 是一样,和上面之前的一样,赋值给变量 e,下面替换内容 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //进行内容的替换 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); //扩展方法 return oldValue; } } ++modCount; //达到阈值便要扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); //扩展方法 return null;}//这里就涉及到了Node节点的创建了Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) { return new Node<>(hash, key, value, next);}

【4.1.1】链表转成树结构treeifyBin()方法分析

final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; //限制了数组最少是64的长度 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); //满足数组长度64,链表长度8,就开始转为树结构 else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; //先将单链表转为双向链表 do { TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); //将双向链表进行树化 if ((tab[index] = hd) != null) hd.treeify(tab); }}

【4.2】扩容方法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; //第一阶段:计算出新的newCap(扩容后的容量)和newThr(扩容后阈值) if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //新容量为旧容量的2倍 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 { //如果数组还没有则将默认值设置进去,默认容量16,阈值为16*0.75=12 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; //第二阶段:根据newCap和newThr构造出新的newTab @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //这里其实是线程不安全的,因为table的引用此时指向了新数组【而新数组还没有被赋值】 table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,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) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //如果是链表 else { //构建两个链表结构【这就是为什么要进行两倍扩容的原因:因为假设是4个槽位,扩容到8个槽位,那么原本在第3槽位的数据散列之后的落点必然是在3与7两者之一】 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;}

【4.2.1】分析树节点的分割子树流程

//本质上也是先弄成两个链表//然后判断存入槽位的该是链表还是树final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { TreeNode<K,V> b = this; //也是创建了两个链表结构 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; } } //对生成的链表进行判断 if (loHead != null) { //要么不满足条件,将退化成为链表,即将TreeNode结构转回为Node 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.2.1.1】分析树节点的退化流程

final Node<K,V> untreeify(HashMap<K,V> map) { Node<K,V> hd = null, tl = null; for (Node<K,V> q = this; q != null; q = q.next) { //重新转为Node节点 Node<K,V> p = map.replacementNode(q, null); if (tl == null) hd = p; else tl.next = p; tl = p; } return hd;}Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) { return new Node<>(p.hash, p.key, p.value, next);}

【4.2.1.2】分析树节点的再次树化treeify()方法流程

final void treeify(Node<K,V>[] tab) { TreeNode<K,V> root = null; // 定义树的根节点 for (TreeNode<K,V> x = this, next; x != null; x = next) { // 遍历链表,x指向当前节点、next指向下一个节点 next = (TreeNode<K,V>)x.next; x.left = x.right = null; // 设置当前节点的左右节点为空 if (root == null) { // 如果还没有根节点 x.parent = null; // 当前节点的父节点设为空 x.red = false; // 当前节点的红色属性设为false(把当前节点设为黑色) root = x; // 根节点指向到当前节点 } else { // 如果已经存在根节点了 K k = x.key; // 取得当前链表节点的key int h = x.hash; // 取得当前链表节点的hash值 Class<?> kc = null; for (TreeNode<K,V> p = root;;) { // 从根节点开始遍历,此遍历没有设置边界,只能从内部跳出 int dir, ph; K pk = p.key; // 当前树节点的key if ((ph = p.hash) > h) // 如果当前树节点hash值 大于 当前链表节点的hash值 dir = -1; // 标识当前链表节点会放到当前树节点的左侧 else if (ph < h) dir = 1; // 标识当前链表节点会放到当前树节点的右侧 //如果两个节点的key的hash值相等,那么还要通过其他方式再进行比较, //如果当前链表节点的key实现了comparable接口,并且当前树节点和链表节点是相同Class的实例,那么通过comparable的方式再比较两者。 //如果还是相等,最后再通过tieBreakOrder比较一次 else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) dir = tieBreakOrder(k, pk); TreeNode<K,V> xp = p; //挂载之后,还需要重新把树进行平衡。平衡之后,就可以针对下一个链表节点进行处理了。 //为什么需要再平衡,基于红黑树的定义【红黑树(Red Black Tree) 是一种自平衡二叉查找树】: //性质1. 结点是红色或黑色。 //性质2. 根结点是黑色。 //性质3. 所有叶子都是黑色。(叶子是NIL结点) //性质4. 每个红色结点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点) //性质5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。 if ((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; if (dir <= 0) xp.left = x; else xp.right = x; root = balanceInsertion(root, x); // 重新平衡 break; } } } } // 把所有的链表节点都遍历完之后,最终构造出来的树可能经历多个平衡操作,根节点目前到底是链表的哪一个节点是不确定的 // 因为我们要基于树来做查找,所以就应该把 tab[N] 得到的对象一定根节点对象,而目前只是链表的第一个节点对象,所以要做相应的处理。 moveRootToFront(tab, root);}//将根结点放置于数组的槽位上,便于一开始就从树的头结点开始遍历static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) { int n; //红黑树根节点不能为空,table数组不能为空 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; //重置红黑树根节点的上下级关系,主要是调整root,root.prev,root.next,first;四者的关系 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); }}

【4.2.1.2】分析树节点的再平衡balanceInsertion()方法流程

static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) { //默认是红色节点 x.red = true; //循环当前节点的树结构 for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { //如果当前对象的父节点为空,则认为是根节点,根节点不能为红节点,返回该节点 if ((xp = x.parent) == null) { x.red = false; return x; } //如果父节点是红色节点,以父节点的父节点为空,当前节点为根节点的孙子,设置该节点为红色,并返回 else if (!xp.red || (xpp = xp.parent) == null) return root; //如果当前节点的父节点和父节点的父节点的左节点相等 if (xp == (xppl = xpp.left)) { //如果当前节点的父节点的父节点的右节点是红色的 if ((xppr = xpp.right) != null && xppr.red) { xppr.red = false; xp.red = false; xpp.red = true; x = xpp; } else { //如果当前节点与父节点的右节点相等,则进行左旋转 if (x == xp.right) { root = rotateLeft(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } //父节点不为空,设置父节点的颜色,及是否右旋转 if (xp != null) { xp.red = false; if (xpp != null) { xpp.red = true; root = rotateRight(root, xpp); } } } } //如果当前节点的父节点和父节点的父节点的左节点不相等 else { if (xppl != null && xppl.red) { xppl.red = false; xp.red = false; xpp.red = true; x = xpp; } else { //如果当前节点与父节点的左节点相等,则进行右旋转 if (x == xp.left) { root = rotateRight(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } //父节点不为空,设置父节点的颜色,及是否左旋转 if (xp != null) { xp.red = false; if (xpp != null) { xpp.red = true; root = rotateLeft(root, xpp); } } } } }}//左旋static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) { TreeNode<K,V> r, pp, rl; if (p != null && (r = p.right) != null) { if ((rl = p.right = r.left) != null) rl.parent = p; if ((pp = r.parent = p.parent) == null) (root = r).red = false; else if (pp.left == p) pp.left = r; else pp.right = r; r.left = p; p.parent = r; } return root;}//右旋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) lr.parent = p; if ((pp = l.parent = p.parent) == null) (root = l).red = false; else if (pp.right == p) pp.right = l; else pp.left = l; l.right = p; p.parent = l; } return root;}

【4.3】主体的存放逻辑已经阐述完了,下次有空再补一下JDK7的版本吧,毕竟JDK8可是修复了老版本的大BUG。

本文链接地址:https://www.jiuchutong.com/zhishi/304599.html 转载请保留说明!

上一篇:从阿里规约看Spring事务(阿里规则官方头条)

下一篇:php $this是什么意思(php中的this)

  • 账面价值与计税基础一般会产生差异的是
  • 当期所得税费用可以是负数吗
  • 个体工商户怎么年报
  • 运输费用的增值税税率
  • 发票审核未通过,怎么查原因
  • 对公账户取现金怎么取
  • 注销公司详细步骤
  • 税务季度申报如何网上申报填写
  • 个税年度累计计算器
  • 民间非营利组织算企业吗
  • 企业所得税研发费用加计扣除政策的文件
  • 计提坏账准备为什么要加借方
  • 电子发票和纸质发票额度算在一起吗
  • 建筑业简易征收差额征税的计算案例
  • 2020年购进农产品的扣除率
  • 高新技术企业资助
  • 核定征收金额如何确定
  • 发票红冲需要用发票打印吗
  • 公司为职工缴纳的医保不计入账户吗
  • 购买固定资产货款未付
  • 资产总额是资产负债表中的哪个数
  • 企业会计准则制度
  • 出口退税挂靠业务如何做帐?
  • 进项抵扣怎么做分录
  • 开始菜单无法打开怎么办
  • 关联企业承担什么责任
  • macbookappstore未知错误
  • 先开票后收款的发票怎么备注
  • 错账的种类
  • 某建筑公司因施工期紧迫,事先未能与有关
  • php实现删除功能
  • bert multihead
  • php array add
  • php合并字符串函数
  • 人工智能科技向善
  • Yii2针对游客、用户防范规则和限制的解决方法分析
  • linux ar命令
  • 年金现值系数和年金终值系数的公式
  • vant的Uploader 文件上传,图片数据回显问题
  • mongodb4.4.2安装教程
  • 帝国cms使用redis
  • 财政拨付注册资本金说明
  • 不动产登记违建处理办法
  • sql server 2008 2014
  • 企业福利费账务处理
  • 税金及附加减半征收金额按哪个
  • 当月作废的发票是否需要报税
  • 预计负债的账务处理
  • 国有资产无偿划转协议
  • 公司向个人借款的会计分录怎么做
  • 委托加工后直接对外销售消费税
  • 上年未结转金额是什么意思
  • 普通发票采购分录
  • 税前扣除项目主要包括
  • 经费收入经费支出怎样记账
  • 挂靠工程项目预交税金的会计分录如何做?
  • 冲暂估成本能冲部分暂估吗
  • 会计明细账怎么记
  • 留抵的进项税可以用多少年
  • window系统怎么截屏屏幕
  • win7超级账户如何启用
  • ubuntu安装ubuntu-desktop
  • macbook launch
  • Win10自带输入法打不出中文
  • win7文件无法删除需要权限
  • windows8.1 preview
  • 番茄花园论坛
  • win7激活工具怎么使用
  • 图文详解地理图册电子版
  • java框架怎么用
  • javascript教程chm
  • jquery获取input内容
  • js上滑翻页
  • js函数总结
  • 容积率大于0.5 房产原值怎样算
  • 国家税务总局党委委员名单
  • 文化公司税务筹划
  • 车辆购置税查询平台打印
  • 重庆市房产交易信息网
  • 中国进口车关税为什么那么贵
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设