JDK源码-TreeMap

1，TreeMap：

    -1，基于红黑树的实现。TreeMap根据创建时的顺序或者根据提供的Comparator进行排序，具体决定于使用的构造方法。提供Conparator方法后，判断对象相等也会基于此方法。

    -2，containsKey，get，put和remove方法消耗log(n)的时间复杂度。

/**
 *
 * @(#) Main.java
 * @Package com.treeMap
 * 
 * Copyright © JING Corporation. All rights reserved.
 *
 */
 
package com.treeMap;
 
import java.util.Comparator;
import java.util.TreeMap;
 
/**
 * 类描述：
 * 
 * @author: Jing History: Jan 23, 2015 9:32:46 AM Jing Created.
 * 
 */
public class Main {
 
	public static void main(String[] args) {
 
		TreeMap<Person, Integer> persons = new TreeMap<Person, Integer>(
				new Comparator<Person>() {
 
					@Override
					public int compare(Person o1, Person o2) {
 
						return o1.age - o2.age;
					}
				});
 
		Person p1 = new Person("lisi1", 3);
		Person p2 = new Person("lisi2", 31);
//		Person p3 = new Person("lisi3", 3);
//		Person p3 = new Person("lisi3", 15);
		Person p3 = new Person("lisi1", 4);
		persons.put(p1, 1);
		persons.put(p2, 2);
		persons.put(p3, 3);
		//p3的age为3,输出  {[age= 3,name= lisi1]=3, [age= 31,name= lisi2]=2}
		//p3的age为15，输出 {[age= 3,name= lisi1]=1, [age= 15,name= lisi3]=3, [age= 31,name= lisi2]=2}
		//p3的age 为4，name为lisi1，p3.equals(p1)输出true，map内容为{[age= 3,name= lisi1]=1, [age= 4,name= lisi1]=3, [age= 31,name= lisi2]=2}
		System.out.println(persons.toString());
		System.out.println(p3.equals(p1));
 
	}
}
 
class Person {
 
	String name;
	int age;
 
	public Person(String name, int age) {
		super();
		this.name = name;
		this.age = age;
	}
 
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + age;
		result = prime * result + ((name == null) ? 0 : name.hashCode());
		return result;
	}
	/**
	 * 名称相等，则确定对象相等
	 */
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		final Person other = (Person) obj;
	
		if (name == null) {
			if (other.name != null)
				return false;
		} else if (!name.equals(other.name))
			return false;
		return true;
	}
 
	@Override
	public String toString() {
 
		return "[age= " + this.age + ",name= " + this.name + "]";
	}
 
}

2，继承结构图：

3，成员变量：

    -1，comparator：用来进行内部排序，如果此属性为null，则默认使用自然排序。

 private final Comparator<? super K> comparator;

    -2，root：树的根节点。

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

    -3，size：树节点的数量。

  private transient int size = 0;

    -4，modCount：结构化修改次数。

 private transient int modCount = 0;

  private transient EntrySet entrySet = null;
    private transient KeySet<K> navigableKeySet = null;
    private transient NavigableMap<K,V> descendingMap = null;

4，主要方法：

    -1，put(K, V)：

 public V put(K key, V value) {
        Entry<K,V> t = root;//根节点
        if (t == null) {//根节点为空，则生成根节点
	    // TBD:
	    // 5045147: (coll) Adding null to an empty TreeSet should
	    // throw NullPointerException
	    //
	    // compare(key, key); // type check
            root = new Entry<K,V>(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) {//比较器不为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)//比较器为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);
        }
        Entry<K,V> e = new Entry<K,V>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);//插入完成后，修改对应红黑树节点颜色
        size++;
        modCount++;//结构化修改加1
        return null;
    }

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
         * <tt>null</tt> child links, and BLACK color.
         */
        Entry(K key, V value, Entry<K,V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }

TreeMap的结构，重点还是在于对红黑树的操作，所以在了解各个操作具体实现前，需要对红黑树的具体算法进行了解。