TreeSet你掌握了吗？ |
您所在的位置：网站首页 › cloneable接口线程安全吗 › TreeSet你掌握了吗？ |
|
前言
上篇文章我们分析了HashSet，它是基于HashMap实现的，那TreeSet会是怎么实现的呢？没错！和大家想的一样，它是基于TreeMap实现的。所以，TreeSet的源码也很简单，主要还是理解TreeMap。 TreeSet的继承关系按照惯例，先来看TreeSet类的继承关系： public class TreeSet extends AbstractSet implements NavigableSet, Cloneable, java.io.Serializable1、毫不意外的继承了抽象类AbstracSet，方便扩展； 2、实现了一个NavigableSet接口，和NavigableMap接口类似，提供了各种导航方法； 3、实现了Cloneable接口，可以克隆； 4、实现了Serializable接口，可以序列化； 这里主要看NavigableSet接口类： public interface NavigableSet extends SortedSet熟悉的味道，继承SortedSet接口。SortedSet则提供了一个返回比较器的方法： Comparator comparator();和SortedMap一样，支持自然排序和自定义排序。自然排序要求添加到Set中的元素实现Comparable接口，自定义排序要求实现一个Comparator比较器。 源码分析 关键点关键点自然是TreeSet如何保证元素不重复以及元素有序的，前面说了它是基于TreeMap实现的，那我们来看看吧。 private transient NavigableMap m; // 保证有序 // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); // 固定Value纵观TreeSet源码，发现只有这两个属性（还有个uid，这里就不算了）。很明显，m是用来保存元素的，但m声明的是NavigableMap而不是TreeMap。可以猜测，TreeMap应该是在构造方法里实例化的，这里使用NavigableMap可以让TreeSet更加灵活。PRESENT和HashSet中的PRESENT作用一样，作为固定Value值进行占位的。 再看add和remove方法： public boolean add(E e) { return m.put(e, PRESENT)==null; } public boolean remove(Object o) { return m.remove(o)==PRESENT; }和HashSet的实现一样，也是利用了Map保存的Key-Value键值对的Key不会重复的特点。 构造函数果然，TreeSet中的TreeMap是在构造函数中初始化的。 public TreeSet() { this(new TreeMap()); // 默认自然排序的TreeMap } public TreeSet(Comparator comparator) { this(new TreeMap(comparator)); // 自定义比较器的TreeMap } public TreeSet(Collection c) { this(); // 还是用的默认 addAll(c); // 将元素一个一个添加到TreeMap中 } public TreeSet(SortedSet s) { this(s.comparator()); // 使用传入的SortedSet的比较器 addAll(s); // 一个一个添加元素 }默认实例化了一个自然排序的TreeMap，当然，我们可以自定义比较器。 这里跟踪下addAll方法： public boolean addAll(Collection c) { // Use linear-time version if applicable if (m.size()==0 && c.size() > 0 && c instanceof SortedSet && m instanceof TreeMap) { SortedSet set = (SortedSet) c; TreeMap map = (TreeMap) m; // 强转成TreeMap Comparator cc = set.comparator(); Comparator mc = map.comparator(); if (cc==mc || (cc != null && cc.equals(mc))) { // 要保证set和map的比较器一样 map.addAllForTreeSet(set, PRESENT); // TreeMap专门为TreeSet准备的方法 return true; } } return super.addAll(c); }调用了TreeMap的addAllForTreeSet方法： void addAllForTreeSet(SortedSet set, V defaultVal) { try { buildFromSorted(set.size(), set.iterator(), null, defaultVal); } catch (java.io.IOException | ClassNotFoundException cannotHappen) { } }看到buildFromSorted，应该很熟悉，在TreeMap的文章中分析过。该方法将传入的集合元素构造成了一棵最底层的结点为红色，而其他结点都是黑色的红黑树。 导航方法既然实现了NavigableSet，那各种导航方法自然少不了。它们的实现也很简单，直接调用m对应的导航方法即可。例如： public E first() { return m.firstKey(); // 返回第一个元素 } public E lower(E e) { return m.lowerKey(e); // 返回小于e的第一个元素 } public NavigableSet headSet(E toElement, boolean inclusive) { return new TreeSet(m.headMap(toElement, inclusive)); // 取前几个元素构成子集 } public E pollFirst() { // 弹出第一个元素 Map.Entry e = m.pollFirstEntry(); return (e == null) ? null : e.getKey(); } public NavigableSet descendingSet() { // 倒排Set return new TreeSet(m.descendingMap()); } ......这里需要注意的是返回子集合的方法，例如：headSet。返回的子集合是可以添加和删除元素的，但是有边界限制。 // 前面构造了一个存储Int的Set // 3、5、7、9 SortedSet subSet = intSet.headSet(8); // 最大值7，超过7越界 for (Integer sub : subSet) { System.out.println(sub); } subSet.add(2); // subSet.add(8); // 越界了 subSet.remove(3); for (Integer sub : subSet) { System.out.println(sub); }TreeSet也是支持逆序输出的，因为有descendingIterator的实现： public Iterator descendingIterator() { return m.descendingKeySet().iterator(); }总结 1、TreeSet是基于TreeMap实现的，支持自然排序和自定义排序，可以进行逆序输出； 2、TreeSet不允许null值； 3、TreeSet不是线程安全的，多线程环境下可以使用SortedSet s = Collections.synchronizedSortedSet(new TreeSet(…))； 感谢各位的观看啦！ 希望可以动动小手点赞一下呀！ 你们的点赞转发就是我更文的动力！ |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |