Java篇 - 一招教你使用TreeMap

53 阅读 0 评论 35 点赞

我是靠谱客的博主糊涂万宝路，最近开发中收集的这篇文章主要介绍Java篇 - 一招教你使用TreeMap，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

今天来讲下TreeMap的源码实现，在这之前，先来简单了解下Java中的几种Map。

1. HashMap

HashMap 是一个最常用的Map，它根据键的HashCode值存储数据，根据键可以直接获取它的值，具有很快的访问速度。遍历时，取得数据的顺序是完全随机的。

HashMap最多只允许一条记录的键为null，允许多条记录的值为 null。
HashMap不支持线程的同步，可能会导致数据的不一致。如果需要同步，可以用Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。
Hashtable与HashMap类似，它继承自Dictionary类。不同的是：它不允许记录的键或者值为空；它支持线程的同步，因此也导致了Hashtable在写入时会比较慢。

2. LinkedHashMap

LinkedHashMap保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的。也可以在构造时带参数，按照应用次数排序。
在遍历的时候会比HashMap慢，不过有种情况例外：当HashMap容量很大，实际数据较少时，遍历起来可能会比LinkedHashMap慢。因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和它的容量有关。

LinkedHashMap还可以用来实现LruCache，因为LinkedHashMap提供了removeEldestEntry()方法。

3. TreeMap

TreeMap实现SortMap接口，能够把它保存的记录根据键排序。默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。

那么TreeMap是否可以有空key呢，分为两种情况(后面分析源码时会讲解):

当未实现 Comparator 接口时，key 不可以为null，否则抛 NullPointerException异常。
当实现 Comparator 接口时，若未对 null 情况进行判断，则可能抛 NullPointerException异常。

4. 三种Map如何选择？

一般情况下，我们用的最多的是HashMap。HashMap里面存入的键值对在取出的时候是随机的，它根据键的HashCode值存储数据，根据键可以直接获取它的值，具有很快的访问速度。在Map中插入、删除和定位元素，HashMap是最好的选择。
TreeMap取出来的是排序后的键值对，如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。
LinkedHashMap 是HashMap的一个子类，如果需要输出的顺序和输入的相同,那么用LinkedHashMap可以实现，它还可以按读取顺序来排列，像连接池中可以应用。

5. TreeMap使用的小例子


TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("k", 1);
treeMap.put("w", 3);
treeMap.put("z", 2);
System.out.println(treeMap);

执行输出：

{k=1, w=3, z=2}

TreeMap默认是按照key的自然顺序升序排列的，比如上面k, w, z，按照它们的ASCII码值排序就是kwz。

我们也可以在构造TreeMap时传入比较器：


TreeMap<String, Integer> treeMap = new TreeMap<>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if (o1 == null)
return -1;
if (o2 == null)
return -1;
return o2.compareTo(o1);
}
});
treeMap.put("k", 1);
treeMap.put("w", 3);
treeMap.put("z", 2);
System.out.println(treeMap);

执行输出：

{z=2, w=3, k=1}

这样就实现了按照key倒叙排序。

6. Comparable和Comparator的区别

Comparable是排序接口。若一个类实现了Comparable接口，就意味着该类支持排序。实现了Comparable接口的类的对象的列表或数组可以通过Collections.sort或Arrays.sort进行自动排序，无需指定比较器。也可以通过compareTo方法直接进行比较，该接口定义如下：


public interface Comparable<T> {
public int compareTo(T o);
}

看个例子：


public static void main(String[] args) {
Coder[] coders = new Coder[]{new Coder("kuang", 20), new Coder("zhong", 30)};
Arrays.sort(coders);
for (Coder coder : coders) {
System.out.println(coder.name + ":" + coder.age);
}
}
private static final class Coder implements Comparable<Coder> {
final String name;
final int age;
public Coder(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public int compareTo(Coder o) {
return age - o.age;
}
}

执行输出：

kuang:20
zhong:30

可以看到，按照年龄的升序排序。

也可以直接调用compareTo进行比较，而且传入的泛型不限制为该对象类型，只要是能比较的类型就行：


public static void main(String[] args) {
Coder coder = new Coder("kuang", 20);
System.out.println(coder.compareTo(30));
}
private static final class Coder implements Comparable<Integer> {
final String name;
final int age;
public Coder(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public int compareTo(Integer integer) {
return age - integer;
}
}

执行输出：-10

Comparator是比较接口，我们如果需要控制某个类的次序，而该类本身不支持排序(即没有实现Comparable接口)，那么我们就可以建立一个"该类的比较器"来进行排序，这个"比较器"只需要实现Comparator接口即可。也就是说，我们可以通过实现Comparator来新建一个比较器，然后通过这个比较器对类进行排序。


public static void main(String[] args) {
Coder[] coders = new Coder[]{new Coder("kuang", 20), new Coder("zhong", 30)};
Arrays.sort(coders, new Comparator<Coder>() {
@Override
public int compare(Coder o1, Coder o2) {
if (o1 == null)
return -1;
if (o2 == null)
return -1;
return o2.age - o1.age;
}
});
for (Coder coder : coders) {
System.out.println(coder.name + ":" + coder.age);
}
}
private static final class Coder {
final String name;
final int age;
public Coder(String name, int age) {
this.name = name;
this.age = age;
}
}

可以看到，上面的Coder类没有实现Comparable接口，但是我们可以通过一个Comparator对象来实现比较。

执行输出：

zhong:30
kuang:20

总结下：

Comparable是排序接口，若一个类实现了Comparable接口，就意味着"该类支持排序"。而Comparator是比较器，我们若需要控制某个类的次序，可以建立一个"该类的比较器"来进行排序。

Comparable相当于"内部比较器"，而Comparator相当于"外部比较器"。

两种方法各有优劣，用Comparable简单，只要实现Comparable 接口的对象直接就成为一个可以比较的对象，但是需要修改源代码。用Comparator 的好处是不需要修改源代码，而是另外实现一个比较器，当某个自定义的对象需要作比较的时候，把比较器和对象一起传递过去就可以比大小了，并且在Comparator 里面用户可以自己实现复杂的可以通用的逻辑，使其可以匹配一些比较简单的对象，那样就可以节省很多重复劳动了。

下一章我将来分析TreeMap的源码实现。