TreeMap

TreeMap定义

与LinkedHashMap不同，TreeMap不是继承于HashMap，而是继承于AbstractMap，归根到底，TreeMap实现的不是hash算法，而是二叉树算法；底层的数据存储也不是数组，而是链表实现的二叉树。二叉树数据结构决定了该map是一个按key进行排序排序的map。定义如下：

......

private final Comparator<? super K> comparator;

private transient Entry<K,V> root = null;

private transient int modCount = 0;

......

 

属性comparator

比较器，在二叉树中进行查找、插入指定的key节点时，就难免与left、parent和right节点的key进行比较，比较算法由comparator提供， 若comparator不为空，则执行该comparator的比较算法：

       int cmp = cpr.compare(key, t.key);

若comparator为空，则采用key自身的比较算法：

       cmp = k.compareTo(t.key);

从代码可以看出，当没有提供comparator 时，默认就会将key强制转换为Comparable，然后调用其 compareTo（）方法，这就要求key必须实现 Comparable接口，否则将发生ClassCastException。

 

属性root

root是一个用链表实现的二叉树，left.key<parent.key<right.key,具体实现代码如下：

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;

        Entry(K key, V value, Entry<K,V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

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

从代码中的” boolean color = BLACK;“可以看出，不仅是二叉树，还是一棵红黑树。红黑树近似平衡， 降低了对旋转的要求，提高了性能。

 

属性modCount

同HashMap一样，该属性用来记录map上的修改（put、remove、clear）次数，以便在对key进行迭代时判断是否发生了并发冲突。

 

 

遍历KeySet

KetSet的Iterator按照前序遍历的方式遍历二叉树中的Key，即从left到parent再到right，即第一个节点是最左边的节点，最后一个节点是最右边的一个节点，代码如下：

//获取第一个节点

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

//获取最后一个节点

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