1 TreeSet
1.1 TreeSet快速入门
相较于HashSet，TreeSet最大的特点是实现了排序，但是需要注意的是，当我们使用无参构造器创建TreeSet时，仍然是无序的。如果希望添加的元素按照字符串大小来排序则需要使用比较器Comparator，并指定排序规则。
来看下面的例子，可以看出，结果按照字符串大小进行了排序：
import java.util.Comparator; import java.util.TreeSet; /** * @author 兴趣使然黄小黄 * @version 1.0 */ public class TreeSetTest { public static void main(String[] args) { TreeSet treeSet = new TreeSet(new Comparator() { @Override public int compare(Object o1, Object o2) { return ((String)o1).compareTo((String) o2); } }); // 添加数据 treeSet.add("lucy"); treeSet.add("drunk"); treeSet.add("youth"); treeSet.add("bob"); treeSet.add("a"); System.out.println("treeSet = " + treeSet); } }
1.2 TreeSet比较机制源码解读
1️⃣ 构造器把传入的比较器对象，赋给了 TreeSet 底层的 TreeMap 属性。
2️⃣ 在调用 treeSet.add(“drunk”)，底层会执行到下述代码，其中cpr 就是我们的匿名内部类（对象），会动态绑定到匿名内部类的compare方法。
Comparator<? super K> cpr = comparator; 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 // 如果相等，即返回0，这个key就没有加入 return t.setValue(value); } while (t != null); }
需要注意的是，当比较结果是相等时，不会将key添加进去！
我们来看下面的例子，尝试将比较规则更改为按照字符串长度排序：
import java.util.Comparator; import java.util.TreeSet; /** * @author 兴趣使然黄小黄 * @version 1.0 */ public class TreeSetTest { public static void main(String[] args) { TreeSet treeSet = new TreeSet(new Comparator() { @Override public int compare(Object o1, Object o2) { return ((String)o2).length() -((String)o1).length(); } }); // 添加数据 treeSet.add("Drunk"); treeSet.add("Youth"); System.out.println("treeSet = " + treeSet); } }
由于 Drunk 与 Youth 长度相同，因此，在底层调用比较器的时候，不加入 Youth 这一 key 值。 这也是小白时期常常容易犯的错误，导致了数据的丢失！
2 TreeMap
2.1 TreeMap快速入门
当使用无参构造器的时候，TreeMap默认按照key值进行自然排序。
import java.util.TreeMap; /** * @author 兴趣使然黄小黄 * @version 1.0 */ public class TreeMapTest { public static void main(String[] args) { TreeMap treeMap = new TreeMap(); // 添加数据 treeMap.put("drunk", "路宝"); treeMap.put("abc", "香克斯"); treeMap.put("cat", "多弗朗明哥"); System.out.println("treeMap = " + treeMap); } }
也可以传入比较器，进行自定义排序。比如，尝试按照key的字符串长度的大小进行排序：
import java.util.Comparator; import java.util.TreeMap; /** * @author 兴趣使然黄小黄 * @version 1.0 */ public class TreeMapTest { public static void main(String[] args) { TreeMap treeMap = new TreeMap(new Comparator() { @Override public int compare(Object o1, Object o2) { return ((String)o1).length() - ((String)o2).length(); } }); // 添加数据 treeMap.put("drunk", "路宝"); treeMap.put("abc", "香克斯"); treeMap.put("cat", "多弗朗明哥"); System.out.println("treeMap = " + treeMap); } }
此时，由于 cat 和 abc 两个键的长度相同，因此，后面的 cat键没有成功加入，只是将 cat 对应的值 与 abc 对应的值进行了替换！
2.2 TreeMap比较机制源码解读
1️⃣ 调用构造器的时候，把传入的实现了 Comparator接口的匿名内部类（对象），赋给了 TreeMap 的属性 comparator；
2️⃣ 在执行第一个put时，加入了一个结点作为root根节点，把 k-v 封装到 Entry对象，放入root；
3️⃣ 之后调用 put 方法，会调用比较器。进行所有 key 的遍历，并动态绑定到匿名内部类的compare()方法。如果发现比当前结点小，则挂到左子树，大了就挂到右子树。如果相等，则只进行value的替换，key不会加入。 使用setValue方法进行。
int cmp; Entry<K,V> parent; // split comparator and comparable paths Comparator<? super K> cpr = comparator; 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); }
