java源码分析05-TreeMap

Myth丶恋晨 2022-08-10 03:57 262阅读 0赞

说什么王权富贵，坚持！

今天，我们来看下TreeMap集合。作为Map集合中的一员大将，她的职责还是很大的，

除了常见的存储键值对和快速查找，她还有很多技能，例如有序的迭代序列，范围查找...,那么，她

到底是怎么拥有这么大的魅力的呢？我迫不及待地想深入了解她。

范围查找让我们想到了Mysql中的limit或者Oracle中的rownum的使用方法，例如查找某段时间内的

记录等

1.类结构

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

![Center][]

![Center 1][]

2.内部结构解析

构造器

public TreeMap() {
            comparator = null;
        }
     public TreeMap(Comparator<? super K> comparator) {
            this.comparator = comparator;
        }
    public TreeMap(Map<? extends K, ? extends V> m) {
            comparator = null;
            putAll(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) {
            }
        }

上述代码表名：第一，如果没有传入比较器，那么会采用默认的比较器；第二，如果传入了比较器，则

按照自定义的方式排序。默认的比较器是自然顺序，例如1,2,3...或者按照字母顺序排列。第三，如果传入的

是已排序的Map，首先获取她的比较器实例。

public void putAll(Map<? extends K, ? extends V> map) {
            int mapSize = map.size();
            if (size==0 && mapSize!=0 && map instanceof SortedMap) {
                Comparator c = ((SortedMap)map).comparator();
                if (c == comparator || (c != null && c.equals(comparator))) {
                    ++modCount;
                    try {
                        buildFromSorted(mapSize, map.entrySet().iterator(),
                                        null, null);
                    } catch (java.io.IOException cannotHappen) {
                    } catch (ClassNotFoundException cannotHappen) {
                    }
                    return;
                }
            }
            super.putAll(map);
        }

增删改查

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

上述代码告诉我们，第一，key不为空，否则抛出空指向异常；其次，节点的存储采用树的

形式（红黑树），通过比较器来判断存储在左子节点还是右子节点；第三，节点的查询也是通过

树的遍历，由于是二叉排序树，所以根据比较器来判断是在左子节点还是右子节点；

public boolean containsKey(Object key) {
            return getEntry(key) != null;
        }

是否包含也是通过getEntry方法来判断。

final Entry<K,V> getFirstEntry() {
            Entry<K,V> p = root;
            if (p != null)
                while (p.left != null)
                    p = p.left;
            return p;
        }

第一个结点的获取，通过查找根节点的左子节点，并且一直查找左子节点，直到该节点的

左子节点为空。

/**
         * @since 1.6
         */
        public Map.Entry<K,V> pollFirstEntry() {
            Entry<K,V> p = getFirstEntry();
            Map.Entry<K,V> result = exportEntry(p);
            if (p != null)
                deleteEntry(p);
            return result;
        }

弹出首节点，首先找到第一个结点，

public Set<K> keySet() {
            return navigableKeySet();
        }

public NavigableSet<K> navigableKeySet() {
            KeySet<K> nks = navigableKeySet;
            return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
        }

public NavigableSet<K> descendingKeySet() {
            return descendingMap().navigableKeySet();
        }

获取map集合，包括升序和降序方式

public Map.Entry<K,V> pollFirstEntry() {
            Entry<K,V> p = getFirstEntry();
            Map.Entry<K,V> result = exportEntry(p);
            if (p != null)
                deleteEntry(p);
            return result;
        }

/**
         * Delete node p, and then rebalance the tree.
         */
        private void deleteEntry(Entry<K,V> p) {
            modCount++;
            size--;
    
            // If strictly internal, copy successor's element to p and then make p
            // point to successor.
            if (p.left != null && p.right != null) {
                Entry<K,V> s = successor(p);
                p.key = s.key;
                p.value = s.value;
                p = s;
            } // p has 2 children
    
            // Start fixup at replacement node, if it exists.
            Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    
            if (replacement != null) {
                // Link replacement to parent
                replacement.parent = p.parent;
                if (p.parent == null)
                    root = replacement;
                else if (p == p.parent.left)
                    p.parent.left  = replacement;
                else
                    p.parent.right = replacement;
    
                // Null out links so they are OK to use by fixAfterDeletion.
                p.left = p.right = p.parent = null;
    
                // Fix replacement
                if (p.color == BLACK)
                    fixAfterDeletion(replacement);
            } else if (p.parent == null) { // return if we are the only node.
                root = null;
            } else { //  No children. Use self as phantom replacement and unlink.
                if (p.color == BLACK)
                    fixAfterDeletion(p);
    
                if (p.parent != null) {
                    if (p == p.parent.left)
                        p.parent.left = null;
                    else if (p == p.parent.right)
                        p.parent.right = null;
                    p.parent = null;
                }
            }
        }

如果弹出第一个结点，不仅仅包含删除第一个节点，还需要使红黑树达到新的平衡。

范围查找

public SortedMap<K,V> subMap(K fromKey, K toKey) {
            return subMap(fromKey, true, toKey, false);
        }

public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                                        K toKey,   boolean toInclusive) {
            return new AscendingSubMap(this,
                                       false, fromKey, fromInclusive,
                                       false, toKey,   toInclusive);
        }

public SortedMap<K,V> headMap(K toKey) {
            return headMap(toKey, false);
        }

public SortedMap<K,V> tailMap(K fromKey) {
            return tailMap(fromKey, true);
        }

红黑树

// Red-black mechanics
    
        private static final boolean RED   = false;
        private static final boolean BLACK = true;
    
        /**
         * Node in the Tree.  Doubles as a means to pass key-value pairs back to
         * user (see Map.Entry).
         */
    
        static final class Entry<K,V> implements Map.Entry<K,V> {
            K key;
            V value;
            Entry<K,V> left = null;
            Entry<K,V> right = null;
            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;
            }

TreeMap采用红黑树结构，这是一种自平衡二叉树。

/** From CLR */
        private void rotateLeft(Entry<K,V> p) {
            if (p != null) {
                Entry<K,V> r = p.right;
                p.right = r.left;
                if (r.left != null)
                    r.left.parent = p;
                r.parent = p.parent;
                if (p.parent == null)
                    root = r;
                else if (p.parent.left == p)
                    p.parent.left = r;
                else
                    p.parent.right = r;
                r.left = p;
                p.parent = r;
            }
        }

左旋

[Center]: /images/20220731/837acf678c234c35b0b346912f9dcb41.png
[Center 1]: /images/20220731/acd9491d0a3345d1985236ff9ae9be7c.png