TreeMap排序规则
public static void main(String[] args) {
Map<String,String> map = new TreeMap<String,String>();
("1", "A");
("2", "C");
("3", "K");
("4", "D");
("5", "B");
("6", "L");
System.out.println(map);
}
运行结果:
{1=A, 2=C, 3=K, 4=D, 5=B, 6=L}
key和value调换位置
public class TestDemo {
public static void main(String[] args) {
Map<String,String> map = new TreeMap<String,String>();
("A", "1");
("C", "2");
("K", "3");
("D", "4");
("B", "5");
("L", "6");
System.out.println(map);
}
}
运行结果:
{A=1, B=5, C=2, D=4, K=3, L=6}
我们发现它是根据key进行排序的
下面看一个自定义对象作为key的例子
class Person{
public String name;
public int age;
public Person(String name,int age){
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Person [name=" + name + ", age=" + age + "]";
}
}
public class TestDemo {
public static void main(String[] args) {
Map<Person,String> map = new TreeMap<Person,String>();
(new Person("张三",20), "1");
(new Person("李四",18), "2");
(new Person("王五",18), "3");
(new Person("赵六",18), "4");
(new Person("钱七",26), "5");
(new Person("周八",33), "6");
System.out.println(map);
}
}
我们发现哇哇的报错
Exception in thread "main" : cannot be cast to
at (:1290)
at (:538)
at (:16)
看到Comparable接口我们就瞬间明白了，String为什么能排序，因为它是Comparable的子类，而TreeMap中的排序就是依赖于Comparable接口的compareTo方法得以实现的，我们自定义的对象不是Comparable的子类，不是Comparable接口子类就不能排序?
看一下源码:[TreeMap存储机制]
public V put(K key, V value) {
Entry<K,V> t = root;
//根节点，新建一个根节点 return
if (t == null) {
//比较器关键部分，下面贴出compare方法
compare(key, key); // type (and possibly null) check
//代码解析在下面 原理:红黑树
root = new Entry<>(key, value, null);
//TreeMap长度，调用()直接返回size
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// 我们使用的是Comparable接口，条件不成立，进入else
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
//这里的比较方法会导致复写的类的所有属性必须参与排序操作，否则会被认为是同一个key,直接被setValue(value),下面会说到这个问题
cmp = (key, );
if (cmp < 0)
t = ;
else if (cmp > 0)
t = ;
else
return (value);
} while (t != null);
}
else {
//我们发现key不能为null，而hashMap是可以的
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = ();
//新来的key小于当前节点key，将的地址给t,表示当前变量t表示了，在下一次循环中就是当前节点，一直到当前节点是个空位置
if (cmp < 0)
t = ;
//新来的key大于当前节点key，将的地址给t,表示当前变量t表示了，在下一次循环中就是当前节点，一直到当前节点是个空位置
else if (cmp > 0)
t = ;
else
//等于，直接更新当前节点值
return (value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
//为空位置赋值
if (cmp < 0)
= e;
else
= e;
//红黑树概念
//这个方法的代码就是红黑树平衡与旋转的处理，太多了，自己看
fixAfterInsertion(e);
//计数
size++;
modCount++;
return null;
}
//关键问题
@SuppressWarnings("unchecked")
final int compare(Object k1, Object k2) {
//如果你传入自定义比较器，则调用自定义比较器，如果没传，它会认为你实现了Comparable接口，将你向上强制转换为Comparable类，所以Person由于没有实现Comparable接口就会转换错误，有人问了为什么k1和k2是同一个key?这样做没有什么特殊的目的，就是为了判断你是否实现了Comparable接口，否则无法排序啊
return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
: ((K)k1, (K)k2);
}
下面我们让Person实现Comparable接口，复写compareTo方法，看看效果
class Person implements Comparable<Person>{
public String name;
public int age;
public Person(String name,int age){
this.name = name;
this.age = age;
}
@Override
public int compareTo(Person o) {
if( > this.age){
return 1;
}else if( < this.age ){
return -1;
}else{
return this.();
}
}
@Override
public String toString() {
return "Person [name=" + name + ", age=" + age + "]";
}
}
public class TestDemo {
public static void main(String[] args) {
Map<Person,String> map = new TreeMap<Person,String>();
(new Person("张三",20), "1");
(new Person("李四",18), "2");
(new Person("王五",18), "3");
(new Person("赵六",18), "4");
(new Person("钱七",26), "5");
(new Person("周八",33), "6");
System.out.println(map);
}
}
运行结果:
{
Person [name=周八, age=33]=6,
Person [name=钱七, age=26]=5,
Person [name=张三, age=20]=1,
Person [name=李四, age=18]=4
}
我们发现元素少了，我在源码里面已经讲过原因了
就是这段
//这里的比较方法会导致复写的类的所有属性必须参与排序操作，否则如果前几个属性相同，最后一个不同，而最后一个没有参与排序，则会被认为是同一个key,直接被setValue(value)，value是最新的一个元素的value,导致元素减少
cmp = (key, );
if (cmp < 0)
t = ;
else if (cmp > 0)
t = ;
else
return (value);
下面我们让所有属性参与排序
我们把复写的compareTo方法修改如下:
@Override
public int compareTo(Person o) {
if( > this.age){
return 1;
}else if( < this.age ){
return -1;
}else{
return (this.name);
}
}
运行结果:
{
Person [name=周八, age=33]=6,
Person [name=钱七, age=26]=5,
Person [name=张三, age=20]=1,
Person [name=赵六, age=18]=4,
Person [name=王五, age=18]=3,
Person [name=李四, age=18]=2
}
另外hashMap有一点还要注意：
在我们使用自定义的对象作为key的时候，复写equals和hashCode方法一定要注意，比如你用对象作为key,对象里有三个属性，而你复写equals只使用了两个，但是实际上第三个属性的值是不同的，但是hashMap会通过equals和hashCode判断返回true和相同的hashCode,那么他们就会被当成一个key，就麻烦了，当然自定义对象很少用作key
HashSet同样如此，凡是不能出现重复元素，或者重复key的集合，一定要注意复写equals和hashCode方法的正确性，所以一般别别复写就行了。
复写的话
new Person("张三",20)
new Person("张三",20)
可以是同一个元素
不复写一定不是同一个元素
END