说明：基于jdk1.7源码
TreeMap是基于红黑树实现的，关于红黑树的介绍可以参考：排序二叉树、平衡二叉树和红黑树
一、概述
Map接口的实现有HashMap、LinkedHashMap、TreeMap等。
HashMap不保证数据有序
LinkedHashMap保证数据可以保持插入顺序
而如果希望Map可以保持key的大小顺序的时候，我们就需要利用TreeMap了。
二、源码分析
1.节点的定义
每个节点由K，V，左右子节点，父节点组成，并且初始颜色为黑色
/** * 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 K key; //V 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. * 使用指定的key，value和所属的父节点来创建一个节点，颜色为黑色。其子节点为空。 */ 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; } /** * Replaces the value currently associated with the key with the given value. * 为key设置新值。并返回旧值 */ public V setValue(V value) { V oldValue = this.value; this.value = value; return oldValue; } /** * 比较节点是否相等(类型、key、value三者都相同，才相等) */ public boolean equals(Object o) { //先判断类型是否相同 if (!(o instanceof Map.Entry)) return false; Map.Entry<?,?> e = (Map.Entry<?,?>)o; //然后判断key和value是否分别都相同。 return valEquals(key,e.getKey()) && valEquals(value,e.getValue()); } /** * 计算节点的hash码 */ public int hashCode() { //计算key的hash码 int keyHash = (key==null ? 0 : key.hashCode()); //计算value的hash码 int valueHash = (value==null ? 0 : value.hashCode()); //按位异或 return keyHash ^ valueHash; } public String toString() { return key + "=" + value; } }
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); } //构造器(使用传入的Map的比较器) 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) { } }
3.put操作
/** * 0.首次添加：直接以传入的key，value来建立根节点。 * 1.非首次添加：查找待插入节点要挂载的父节点位置:从根节点开始依次将待插入节点和节点进行比较，直到找到合适的插入位置(父节点) * ①.若使用了比较器，则使用比较器进行比较 * ②.若未使用比较器，则使用每个节点自己的比较功能比较 * 2.使用传入的key，value创建新节点，并将其挂载到插入位置节点处。 * 3.插入后修复。重新调整树结构和颜色，以满足红黑树的要求 */ public V put(K key, V value) { Entry<K,V> t = root; //0.首次添加。以<key，value>来建立根节点 if (t == null) { //key的类型检查和非空检查 compare(key, key); // type (and possibly null) check root = new Entry<>(key, value, null); size = 1; modCount++; return null;//返回旧节点，显然为空 } //1.说明是非首次添加 int cmp; Entry<K,V> parent; // split comparator and comparable paths Comparator<? super K> cpr = comparator; //1①比较器不为空。从根节点开始查找，使用比较器进行比较，直到找到插入位置 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); }//1②比较器为空。从根节点开始查找，使用节点自身的比较功能进行比较 ，直到找到插入位置 else { if (key == null) throw new NullPointerException(); 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); } //2.使用传入的key，value创建节点,并将其挂到合适的父节点下 Entry<K,V> e = new Entry<>(key, value, parent); if (cmp < 0) parent.left = e; else parent.right = e; //3.插入后修复 fixAfterInsertion(e); size++; modCount++; return null; } /** From CLR */ private void fixAfterInsertion(Entry<K,V> x) { x.color = RED; while (x != null && x != root && x.parent.color == RED) { 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; }
4.get操作
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); //否则，说明使用的是key的自然顺序。 //不允许键为空，否则抛出异常 if (key == null) throw new NullPointerException(); Comparable<? super K> k = (Comparable<? super K>) key;//【能强转，说明key本身就实现了Camparable接口】 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; }
总结
1.什么是红黑树？
2.TreeMap中比较器的作用？
TreeMap使用比较器来维持元素的顺序。
在构造TreeMap时，如果传入了比较器或者带比较功能的Map，则使用比较器来比较元素。否则，比较时使用元素自身的比较功能。
3.put操作的实现？get操作的实现？
4.元素是否允许null？
key为null时会抛出NullPointerException