》 TreeMap:是基于红黑树的Map接口的实现。
红黑树：平衡二叉树
取出时，可以有三种方式：前序遍历，中序遍历，后序遍历
》排序:
A 自然排序 --TreeMap无参构造
TreeMap<key类型,value类型> map= new TreeMap<key类型,value类型>();//key类应当实现Comparable接口,并重写hashCode()和equals()方法
B 比较器排序—TreeMap 比较器有参构造
TreeMap<key类型,value类型> map= new TreeMap<key类型,value类型>( new Comparator<key类型> (){ @Override compare(){ } });
》TreeMap put()方法源码
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;//构造TreeMap时确定comparator是否为null
//比较器排序 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; else return t.setValue(value); } while (t != null); } //自然排序
else { if (key == 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++; return null; }
案例:
package cn.itcast_04; import java.util.Comparator; import java.util.Set; import java.util.TreeMap; /* * TreeMap<Student,String> * 键:Student * 值：String */ public class TreeMapDemo2 { public static void main(String[] args) { // 创建集合对象(比较器Comparator的子类来实现排序规则) TreeMap<, String> tm = new TreeMap<Student, String>( new <>() { @Override public int compare(Student s1, Student s2) { // 主要条件 int num = s1.getAge() - s2.getAge(); // 次要条件 int num2 = num == 0 ? s1.getName().compareTo( s2.getName()) : num; return num2; } }); // 创建学生对象 Student s1 = new Student("潘安", 30); Student s2 = new Student("柳下惠", 35); Student s3 = new Student("唐伯虎", 33); Student s4 = new Student("燕青", 32); Student s5 = new Student("唐伯虎", 33); // 存储元素 tm.put(s1, "宋朝"); tm.put(s2, "元朝"); tm.put(s3, "明朝"); tm.put(s4, "清朝"); tm.put(s5, "汉朝"); // 遍历 Set<Student> set = tm.keySet(); for (Student key : set) { String value = tm.get(key); System.out.println(key.getName() + "---" + key.getAge() + "---" + value); } } }
//因为上面案例使用的是比较器排序，而不是自然排序，所以作为key的Student并不需要实现Comparable接口
开始做，坚持做，重复做package cn.itcast_04; public class Student { private String name; private int age; public Student() { super(); } public Student(String name, int age) { super(); this.name = name; this.age = age; } public String getName() { return name; } public void setName(String name) { this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } }
