/**

* Map接口的实现类TreeMap 使用红黑树存储数据 通过Comparable或Comparator对key进行排序且key不可重复

*/

public class TestTreeMap1 {

public static void main(String[] args) {

Map comment = new TreeMap<>();

comment.put(9865481,"good");

comment.put(6848453,"bad");

for (Integer id :

comment.keySet()) {

//通过.keySet()遍历

System.out.println(id+":"+comment.get(id));

}

comment.put(8764582,"excellent");

for (Map.Entry comm :

comment.entrySet()) {

//通过.entrySet()遍历

System.out.println(comm.getKey()+":"+comm.getValue());

}

System.out.println(comment);

//结果为{6848453=bad, 8764582=excellent, 9865481=good} TreeSet对key=Integer排序，从小到大

//comment.remove();comment.clear();comment.containsValue();comment.isEmpty();comment.size();方法的使用和HashMap相同

Map comment2 = new TreeMap<>(new Comparator() {

//通过比较器comparator指定规则排序

@Override

public int compare(Integer o1, Integer o2) {

if (o1>o2) return -1;

if (o1

return 0;

}

});

}

}

/* 分析TreeMap集合put()源码

public class TreeMap extends AbstractMap implements NavigableMap, Cloneable, java.io.Serializable {

//TreeMap实现NavigableMap，而NavigableMap extends SortedMap extends Map

public V put(K key, V value) {

Entry t = root; //root根结点 红黑树中不使用Node存储结点，直接使用内部定义的Entry类存储结点 每个结点有key、value、left左子树结点/左孩子、right右子树结点/右孩子、parent父结点和boolean color表示红色或黑色，红色用常量RED = false，黑色用常量BLACK = true

if (t == null) {

compare(key, key); // type (and possibly null) check //当根结点为空即红黑树集合中没有存放结点，通过调用compare方法检查key是否指定了排序规则，当既没有实现Comparable也没有指定Comparator比较器时会抛出类型转换异常

root = new Entry<>(key, value, null);

size = 1; //将根结点设为新结点，size即结点数变为1，结束方法

modCount++;

return null;

} //当已经存在根结点时往下执行

int cmp;

Entry parent;

// split comparator and comparable paths分成使用Comparable排序或使用Comparator排序两条路

Comparator<? super K> cpr = comparator; //cmp即Comparable，cpr即Comparator，parent用来缓存父结点

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; //近似二分法，当比较结果为负走左子树这条路，当比较结果为正走右子树这条路，这样在put阶段直接完成了排序

else

return t.setValue(value); //返回0即两个key相同，变更value并将原value返回

} while (t != null); //直到遇到null即这条路走到头了到达了叶结点的子结点null，这时parent为叶结点即树的末端结点，如果没有key冲突则往下执行新结点的添加

}

else { //当不存在比较器的时候使用自身实现的compareTo方法，过程和上面类似

if (key == null)

throw new NullPointerException();

@SuppressWarnings("unchecked")

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 e = new Entry<>(key, value, parent); //将新结点的父结点设为叶结点

if (cmp < 0) //根据比较结果判断应该将新结点放在叶结点的左孩子还是右孩子位

parent.left = e;

else

parent.right = e;

fixAfterInsertion(e); //为了维持红黑树的性质，这里要针对新增的结点进行修复

size++;

modCount++;

return null; //添加完成返回null

}

*/