天天看點

一起來看源代碼-01TreeMap添加操作

本文作者:黃海燕,叩丁狼進階講師。原創文章,轉載請注明出處。

##前言

之前很多小夥伴問我怎麼看源代碼,還有就是越來越多的程式員都想要看源代碼,搞懂底層原理,但是感覺源代碼非常的晦澀難懂,不夠直接和清晰,是以我希望這篇文章能夠快速帶同學們看懂java源碼,更加深入的學習java,幫助小夥伴們節約學習的時間成本.

##1.樹的介紹

  • 什麼是樹結構?其實就是一個節點下面有多個子節點,我們稱之為樹結構,如下圖:
  • 普通節點:擁有子節點的節點。
  • 葉子節點:沒有子節點的節點。
一起來看源代碼-01TreeMap添加操作

什麼是二叉樹?

  • 二叉樹就是一個節點最多隻能有2個子節點,分為左節點和右節點,如下圖:
    一起來看源代碼-01TreeMap添加操作

什麼是排序二叉樹?

  • 若左子樹不為空,則左子樹所有節點的值小于根節點的值。
  • 若右子樹不為空,則右子樹所有節點的值大于根節點的值。

    如圖:

    一起來看源代碼-01TreeMap添加操作

什麼是紅黑樹?

紅黑樹其實是一個平衡排序二叉樹,屬于查詢高效的樹結構.請看下圖:

一起來看源代碼-01TreeMap添加操作

查詢元素6普通的二叉樹需要操作6次,紅黑樹隻需要操作4次,是以紅黑樹查詢更加高效.

##1.TreeMap的結構介紹

###1.1 結構關系

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable{
           

繼承關系:

  • 父類AbstractMap,讓子類擁有基本Map的方法,比如增(put)删(remove)查(get)等方法.

實作關系:

  • NavigableMap:父接口為SortedMap,是以NavigableMap為可排序接口,表示TreeMap但是一個排序的Map:
  • Cloneable:标記型的接口,内部都沒有方法和屬性,實作 Cloneable來表示該對象能被克隆,能使用Object.clone()方法。如果沒有實作 Cloneable的類對象調用clone()就會抛出CloneNotSupportedException。
  • Serializable:标記型的接口,内部都沒有方法和屬性,實作Serializable表示可進行序列化和反序列化,表示能夠使用在ObjectOutputStream.writeObject())和ObjectInputStream.readObject()

###1.2 基本成員組成

/**
     * 比較器:類似于一個"裁判",用于比較插入對象和樹節點的内容大小
     * 因為TreeMap是一個紅黑樹,紅黑樹是一個排序二叉樹,插入元素的時候需要進行排序,排序可以使用比較器中的方式排序
     */
    private final Comparator<? super K> comparator;
    /**
     *  根節點
     */
    private transient Entry<K,V> root;
    /**
     * 樹的元素個數
     */
    private transient int size = 0;
    /**
     * 操作次數:增加和删除操作數都會加1,用于控制并發修改異常
     */
    private transient int modCount = 0;
           

通過root根節點可以看出一個節點(元素)就是一個Entry對象,是以一個節點(元素)中包含多個資料.結構如下:

static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;//鍵
        V value;//值
        Entry<K,V> left;//左節點
        Entry<K,V> right;//右節點
        Entry<K,V> parent;//父節點
        boolean color = BLACK;//顔色
           

節點表示如下:

一起來看源代碼-01TreeMap添加操作

###1.3添加操作:

public V put(K key, V value) {
        Entry<K, V> t = root;//和插入節點進行比較的樹節點
        //根節點為空
        if (t == null) {
            compare(key, key); //key比key,自己比較自己,目的是想要檢查類型,確定傳入了比較器或者是key實作了可比較接口
            //建立了一個沒有父節點的新的節點,作為根節點
            root = new Entry<>(key, value, null);
            size = 1;//元素個數為1
            modCount++;//操作數+1
            return null;//傳回空,根節點添加結束
        }
        int cmp;//表示比較結果
        Entry<K, V> parent;
        // cpr臨時表示比較器
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {//比較器不為空,就使用比較器比較元素
            do {
                parent = t;//父節點為t
                cmp = cpr.compare(key, t.key);//通過比較器對key和樹節點比較得到比較結果
                if (cmp < 0)//比較結果小于0,表示插入的元素比樹節點小
                    t = t.left;//t往左走
                else if (cmp > 0)//比較結果大于0,表示插入的元素比樹節點大
                    t = t.right;//t往右走
                else//cmp比較結果為0,覆寫節點中的value
                    return t.setValue(value);
            } while (t != null);//直到t為空停下來,保證插入的是節點
        } else {//比較器為空就使用元素中的比較方法
            if (key == null)//插入的元素key為空,沒辦法和樹結構中的元素比較,抛出空指針異常
                throw new NullPointerException();
            /*
             *  key進行強轉,看一下key是否實作了Comparable接口,是否存在compareTo方法,
             *  如果沒有實作接口,也就不确定有沒有compareTo方法了,沒辦法進行比較了
             */
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;//父節點為t
                cmp = k.compareTo(t.key);//通過節點中的比較方法比較插入節點和樹節點的大小
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);//直到沒有節點可以比較
        }
        Entry<K, V> e = new Entry<>(key, value, parent);
        if (cmp < 0)//如果比較結果小于0插入左邊
            parent.left = e;
        else
            parent.right = e;//否則插入右邊
        fixAfterInsertion(e);//對樹進行自平衡
        size++;
        modCount++;
        return null;
    }
           

###1.4 元素插入後對樹進行自平衡

紅黑樹的自平衡規則:(目标就是黑色節點平衡)
  • 每個節點都隻能是紅色或者黑色
  • 根節點是黑色
  • 每個葉節點(空節點)是黑色的。
  • 如果一個結點是紅的,則它兩個子節點都是黑的。也就是說在一條路徑上不能出現相鄰的兩個紅色結點。
  • 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。
private void fixAfterInsertion(Entry<K, V> x) {//x表示插入的節點,
        x.color = RED;//設定插入的節點為紅色
        //當x不為空,x不為根節點,x的父節點為紅色就需要進行平衡
        while (x != null && x != root && x.parent.color == RED) {
            //x的父節點等于x的爺爺節點的左邊,其實就是說x的父節點是否屬于左節點
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                //擷取x的爺爺節點的右節點
                Entry<K, V> y = rightOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {//爺爺節點的右節點為紅色
                    setColor(parentOf(x), BLACK);//将x的父節點設定為黑色
                    setColor(y, BLACK);//x父節點的兄弟節點設定為黑色
                    setColor(parentOf(parentOf(x)), RED);//爺爺節點設定為紅色
                    x = parentOf(parentOf(x));//x指向原來的爺爺節點,目的是為了繼續往上修改顔色
                } else {//不為紅色,也就是子節點和父節點的顔色出現沖突
                    //如果x等于父節點的右節點
                    if (x == rightOf(parentOf(x))) {
                        //操作的x為x的父節點
                        x = parentOf(x);
                        //左自旋,旋轉後x為原來x的子節點
                        rotateLeft(x);
                    }
                    //x的父節點設定為黑色
                    setColor(parentOf(x), BLACK);
                    //x的爺爺節點設定為紅色
                    setColor(parentOf(parentOf(x)), RED);
                    //右自旋
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {
                //y為爺爺節點的左節點(父節點的兄弟節點)
                Entry<K, V> y = leftOf(parentOf(parentOf(x)));
                //如果y的顔色為紅色
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);//父節點設定為黑色
                    setColor(y, BLACK);//y設定為黑色
                    setColor(parentOf(parentOf(x)), RED);//爺爺節點設定為紅色
                    x = parentOf(parentOf(x));//x指向原來的爺爺節點,目的是為了繼續往上修改顔色
                } else {
                    //如果父節點的左節點為x
                    if (x == leftOf(parentOf(x))) {
                        //x為父節點
                        x = parentOf(x);
                        //右自旋,旋轉後x為原來x的子節點
                        rotateRight(x);
                    }
                    setColor(parentOf(x), BLACK);//父節點設定為黑色
                    setColor(parentOf(parentOf(x)), RED);//爺爺節點設定為紅色
                    rotateLeft(parentOf(parentOf(x)));//左自旋
                }
            }
        }
        root.color = BLACK;//保證根節點必須為黑色
    }
           

###1.5左自旋

private void rotateLeft(Entry<K, V> p) {
        //p不為空
        if (p != null) {
            //r表示p的右節點
            Entry<K, V> r = p.right;
            //将r的左節點 指派給 p的有右節點
            p.right = r.left;
            //如果r的左節點不為空
            if (r.left != null)
                //r的左節點的父節點為p
                r.left.parent = p;
            //r的父節點為p的父節點
            r.parent = p.parent;
            //如果p的父節點為空
            if (p.parent == null)
                //r作為根節點
                root = r;
            //如果p的父節點的左節點等于p,說明p為父節點的左節點
            else if (p.parent.left == p)
                //p的父節點的左節點為r
                p.parent.left = r;
            else
                //p的父節點的左節點為r
                p.parent.right = r;
            //r的左節點為p
            r.left = p;
            //p的父節點為r
            p.parent = r;
        }
    }
           

###1.6右自旋

private void rotateRight(Entry<K, V> p) {
        //p不為空
        if (p != null) {
            //l表示p的左節點
            Entry<K, V> l = p.left;
            //p的左節點指向l的右節點
            p.left = l.right;
            //如果l的右節點不為空
            if (l.right != null)
                //l的右節點的父節點為p
                l.right.parent = p;
            //l的父節點指向p的父節點
            l.parent = p.parent;
            //如果p的父節點為空
            if (p.parent == null)
                //l為根節點
                root = l;
            //如果p的父節點的右節點為p
            else if (p.parent.right == p)
                //p的父節點的右節點為l
                p.parent.right = l;
            else
                //p的父節點的左節點為l
                p.parent.left = l;
            //l的右節點指向p
            l.right = p;
            //p的父節點指向l
            p.parent = l;
        }
    }
           

###1.7案例示範:

示範代碼如下:

一起來看源代碼-01TreeMap添加操作

代碼執行步驟如下:

一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作
一起來看源代碼-01TreeMap添加操作