有序集合TreeMap
本⽂讨论的问题：TreeMap的key排序问题
请看下⾯⼀个例⼦：
java集合排序怎么实现TreeMap<String, String> map = new TreeMap<String, String>();
map.put("f", "12345");
map.put("b", "12345");
map.put("e", "12345");
map.put("d", "12345");
map.put("g", "644");
map.put("c", "980000000");
map.put("a", "12345");
System.out.println(map);
输出结果是：
{a=12345, b=12345, c=980000000, d=12345, e=12345, f=12345, g=644}
为什么TreeMap对String类型的key值有排序效果呢？查看String类源码可知String类实现了Comparable接⼝，该接⼝中只有⼀个public int compareTo(T o);⽅法，对象的⼤⼩关系由返回值来确定，返回负整数，零，正整数表⽰当前对象⼩于，等于，⼤于指定对象。那么String类是如何实现的呢？
public int compareTo(String anotherString) {
int len1 = value.length;
int len2 = anotherString.value.length;
int lim = Math.min(len1, len2);
char v1[] = value;
char v2[] = anotherString.value;
int k = 0;
while (k < lim) {
char c1 = v1[k];
char c2 = v2[k];
if (c1 != c2) {
return c1 - c2;
}
k++;
}
return len1 - len2;
}
⾸先先⽐较相同长度内的每个字符是否相等，如果不等则返回该位置上两个字符的差值。如果都相等，那么就返回两者间length的差值。由此可见，存在⼀个效率问题，假设字符串str1由1万个a字符组成，字符串str2由⼀万个a字符串+b字符组成。那么在⽐较这两者⼤⼩的时候，就做了⼀万次⽆⽤的循环…，其实没想明⽩，为什么不先⽐较两者的length呢？
如果不想使⽤String类本⾝的排序规则怎么办呢？TreeMap还提供了⼀个有参构造⽅法来⾃定义排序规则。写⼀个类StringComparator继承Comparator接⼝，实现compare⽅法
package st;
import java.util.Comparator;
public class StringComparator implements Comparator<String> {
@Override
public int compare(String o1, String o2) {
int len1 = o1.length();
int len2 = o2.length();
// 如果长度不等，那么直接返回差值
if(len1 != len2)
return len1 - len2;
int lim = Math.min(len1, len2);
char v1[] = o1.toCharArray();
char v2[] = o2.toCharArray();
int k = 0;
while (k < lim) {
char c1 = v1[k];
char c2 = v2[k];
if (c1 != c2) {
return c1 - c2;
}
k++;
}
// 如果while循环中的return没执⾏，那么这两个字符串是相等的
return 0;
}
}
将StringComparator传⼊TreeMap的构造⽅法中
TreeMap<String, String> map = new TreeMap<>(new StringComparator());
map.put("f", "12345");
map.put("b", "12345");
map.put("e", "12345");
map.put("d", "12345");
map.put("g", "644");
map.put("c", "980000000");
map.put("a", "12345");
System.out.println(map);
运⾏结果如下所⽰
{a=12345, b=12345, c=980000000, d=12345, e=12345, f=12345, g=644}
可以看到效果是⼀样的，但从原理上⽐前者效率要⾼。为什么String类⾃⾝的⽐较器没起作⽤了呢？查看TreeMap源码可知，TreeMap在put 的时候，⾸选传⼊的⽐较器，如果⽤户没有指定⽐较器则使⽤当前对象⾃⾝的⽐较器。如果⾃定义对象要作为TreeMap的key值时，则必须实现Comparator接⼝或者传
⼊⾃定义⽐较器，否则将会抛出java.lang.ClassCastException异常，原因是当没i有⾃定义⽐较器的时
候，TreeMap在put时会执⾏Comparable<? super K> k = (Comparable<? super K>) key；操作。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。