java双例集合TreeMap类
/**
* Map接口的实现类TreeMap 使用红黑树存储数据 通过Comparable或Comparator对key进行排序且key不可重复
*/
public class TestTreeMap1 {
public static void main(String[] args) {
Map<Integer,String> 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<Integer, String> 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<Integer,String> comment2 = new TreeMap<>(new Comparator<Integer>() {
//通过比较器comparator指定规则排序
@Override
public int compare(Integer o1, Integer o2) {
if (o1>o2) return -1;
if (o1<o2)return 1;
return 0;
}
});
}
}
/* 分析TreeMap集合put()源码
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
//TreeMap实现NavigableMap<K,V>，而NavigableMap<K,V> extends SortedMap<K,V> extends Map<K,V>
public V put(K key, V value) {
Entry<K,V> 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<K,V> 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<K,V> e = new Entry<>(key, value, parent); //将新结点的父结点设为叶结点
if (cmp < 0) //根据比较结果判断应该将新结点放在叶结点的左孩子还是右孩子位
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e); //为了维持红黑树的性质，这里要针对新增的结点进行修复
size++;
modCount++;
return null; //添加完成返回null
}
*/
