HashMap底层源码解析及红黑树分析

这篇具有很好参考价值的文章主要介绍了HashMap底层源码解析及红黑树分析。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

HashMap线程不安全,底层数组+链表+红黑树
面试重点是put方法,扩容

总结

put方法

HashMap的put方法,首先通过key去生成一个hash值,第一次进来是null,此时初始化大小为16,i = (n - 1) & hash计算下标值,第一次获取是null,直接放入一个Node节点,如果不是null,分成下面三种情况
1)如果发现hash和key相等,将原来的覆盖
2)不相等,就要用到链表,通过尾插法插入到尾部。超过8转成红黑树
3)如果是TreeNode,插入即可

扩容

首先,上面put方法每次都会计算大小
如果超过16*0.75,即12就会r调用resize方法
这里主要是老数组上面元素转到新数组上面去的逻辑
遍历,如果老数组上面元素不是null
这里又是几种情况
1)如果next下标是null,
说明只有一个元素,直接重新计算下标放入新数组
2)判断是否是TreeNode
对TreeNode树进行拆分,转到新数组,不一定在一起。拆分后不一定还是树,这里各种情况,看节点对应的是高位还是低位。判断低位个数如果不超过6,转成链表(TreeNode转成Node)。高位也一样。否则重新生成红黑树(根据是否有高地位判断是否需要重新生成红黑树)
3)否则说明是个链表,
将链表转到新数组上面去,扩容后重新计算hash后下标不一定还是相同的,所以不能直接转到新数组,但是扩容后下标是有规律的。扩容后只有两种情况,低位和高位。 哪些节点是在低位链表上面,哪些节点是在高位链表上面。然后放到新数组即可。

源码如下:

/**
 * 默认的初始容量-必须是二的幂。2的4次方=16,
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * 如果隐式指定了更高的值,则使用最大容量由带有参数的构造函数中的任何一个执行。必须是二次方<=1<<30。
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 在构造函数中未指定时使用的负载系数。
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 使用树而不是列表作为存储箱的存储箱计数阈值。当向至少有这么多节点的bin添加元素时,bin会转换为树。该值必须大于2,并且应至少为8,以符合树木移除中关于收缩后转换回普通垃圾箱的假设。
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 在调整大小操作期间取消尝试(拆分)垃圾箱的垃圾箱计数阈值。应小于TREEIFY_THRESHOLD,并且最多6个,以便在去除时进行收缩检测。
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 可以将垃圾箱树化的最小桌子容量。(否则,如果一个bin中的节点太多,则会调整表的大小。)应至少为4*TREEIFY_THRESHOLD,以避免调整大小阈值和树化阈值之间的冲突。
 */
static final int MIN_TREEIFY_CAPACITY = 64;

/**
 * 基本hash bin节点,用于大多数条目。(TreeNode子类见下文,Entry子类见LinkedHashMap。)
 */
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;
    }
}

new HashMap,默认无参构造,负载因子0.75

public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // 这个是0.75f
    }
    /**
     * The number of times this HashMap has been structurally modified
     * Structural modifications are those that change the number of mappings in
     * the HashMap or otherwise modify its internal structure (e.g.,
     * rehash).  This field is used to make iterators on Collection-views of
     * the HashMap fail-fast.  (See ConcurrentModificationException).
     */
    transient int modCount;//记录修改次数

put方法

//put方法
public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
/**
 * 计算key.hashCode()并将哈希的高位扩展(XOR)到低位。因为该表使用了两个掩码的幂,所以仅在当前掩码之上以位为单位变化的哈希集总是会发生冲突。(已知的例子包括在小表中保存连续整数的浮点键集。)因此,我们应用了一种变换,将高位的影响向下扩展。比特扩展的速度、效用和质量之间存在权衡。由于许多常见的哈希集已经合理分布(因此不会从扩展中受益),并且因为我们使用树来处理箱中的大型冲突集,所以我们只需以最便宜的方式对一些移位的比特进行异或,以减少系统损失,并将最高比特的影响纳入其中,否则由于表绑定,这些比特将永远不会用于索引计算
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

首先通过hash方法,传入key计算出一个int类型的hash值。

这里为什么不直接用key.hashCode()的值呢?

key.hashCode()计算出一个hash值,然后赋值给h,h右移16位,然后两个做异或运算
计算的值右移16位,右移之前和右移之后的值进行异或^运算,得到最终的hashcode,这个最终的值时通过低位和高位一起异或运算算出来的。这样高位也参加到了计算中,高位都是0.

下面还有计算数组下标的
i = (n - 1) & hash,第一次n=16,做&运算,何为&运算,即都为1则为1。
比方15的二进制时是 0000 1111 而上面计算得到的hash值和这个做&运算,值在0-15之间。这样(n - 1) & hash计算是为了使均匀分布。0-15出现频率都差不多。hash值比较均匀,最后计算的i就比较均匀。为啥要n-1,如果16的话,做&运算得到结果就两种

然后调用putVal方法,入参事key的hash值,key,value,false,true

这里是put的核心方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
                   //定义tab,p,n,i,初始化一些变量
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //这里为啥不直接用table?性能问题,我们自己初始化变量是属于栈中,而table是堆中,不用每次从堆中去拿table。
        //第一次进来是null
        if ((tab = table) == null || (n = tab.length) == 0)
        //这里调用resize,初始化及扩容,第一次返回16
            n = (tab = resize()).length;//那=16
        //下面这个i是如何来的?i = (n - 1) & hash,算出数组下标,如果没有值,是null,就放到这里。
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        //如果这个位置不是null,这里就涉及到链表
        else {
        //如果这个位置上不是null,说明这个位置有东西
            Node<K,V> e; K k;
            //如果发现hash和key相等
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //直接赋值到e,下面不会走了
                e = p;
                //如果这个位置上的是TreeNode类型
            else if (p instanceof TreeNode)
            //进行红黑树的插入
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
            //不相等,就要用到链表,这里for循环,
            //如何加?通过Node对象的next属性
                for (int binCount = 0; ; ++binCount) {
                //binCount=0,有一个节点,所以下面要8-1=7,binCount=8
                //尾插法,找到尾节点,尾节点的next==null
                    if ((e = p.next) == null) {
                    //将新的节点给到next属性,完成链表插入
                        p.next = newNode(hash, key, value, null);
                        //如果bincount的大小>=8-1=7,binCount=7,链表有8个节点,但是你自己上面newNode还新增了一个,其实现在有9个节点
                        //为啥超过8个转红黑树,这个和红黑树的性能有关
                        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;
                }
            }
            //如果e不是null,
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                更新value
                    e.value = value;
                afterNodeAccess(e);
                //将原来老的value返回
                return oldValue;
            }
        }
        ++modCount;
        //统计++size,hashmap大小,和域值threshold(16*0.75)比较
        //不停往集合put,如果大于12(threshold)个,就会调用resize扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

    /**
     * 初始化或加倍表大小。如果为null,则根据字段阈值中的初始容量目标进行分配。否则,因为我们使用的是二次幂展开,所以每个bin中的元素必须保持在同一索引,或者在新表中以二次幂偏移量移动。
     *
     * @return the table
     */
    transient Node<K,V>[] table;
    int threshold;
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        //一开始时null
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                     //左移1位,翻倍
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
        //一开始0,走到这里执行
            newCap = DEFAULT_INITIAL_CAPACITY;//默认16(1>>4)
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//16*0.75=12这个和扩容有关系,扩容的一个域值
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;//第一次将12赋值给threshold
        @SuppressWarnings({"rawtypes","unchecked"})
        //这里开始创建Node,第一次newCap=16,这里创建出一个16大小的node数组
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        //将16给到table,table=16
        table = newTab;
        //老数组上面元素转到新数组上面去
        if (oldTab != null) {
        //遍历老数组
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                //如果老数组这个元素不是null
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    //如果为null,说明只有一个元素
                    if (e.next == null)
                    //重新计算放到新数组中
                        newTab[e.hash & (newCap - 1)] = e;
                    //判断是不是TreeNode
                    else if (e instanceof TreeNode)
                    //对TreeNode树进行拆分,转到新数组,不一定在一起。拆分后不一定还是树,这里各种情况,看节点对应的是高位还是低位。判断低位个数如果不超过6,转成链表(TreeNode转成Node)。否则还是TreeNode,然后判断高位低位,如果低位,不用动,如果有高位,说明树进行了拆分,重新生成红黑树。
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                    //是个链表,将链表转到新数组上面去,扩容后重新计算hash后下标不一定还是相同的,所以不能直接转到新数组,但是扩容后下标是有规律的。只有两种情况,低位和高位
                    //哪些节点是在低位链表上面,哪些节点是在高位链表上面
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            //e.hash & oldCap==0判断在低位还是高位,等于0在低位
                            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);
                        //低位链表放到newTab
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        //高位链表放到newTab
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;//第一次调用的最后返回16
    }

转红黑树的方法

final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        //MIN_TREEIFY_CAPACITY=64,判断数组长度是否小于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 {
            //将这个链表上面的Node节点遍历变成TreeNode节点,完成转换
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                //将prev也赋值,改成双向链表,方便去拿前一个节点
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
            //将TreeNode节点转成红黑树
                hd.treeify(tab);
        }
    }

红黑树查询删除等时间复杂度都是log(n),要快一点,提升查询性能
并不是超过8就一定转成红黑树,而是还要判断数组长度,64比较,小于64扩容
为啥要判断数组长度?和扩容有关,resize扩容,将链表拆分成两个短链表。

扩容,两个地方进行扩容
一个是计算hashmap大小大于12进行扩容
一个是链表长度大于8,不一定转成红黑树,而是通过判断数组长度是否小于64进行扩容

扩容先生成新数组,再把老数组上面元素放到新数组位置上

扩容,如果是TreeNode情况

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;
                }
            }
//如果低位不是null
            if (loHead != null) {
            //如果低位数量不超过6
                if (lc <= UNTREEIFY_THRESHOLD)
                //将TreeNode转成Node,转成了链表
                    tab[index] = loHead.untreeify(map);
                else {
                //如果超过,说明要用红黑树,
                    tab[index] = loHead;
                    //如果高位不是null,说明有高位,此时需要重新生成红黑树,如果没有高位,就不用走到treeify方法,用之前的就行。不需要重新再生成红黑树。
                    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);
                }
            }
        }

红黑树

  1. 根节点是黑色的;

  2. 每个叶子节点都是黑色的空节点(NIL),也就是说,叶子节点不存储数据;

  3. 任何相邻的节点都不能同时为红色,红色节点是被黑色节点隔开的;

  4. 每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点

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;;) {
            //如果是null,父节点,返回
                if ((xp = x.parent) == null) {
                    x.red = false;
                    return x;
                }
                //如果父节点是黑色,不用调整,返回root
                else if (!xp.red || (xpp = xp.parent) == null)
                    return root;
                //父节点是红色的情况,
                //父节点正好是xpp的左节点
                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);
                            }
                        }
                    }
                }
            }
        }

HashMap为什么用红黑树

R-B Tree。它是一种不严格的平衡二叉查找树
引入RB-Tree是功能、性能、空间开销的折中结果。
红黑是用非严格的平衡来换取增删节点时候旋转次数的降低,任何不平衡都会在三次旋转之内解决,而AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多。
就插入节点导致树失衡的情况,AVL和RB-Tree都是最多两次树旋转来实现复衡rebalance,旋转的量级是O(1)
删除节点导致失衡,AVL需要维护从被删除节点到根节点root这条路径上所有节点的平衡,旋转的量级为O(logN),而RB-Tree最多只需要旋转3次实现复衡,只需O(1),所以说RB-Tree删除节点的rebalance的效率更高,开销更小!

hashmap使用红黑树的原因是:这样可以利用链表对内存的使用率以及红黑树的高效检索,是一种很有效率的数据结构。AVL树是一种高度平衡的二叉树,所以查找的效率非常高,但是,有利就有弊,AVL树为了维持这种高度的平衡,就要付出更多代价。每次插入、删除都要做调整,复杂、耗时。对于有频繁的插入、删除操作的数据集合,使用AVL树的代价就有点高了。而且红黑树只是做到了近似平衡,并不严格的平衡,所以在维护的成本上,要比AVL树要低。所以,hashmap用红黑树。

红黑树相比avl树,在检索的时候效率其实差不多,都是通过平衡来二分查找。但对于插入删除等操作效率提高很多。红黑树不像avl树一样追求绝对的平衡,他允许局部很少的不完全平衡,这样对于效率影响不大,但省去了很多没有必要的调平衡操作,avl树调平衡有时候代价较大,所以效率不如红黑树,在现在很多地方都是底层都是红黑树的天下啦。

java8不是用红黑树来管理hashmap,而是在hash值相同的情况下(且重复数量大于8),用红黑树来管理数据。 红黑树相当于排序数据,可以自动的使用二分法进行定位,性能较高。一般情况下,hash值做的比较好的话基本上用不到红黑树。

AVL树用于自平衡的计算牺牲了插入删除性能,但是因为最多只有一层的高度差,查询效率会高一些。红黑树的高度只比高度平衡的AVL树的高度(log2n)仅仅大了一倍,在性能上却好很多。

HashMap为什么要转成树?为什么阈值是8?

当链表长度不断变长,肯定会对查询性能有一定的影响,所以才需要转成树。
选择8,是根据概率统计决定。

HashMap源码里有一段注解,大概意思是:
理想情况下使用随机的哈希码,容器中节点分布在hash桶中的频率遵循泊松分布(具体可以查看http://en.wikipedia.org/wiki/Poisson_distribution),按照泊松分布的计算公式计算出了桶中元素个数和概率的对照表,可以看到链表中元素个数为8时的概率已经非常小,再多的就更少了,所以原作者在选择链表元素个数时选择了8,是根据概率统计而选择的。
HashMap底层源码解析及红黑树分析
这里看到8的时候概率小的可怜了。

空间和时间的权衡
TreeNodes占用空间是普通Nodes的两倍,所以只有当bin包含足够多的节点时才会转成TreeNodes,而是否足够多就是由TREEIFY_THRESHOLD的值决定的。当bin中节点数变少时,又会转成普通的bin。并且我们查看源码的时候发现,链表长度达到8就转成红黑树,当长度降到6就转成普通bin。

为什么不用B+Tree

B+树在数据库中被应用的原因是其“矮胖”的特点,B+树的非叶子结点不存储数据,所以每个结点能存储的关键字更多。所以B+树更能应对大量数据的情况。Mysql就是用的B+Tree。
jdk1.7中的HashMap本来是数组+链表的形式,链表由于其查找慢的特点,所以需要被查找效率更高的树结构来替换。如果用B+树的话,在数据量不是很多的情况下,数据都会“挤在”一个结点里面。这个时候遍历效率就退化成了链表。

结论:b+树不属于二叉树,因为二叉查找树的查找效率是最高的,如果内存能装下完整的树,最好使用二叉查找树,b+树是退而求其次的方式。

所以就是根据数据量去选择,HashMap数据量不大,,没有必要用B+Tree。文章来源地址https://www.toymoban.com/news/detail-432856.html

到了这里,关于HashMap底层源码解析及红黑树分析的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 源码分析——HashMap(JDK1.8)源码+底层数据结构分析

    HashMap 主要用来存放键值对,它基于哈希表的Map接口实现,是常用的Java集合之一。 JDK1.8 之前 HashMap 由 数组+链表 组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突).JDK1.8 以后在解决哈希冲突时有了较大的变化,当链表长度大于阈

    2024年02月13日
    浏览(44)
  • 【C++】红黑树 --- map/set 底层

    红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是 Red 或 Black . 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出两倍,因而是接近平衡的;如下图: 每个结点不是红色就是黑色;

    2024年02月04日
    浏览(35)
  • 【C++】map与set容器——红黑树底层封装

    💭STL中,容器大概可分为两种类型——序列式容器和关联式容器。在前面的系列文章中,我们已经介绍了诸多序列式容器,如:vector、list、stack、queue等,它们以序列的形式存储数据。 💭而关联式容器也是一种非常重要的容器。标准的STL关联式容器分为set(集合)和map(映

    2023年04月11日
    浏览(39)
  • 线程池ThreadPoolExecutor底层原理源码分析

    ThreadPoolExecutor中提供了两种执行任务的方法: void execute(Runnable command) Future? submit(Runnable task) 实际上submit中最终还是调用的execute()方法,只不过会返回⼀个Future对象,用来获取任务执行结果: execute(Runnable command)方法执行时会分为三步: 注意:提交⼀个Runnable时,不管当前线程

    2024年02月06日
    浏览(64)
  • 【C++】红黑树的插入分析及验证

    红黑树 是一种二叉搜索树, 但在每个节点上增加一个存储位表示节点的颜色,可以是red或black, 通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保没有一条路径会比其他路径长处两倍,所以是接近平衡的 1. 每个结点不是红色就是黑色 2. 根节点是黑

    2024年02月05日
    浏览(47)
  • 【高阶数据结构】红黑树 {概念及性质;红黑树的结构;红黑树的实现;红黑树插入操作详细解释;红黑树的验证}

    红黑树(Red Black Tree) 是一种自平衡二叉查找树,在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。 AVL树 VS 红黑树 红黑树是

    2024年02月09日
    浏览(48)
  • 数据结构之进阶二叉树(二叉搜索树和AVL树、红黑树的实现)超详细解析,附实操图和搜索二叉树的实现过程图

    绪论​ “生命有如铁砧,愈被敲打,愈能发出火花。——伽利略”;本章主要是数据结构 二叉树的进阶知识,若之前没学过二叉树建议看看这篇文章一篇掌握二叉树,本章的知识从浅到深的 对搜索二叉树的使用进行了介绍和对其底层逻辑的实现进行了讲解 ,希望能对你有所

    2024年02月04日
    浏览(46)
  • HashMap源码解析

    成员变量定义了一些初始化相关和扩容相关的参数。 提供了四个构造方法,空参,设置容量,设置容量和负载因子,通过Map构造HashMap。除了最后一个,其他的都是只设置了容量大小和负载因子。 调用putVal,参数中第一个是计算key的hash值。 调用对象的hashCode方法,返回一个

    2024年02月08日
    浏览(40)
  • 【C++高阶(四)】红黑树深度剖析--手撕红黑树!

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:C++从入门到精通⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你学习C++   🔝🔝 如果说发明AVL树的人是天才,那么 发明红黑树的人可以称为天才中的 精英!为什么AVL树这么强大但是没啥 人用呢?就是因为红黑树比你还好

    2024年02月05日
    浏览(45)
  • openxr runtime Monado 源码解析 源码分析:整体介绍 模块架构 模块作用 进程 线程模型 整体流程

    monado系列文章索引汇总: openxr runtime Monado 源码解析 源码分析:源码编译 准备工作说明 hello_xr解读 openxr runtime Monado 源码解析 源码分析:整体介绍 模块架构 模块作用 进程 线程模型 整体流程 openxr runtime Monado 源码解析 源码分析:CreateInstance流程(设备系统和合成器系统)C

    2024年02月11日
    浏览(83)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包