java集合之TreeMap实现原理

java集合之TreeMap实现原理

        TreeMap集合的实现其实说简单也简单说复杂也复杂，说简单是因为TreeMap底层实现完全依靠红黑树这个数据结构，相比与HashMap来说TreeMap不用考虑hash表的扩容也不用考虑hash冲突，以及一些具有策略性的转换等（比如jdk8以上HashMap中链表长度大于等于8的时候，会自动转换为红黑树，所以HashMap的结构本身就包含TreeMap）。所以TreeMap相比于HashMap就简单许多。说复杂是因为红黑树的实现也并非我们想象的那么简单，甚至还有点难度。要想把它用自己的代码实现需要对二叉树或二叉排序树非常熟悉，包括对查找二叉树前驱节点后继节点的算法以及二叉树旋转算法等。

        关于红黑树的实现原理之前有一篇博客已经介绍过了，在此就不多叙述，否则的话估计本篇3/4都在描述红黑树的实现。红黑树的实现请参考：http://www.jiajiajia.club/official/weblog/yjw520/42

        从源码可以看出TreeMap实现了Map接口并定义了一下几个重要属性

private transient Entry<K,V> root;
    /**
     * The number of entries in the tree
     */
    private transient int size = 0;

    /**
     * The number of structural modifications to the tree.
     */
private transient int modCount = 0;
    /**
     * The comparator used to maintain order in this tree map, or
     * null if it uses the natural ordering of its keys.
     *
     * @serial
     */
    private final Comparator<? super K> comparator;

1. root属性，root是红黑树实现的根节点，树中所有节点的添加、查找、删除等操作都必须经过根节点而来。
2. Size属性不用多说，就是集合中节点的个数。
3. modCount属性是记录对树进行结构修改的次数。
4. comparator属性是一个比较器，用于解决TreeMap中key的排序问题，由于红黑树也是二叉查找树，它们当中每一个节点的比较值都必须大于或等于在它的左子树中的所有节点，并且小于或等于在它的右子树中的所有节点。这确保红黑树运作时能够快速的在树中查找给定的值。所以在调用put方法的key类必须实现Comparable接口或者在创建TreeMap的时候传入一个比较器Comparator的实现类。如下面两种实现：

class Entity implements Comparable<Entity>{
	int a;
	public Entity(int a) { this.a=a; }
	@Override
	public int compareTo(Entity o) {
		if(o.a>this.a) return 1;
		if(o.a<this.a) return -1;
		else return 0;
	}
}
public class Test {
	public static void main(String[] args) {
	    TreeMap<Entity, String> t=new TreeMap<Entity, String>();
	    t.put(new Entity(2),"2");
	    t.put(new Entity(3),"3");
	}
}

class Entity {
	public Entity(int a) { this.a=a; }
	int a;
}
public class Test {
	public static void main(String[] args) {
	    TreeMap<Entity, String> t=new TreeMap<Entity, String>(new Comparator<Entity>() {
			@Override
			public int compare(Entity o1, Entity o2) {
				if(o1.a>o2.a) return 1;
				if(o1.a<o2.a) return -1;
				else return 1;
			}
		});
	    t.put(new Entity(2),"2");
	    t.put(new Entity(3),"3");
	    System.out.println(t);
	}
}

        如果你使用HashMap的时候不满足以上任何一种则会包java.lang.ClassCastException异常。（注意如果用Integer或String等不会有异常，这些类已经实现的Comparable接口）

public class Test {
	public static void main(String[] args) {
	    TreeMap<Integer, Integer> t=new TreeMap<Integer, Integer>();
	    t.put(2,2);
	    t.put(3,3);
	    t.put(9,9);
	    t.put(4,4);
	    t.put(5,5);
	    t.put(0,0);
	    t.put(8,8);
	    t.put(7,7);
	    t.put(1,1);
	    t.put(34,34);
	    t.put(90,90);
	    /**
	     * 	方式1
	     */
	    Iterator<Entry<Integer, Integer>> iterator = t.entrySet().iterator();
	    while (iterator.hasNext()) {
	    	Entry<Integer, Integer> entry =iterator.next();
	    	System.out.println(entry);
	    }
	    
	    System.out.println("****************************");
	    /**
	     * 	方式2
	     */
	    for(Entry<Integer, Integer> entry : t.entrySet()) {
	    	 System.out.println(entry);
	    }
	}
}

        在遍历TreeMap时删除元素，一下两种方式会抛java.util.ConcurrentModificationException异常，所以做这个操作时一定要注意。

public class Test {
	public static void main(String[] args) {
	    TreeMap<Integer, Integer> t=new TreeMap<Integer, Integer>();
	    t.put(2,2);
	    t.put(3,3);
	    t.put(9,9);
	    t.put(4,4);
	    t.put(5,5);
	    t.put(0,0);
	    t.put(8,8);
	    t.put(7,7);
	    t.put(1,1);
	    t.put(34,34);
	    t.put(90,90);
	    Iterator<Entry<Integer, Integer>> iterator = t.entrySet().iterator();
	    while (iterator.hasNext()) {
	    	Entry<Integer, Integer> entry =iterator.next();
	    	System.out.println(entry);
	    	if(entry.getValue()==4) {
	    		t.remove(entry.getKey());//删除元素
	    	}
	    }
	    System.out.println("****************************");
	    for(Entry<Integer, Integer> entry : t.entrySet()) {
	    	 System.out.println(entry);
	    	 if(entry.getKey()==7) {
	    		t.remove(entry.getKey()); //删除元素
	    	 }
	    }
	}
}

正确的删除方式

public class Test {
	public static void main(String[] args) {
	    TreeMap<Integer, Integer> t=new TreeMap<Integer, Integer>();
	    t.put(2,2);
	    t.put(3,3);
	    t.put(9,9);
	    t.put(4,4);
	    t.put(5,5);
	    t.put(0,0);
	    t.put(8,8);
	    t.put(7,7);
	    t.put(1,1);
	    t.put(34,34);
	    t.put(90,90);
	    Iterator<Entry<Integer, Integer>> iterator = t.entrySet().iterator();
	    while (iterator.hasNext()) {
	    	Entry<Integer, Integer> entry =iterator.next();
	    	System.out.println(entry);
	    	if(entry.getValue()==4) {
	    		iterator.remove();//正确删除元素的方式
	    	}
	    }
	    System.out.println("****************************");
	    for(Entry<Integer, Integer> entry : t.entrySet()) {
	    	 System.out.println(entry);
	    }
	}
}

        TreeMap和HashMap一样都是非线程安全的，从它的源码的实现中可以看出，所以在并发编程中使用的时候要注意这一点。