源碼的魅力 - TreeMap 的工作原理（Android 7.1源碼）

簡介

由于HashMap與linkedHashMap都不能按照key的數(shù)據(jù)順序進行遍歷，所以后來就有了TreeMap。

怎么做到按照插入順序排序的呢

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

    public V put(K key, V value) {
        TreeMapEntry<K,V> t = root;
        if (t == null) {
            if (comparator != null) {
                if (key == null) {
                    comparator.compare(key, key);
                }
            } else {
                if (key == null) {
                    throw new NullPointerException("key == null");
                } else if (!(key instanceof Comparable)) {
                    throw new ClassCastException(
                            "Cannot cast" + key.getClass().getName() + " to Comparable.");
                }
            }

            root = new TreeMapEntry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        TreeMapEntry<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);
        }
        TreeMapEntry<K,V> e = new TreeMapEntry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

TreeMap存在一個參數(shù)為Comparator的構(gòu)造函數(shù)抠璃，在插入數(shù)據(jù)時默認是使用數(shù)據(jù)的默認比較器泌辫，否則使用比較器很钓，通過比較器比較的值挨队，如果相等則直接替換狈茉，如果不同則插入嘁字，使用紅黑樹維護整個結(jié)構(gòu)昨稼。

怎么獲取數(shù)據(jù)時是有序的呢

    abstract class PrivateEntryIterator<T> implements Iterator<T> {
        TreeMapEntry<K,V> next;
        TreeMapEntry<K,V> lastReturned;
        ...

        final TreeMapEntry<K,V> nextEntry() {
            TreeMapEntry<K,V> e = next;
            if (e == null)
                throw new NoSuchElementException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            next = successor(e);
            lastReturned = e;
            return e;
        }
    }

    //中序遍歷查找下一個節(jié)點
    static <K,V> TreeMapEntry<K,V> successor(TreeMapEntry<K,V> t) {
        if (t == null)
            return null;
        else if (t.right != null) {
            TreeMapEntry<K,V> p = t.right;
            while (p.left != null)
                p = p.left;
            return p;
        } else {
            TreeMapEntry<K,V> p = t.parent;
            TreeMapEntry<K,V> ch = t;
            while (p != null && ch == p.right) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }

通過PrivateEntryIterator遍歷器然后，通過中序遍歷返回數(shù)據(jù)拳锚，正是排序的數(shù)據(jù)假栓。