欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java基礎(chǔ)之TreeMap詳解

 更新時間:2021年04月30日 10:56:43   作者:伏城之外  
這篇文章主要介紹了Java基礎(chǔ)之TreeMap詳解,文中有非常詳細(xì)的代碼示例,對正在學(xué)習(xí)java基礎(chǔ)的小伙伴們有非常好的幫助,需要的朋友可以參考下

一、寫在前面

TreeMap的底層數(shù)據(jù)結(jié)構(gòu)是紅黑樹,且TreeMap可以實現(xiàn)集合元素的排序。

所以TreeMap的源碼需要實現(xiàn):

1.紅黑樹的數(shù)據(jù)結(jié)構(gòu),以及紅黑樹的節(jié)點插入,刪除,以及紅黑樹的自平衡操作,如左旋,右旋,以及節(jié)點變色

2.紅黑樹需要支持按照指定的比較器進(jìn)行排序,或者進(jìn)行自然排序。

二、定義

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

TreeMap

繼承了AbstractMap

實現(xiàn)了NavigableMap,而NavigableMap接口繼承了SortedMap接口,SortedMap接口表示其實現(xiàn)類是一個有序集合

實現(xiàn)了Cloneable,所以支持對象克隆

實現(xiàn)了Serializable,所以支持對象序列化

三、成員變量

comparator

 /**
     * The comparator used to maintain order in this tree map, or
     * null if it uses the natural ordering of its keys.
     *
     * @serial
     */
    private final Comparator<? super K> comparator;

外部指定的比較器。在創(chuàng)建TreeMap對象時可以指定。如果指定了比較器,則TreeMap插入鍵值對時,按照comparator比較排序。 

root

 private transient Entry<K,V> root;

root指代TreeMap底層紅黑樹的根節(jié)點。 root的類型Entry<K,V>就是紅黑樹節(jié)點的類型。

紅黑樹數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)就依賴于Entry<K,V>

size

/**
     * The number of entries in the tree
     */
    private transient int size = 0;

 表示TreeMap集合中鍵值對個數(shù)。

modCount 

/**
     * The number of structural modifications to the tree.
     */
    private transient int modCount = 0;

表示TreeMap集合被結(jié)構(gòu)化修改的次數(shù)。用于迭代器迭代過程中檢測集合是否被結(jié)構(gòu)化修改,若是,則fail-fast。

四、內(nèi)部類

Entry<K,V>

Entry<K,V>是紅黑樹節(jié)點的代碼實現(xiàn),是實現(xiàn)紅黑樹數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。

    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;
 
        /**
         * Make a new cell with given key, value, and parent, and with
         * {@code null} child links, and BLACK color.
         */
        Entry(K key, V value, Entry<K,V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }
 
        /**
         * Returns the key.
         *
         * @return the key
         */
        public K getKey() {
            return key;
        }
 
        /**
         * Returns the value associated with the key.
         *
         * @return the value associated with the key
         */
        public V getValue() {
            return value;
        }
 
        /**
         * Replaces the value currently associated with the key with the given
         * value.
         *
         * @return the value associated with the key before this method was
         *         called
         */
        public V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }
 
        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
 
            return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
        }
 
        public int hashCode() {
            int keyHash = (key==null ? 0 : key.hashCode());
            int valueHash = (value==null ? 0 : value.hashCode());
            return keyHash ^ valueHash;
        }
 
        public String toString() {
            return key + "=" + value;
        }
    }

成員變量 

K key,V value分別是TreeMap集合中存儲的鍵值對的鍵和值

Entry<K,V> left 代表當(dāng)前節(jié)點的左子節(jié)點

Entry<K,V> right 代表當(dāng)前節(jié)點的右子節(jié)點

Entry<K,V> parent 代表當(dāng)前節(jié)點的父節(jié)點

boolean color 代表當(dāng)前節(jié)點的顏色,默認(rèn)是黑色,為true

構(gòu)造器

Entry<K,V>只提供了一個構(gòu)造器 Entry(K key, V value, Entry<K,V> parent)

即:創(chuàng)建一個紅黑樹節(jié)點,只需要指定其存儲的鍵值信息,以及其父節(jié)點引用。不需要指定左孩子和右孩子,以及顏色。

成員方法

提供了getKey()方法返回當(dāng)前節(jié)點的key值。

提供了getValue(),setValue(V v)分別用于獲取Value,以及覆蓋Value后返回oldValue

重寫了equals()方法用于判斷兩個紅黑樹節(jié)點是否相同。邏輯是:兩個紅黑樹節(jié)點的key要么都為null,要么equals結(jié)果true,且,value要么都為null,要么equals結(jié)果為true。

重寫了hashCode()方法。

重寫了toString()方法。

五、構(gòu)造器

public TreeMap()

    public TreeMap() {
        comparator = null;
    }

無參構(gòu)造器,即不指定比較器的構(gòu)造器。

注意,此時插入集合的鍵值對的key的類型必須實現(xiàn)Comparable接口,即提供自然排序能力,否則會報錯類型轉(zhuǎn)換異常。 

public TreeMap(Comparator<? super K> comparator)

 public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

指定比較器的構(gòu)造器。

指定的比較器用于比較key,且comparator指定了泛型,即比較器比較的元素的類型必須是K或者K的父類類型。

public TreeMap(Map<? extends K, ? extends V> m)

    public TreeMap(Map<? extends K, ? extends V> m) {
        comparator = null;
        putAll(m);
    }

 將非TreeMap集合轉(zhuǎn)為TreeMap集合構(gòu)造器

public TreeMap(SortedMap<K, ? extends V> m)

 public TreeMap(SortedMap<K, ? extends V> m) {
        comparator = m.comparator();
        try {
            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
    }

將有序Map集合轉(zhuǎn)為TreeMap集合

六、成員方法

public V get(Object key)

    public V get(Object key) {
        Entry<K,V> p = getEntry(key);
        return (p==null ? null : p.value);
    }

TreeMap的get方法用于獲取指定key的value。如果指定key沒有對應(yīng)的紅黑樹節(jié)點,則返回null,否則返回對應(yīng)紅黑樹節(jié)點的value。

可以看到get方法實現(xiàn)依賴于getEntry(Object key)方法。

getEntry(Object key)方法是根據(jù)指定key找對應(yīng)的紅黑樹節(jié)點并返回該節(jié)點。

final Entry<K,V> getEntry(Object key)

    final Entry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        if (comparator != null)//如果外部指定了比較器
            return getEntryUsingComparator(key);//則使用指定比較器來查找
        if (key == null)//如果外部沒有指定比較器,且要查找的key為null,則拋出空指針異常
            throw new NullPointerException();
        @SuppressWarnings("unchecked")//此時外部沒有指定構(gòu)造器,且要查的Key不為null
            Comparable<? super K> k = (Comparable<? super K>) key;//檢查Key的類型是否實現(xiàn)了Comparable接口,即是否實現(xiàn)了自然排序,如果實現(xiàn)了,則此處可以強轉(zhuǎn)成功,否則會報錯類型轉(zhuǎn)換異常
        Entry<K,V> p = root;
        while (p != null) {//從紅黑樹根節(jié)點開始使用key本身的自然排序進(jìn)行比較
            int cmp = k.compareTo(p.key);
            if (cmp < 0)//如果要查找的key小于樹節(jié)點的key,則說明要找的key在當(dāng)前節(jié)點的左子樹上,則下次遍歷從左子樹的根節(jié)點開始
                p = p.left;
            else if (cmp > 0)//如果要查找的key大于樹節(jié)點的key,則說明要找的key在當(dāng)前節(jié)點的右子樹上,則下次遍歷從右子樹的根節(jié)點開始
                p = p.right;
            else//如果要查找的key等于樹節(jié)點的key,則該節(jié)點就是要找的,直接返回該節(jié)點
                return p;
        }
        return null;//如果上面遍歷沒有找到對應(yīng)Key的節(jié)點,則返回null
    }
 
 
    final Entry<K,V> getEntryUsingComparator(Object key) {//使用指定比較器來查找,邏輯基本和自然排序查找一樣,只是這里使用了比較器排序查找
        @SuppressWarnings("unchecked")
            K k = (K) key;
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = cpr.compare(k, p.key);
                if (cmp < 0)
                    p = p.left;
                else if (cmp > 0)
                    p = p.right;
                else
                    return p;
            }
        }
        return null;
    }

 public V put(K key, V value)

public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check
 
            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = 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)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }
final int compare(Object k1, Object k2) {
        return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
            : comparator.compare((K)k1, (K)k2);
    }
public V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

  TreeMap的put方法用于插入一個鍵值對,

當(dāng)插入的key在集合中不存在時,則put表示新增鍵值對,并返回null;

當(dāng)插入的key在集合中存在時,則put表示覆蓋已存在key對應(yīng)的value,并返回老value。

private void fixAfterInsertion(Entry<K,V> x)

  private void fixAfterInsertion(Entry<K,V> x) {//x是被插入的紅黑樹節(jié)點
        x.color = RED;//默認(rèn)被插入的節(jié)點都是紅色
 
        while (x != null && x != root && x.parent.color == RED) {//如果被插入節(jié)點不是根節(jié)點
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                Entry<K,V> y = rightOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == rightOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateLeft(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {
                Entry<K,V> y = leftOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == leftOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
        root.color = BLACK;//如果被插入的節(jié)點是根節(jié)點,則節(jié)點顏色改為黑色
    }

fixAfterInsertion方法用于:當(dāng)TreeMap插入紅黑樹節(jié)點后,導(dǎo)致紅黑樹不平衡時,TreeMap保持自平衡的自旋和變色操作。

該方法的入?yún)⒕褪遣迦氲募t黑樹節(jié)點。

到此這篇關(guān)于Java基礎(chǔ)之TreeMap詳解的文章就介紹到這了,更多相關(guān)Java TreeMap詳解內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • NoHttpResponseException問題排查解決記錄分析

    NoHttpResponseException問題排查解決記錄分析

    這篇文章主要為大家介紹了NoHttpResponseException問題排查解決記錄分析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2023-08-08
  • Mybatis如何通過注解開啟使用二級緩存

    Mybatis如何通過注解開啟使用二級緩存

    這篇文章主要介紹了Mybatis基于注解開啟使用二級緩存,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2019-11-11
  • SpringBoot使用POI進(jìn)行Excel下載

    SpringBoot使用POI進(jìn)行Excel下載

    這篇文章主要為大家詳細(xì)介紹了SpringBoot使用POI進(jìn)行Excel下載,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2019-09-09
  • Java設(shè)計模式之適配器模式的實現(xiàn)

    Java設(shè)計模式之適配器模式的實現(xiàn)

    這篇文章主要介紹了Java設(shè)計模式之適配器模式的實現(xiàn),適配器模式(Adapter Pattern)是作為兩個不兼容的接口之間的橋梁,這種類型的設(shè)計模式屬于結(jié)構(gòu)型模式,它結(jié)合了兩個獨立接口的功能,需要的朋友可以參考下
    2023-11-11
  • JAVA中使用JSON進(jìn)行數(shù)據(jù)傳遞示例

    JAVA中使用JSON進(jìn)行數(shù)據(jù)傳遞示例

    本篇文章主要介紹了JAVA中使用JSON進(jìn)行數(shù)據(jù)傳遞示例,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-01-01
  • 如何在logback日志配置里獲取服務(wù)器ip和端口

    如何在logback日志配置里獲取服務(wù)器ip和端口

    這篇文章主要介紹了如何在logback日志配置里獲取服務(wù)器ip和端口的方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-08-08
  • 搭建SpringBoot項目三種方式(圖文教程)

    搭建SpringBoot項目三種方式(圖文教程)

    Springboot作為當(dāng)下最主流的java開發(fā)框架,已成為IT從業(yè)人員的入門必備技能,本文主要介紹了搭建SpringBoot項目三種方式,感興趣的可以了解一下
    2023-09-09
  • SpringBoot項目打jar包與war包的詳細(xì)步驟

    SpringBoot項目打jar包與war包的詳細(xì)步驟

    SpringBoot和我們之前學(xué)習(xí)的web應(yīng)用程序不一樣,其本質(zhì)上是一個 Java應(yīng)用程序,那么又如何部署呢?這篇文章主要給大家介紹了關(guān)于SpringBoot項目打jar包與war包的詳細(xì)步驟,需要的朋友可以參考下
    2023-02-02
  • Java兩個變量的互換(不借助第3個變量)具體實現(xiàn)方法

    Java兩個變量的互換(不借助第3個變量)具體實現(xiàn)方法

    這篇文章主要介紹了Java兩個變量的互換(不借助第3個變量)具體實現(xiàn)方法,需要的朋友可以參考下
    2014-02-02
  • 詳解maven中央倉庫連不上的解決辦法

    詳解maven中央倉庫連不上的解決辦法

    這篇文章主要介紹了詳解maven中央倉庫連不上的解決辦法,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-09-09

最新評論