TreeMap In Java
TreeMap
Java里的treemap和hashmap类似，都是键值对的存储结构，但是hashmap存储数据不实按照自然顺序的，是按照key的hashcode来的，遍历得到的数据也是完全随机的，而treemap存储数据则是有序的，因为treemap实现了sortedmap接口，而sortedmap接口是基于红黑树的（BST的一种），看到BST我们应该能想起来查找时间复杂度是O(log(n))，比hashmap的O(n)查找要快,因为BST查找只需要比较数的深度次（这里提出来就是为了加深印象，一般面试时会考虑的也是他们存储的数据有序无序，还有时间复杂度）。
看官网的文档上清楚说明了以下几点：
-implemented interfaces areMap,NavigableMap,SortedMap
-public class TreeMap extendsAbstractMap
-a red-black tree based NavigableMapimplementation. The map is sorted according to the natural order its keys, orby a Comparator provided at map creation time.
This implementation provides guaranteedlog(n) time cost for the containsKeey, get, put, and remove operations.
-constructiors:
TreeMap()-用于构造一个新的空的tree map， 排序根据key的自然排序
TreeMap(Comparator comparator) –构造一个新的空的tree map，但是排序是根据括号里创建的比较器里的排序来的。
TreeMap(Map m) –根据传递的map m来构造一个数据一样的tree map，排序根据key的自然排序。
TreeMap(SortedMap m) –创建一个数据，排序都和m一样的tree map
-主要的方法： 和hashmap类似：
clear():清除map
containsKey(Objectkey):包含key则返回true，否则false
containsValue(Objectvalue):是否包含value
等等，方法，详见官网文档，下面我们来仔细练习几个tree map的方法。
1. 先创建一个比较器，没有看过treemap底层代码是如何实现的，但是根据官方文档介绍可以推断是用到了比较器的，Comparator接口里面定义来比较方法compare（Object a,Object b）,
并且默认是根据传入的a,b的值做比较，返回一个a-b的值，如果a-b=0则表示ab一样大，如果a-b大于0则表示a大于b,小于零则表示a比b小，默认的都是生序排列的，如果要降序排列，可以把a-b 换成 b-a，这样就是逆序了。
package zexin;
import java.util.Comparator;
class SortOrder implements Comparator{
public int compare(Student a, Student b){
return a.studno - b.studno;
}
}
2. 创建一个student对象：
package zexin;
public class Student {
int studno;
String
name, address;
//constructor
public Student(int studno, String name, String address) {
this.studno = studno;
this.name = name;
this.address = address;
}
}
[if !supportLists]3. [endif]验证功能：
package zexin;
import java.util.*;
public class Main {
public static void main(String[] args) {
// write your code here
SortOrder sort = new SortOrder();
TreeMap tree_map
=
new TreeMap(sort);
Student s1 =
new Student(1, "heaven", "melbourne");
Student s2 =
new Student(2, "siyuan", "huzhou");
Student s3 =
new Student(3, "zexin", "docklands");
Student s4 =
new Student(4, "tanzey", "shenzhen");
// Mapping string values to int keys
tree_map.put(s1, 4);
tree_map.put(s2,
3);
tree_map.put(s3,
2);
tree_map.put(s4,
1);
// Displaying the TreeMap
System.out.println("TreeMap: "
+ tree_map);
for(var i : tree_map.entrySet()){
System.
out.println(i);
}
Map hm =
new HashMap<>();
hm.put(
1,s1);
hm.put(
2,s2);
hm.put(
3,s3);
hm.put(
4,s4);
TreeMap tm =
new TreeMap<>(hm);
System.
out.println("Treemap2 created by hash map:" + tm);
}
}
当我们的compare函数里是使用默认的a-b的形式时，我们可以看到如下结果：
当我们将默认的a-b 交换减数被减数位置后逆序排列：
重点要理解treemap里排序规则，一般用到treemap都是要考虑排序的时候，
所以override
comparator排序规则就很有必要。
