TreeMap源码阅读

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

什么是AbstractMap? This class provides a skeletal(骨架) implementation of the Map interface, to minimize the effort required to implement this interface. To implement an unmodifiable map, the programmer needs only to extend this class and provide an implementation for the entrySet method, which returns a set-view of the map’s mappings. This set should not support the add or remove methods, and its iterator should not support the remove method.
什么是SortedMap? A {@link SortedMap} extended with navigation methods returning the closest matches for given search targets. Methods {@code lowerEntry}, {@code floorEntry}, {@code ceilingEntry}, and {@code higherEntry} return {@code Map.Entry} objects associated with keys respectively less than, less than or equal, greater than or equal, and greater than a given key, returning {@code null} if there is no such key. Similarly, methods {@code lowerKey}, {@code floorKey}, {@code ceilingKey}, and {@code higherKey} return only the associated keys. All of these methods are designed for locating, not traversing entries.

sortedMap中的方法包括

SortedMap
comparator
entrySet
firstKey
headMap: Returns a view of the portion of this map whose keys are strictly less than {@code toKey}.
keySet
lastKey: the last (highest) key currently in this map
subMap(fromKey,toKey): 区间内的Entry
tailMap(fromKey): Returns a view of the portion of this map whose keys are greater than or equal to {@code fromKey}.
values

NavigableMap接口是专门为TreeMap和ConcurrentSkipListMap设计的(只找到了这两个类实现该接口), 其中的方法包括

NavigableMap
ceilingEntry
ceilingKey
descendingKeySet
descendingMap
firstEntry
floorEntry
floorKey
headMap
headMap
higherEntry
higherKey
lastEntry
lowerEntry
lowerKey
navigableKeySet
pollFirstEntry
pollLastEntry
subMap
subMap
tailMap
tailMap

接口和父类看完后, 首先看一下最简单的get方法如何实现:

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

final Entry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return 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;
    }

再看getCeilingEntry方法(求Entry.key>=key). 该方法与getHigherEntry(求Entry.key>key)几乎相同.

final Entry<K,V> getCeilingEntry(K key) {
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = compare(key, p.key);
            if (cmp < 0) {
                if (p.left != null)
                    p = p.left;
                else
                    return p;
            } else if (cmp > 0) {
                if (p.right != null) {
                    p = p.right;
                } else {
                    Entry<K,V> parent = p.parent;
                    Entry<K,V> ch = p;
                    while (parent != null && ch == parent.right) {
                        ch = parent;
                        parent = parent.parent;
                    }
                    return parent;
                }
            } else
                return p;
        }
        return null;
    }

compare方法,如果有comparator,就用指定的比较器. 不然就用默认比较器, 通篇均是这种比较方法.

final int compare(Object k1, Object k2) {
        return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
            : comparator.compare((K)k1, (K)k2);
    }

再看put方法, 先用比较器判断插入位置, 然后插入并根据红黑树调整树形结构.

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;
    }

CODE ICU

Code Recording 就是好玩

TreeMap源码阅读