TreeMap类

• 实现了SortedMap接口（是Map的子接口），可以对key自动排序。

1. TreeMap

TreeMap<Student, Integer> treeMap = new TreeMap<Student, Integer>();
Student s1 = new Student("tang", 36);
Student s2 = new Student("yu", 101);
Student s3 = new Student("he", 10);
// 1.添加元素
treeMap.put(s1, 21);
treeMap.put(s2, 22);
treeMap.put(s3, 21);
// 需要实现Comparable接口，因为红黑树需要比较大小
System.out.println(treeMap.toString());

// 2.删除元素
treeMap.remove(new Student("he", 10));
System.out.println(treeMap.toString());

// 3.遍历
// 3.1 使用keySet()
for (Student key : treeMap.keySet()) {
    System.out.println(key + " " + treeMap.get(key));
}

// 3.2 使用entrySet()
for (Entry<Student, Integer> entry : treeMap.entrySet()) {
    System.out.println(entry.getKey() + " " + entry.getValue());
}

// 4.判断
System.out.println(treeMap.containsKey(s1));
System.out.println(treeMap.isEmpty());

在学生类中实现Comparable接口：

public class Student implements Comparable<Student> {

  // ...

  @Override
  public int compareTo(Student o) {
    int n1 = this.id - o.id;
    return n1;
  }
}

除此之外还可以使用比较器来定制比较：

TreeMap<Student, Integer> treeMap2=new TreeMap<Student, Integer>(new Comparator<Student>(){
@Override
public int compare(Student o1,Student o2){
        // 略
        return 0;
        }
});

2. TreeSet源码分析

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    private transient NavigableMap<E,Object> m;
    private static final Object PRESENT = new Object();
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }
}

TreeSet的存储结构实际上就是TreeMap，再来看其存储方式：

public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}

它的add方法调用的就是TreeMap的put方法，将元素作为key传入到存储结构中。