HashSet和TreeSet #8
Description
前言
上一篇重点看了下 HashMap 以及简单说了说 LinkedHashMap，今天看下 HashSet 和 TreeSet。
HashSet
HashSet 很简单，没什么内容。先看下两个属性和几个主要的方法源码：
两个属性
private transient HashMap<E,Object> map; // Dummy value to associate with an Object in the backing Map //作为map的value，没什么用处 private static final Object PRESENT = new Object();HashSet( )
/** * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has * default initial capacity (16) and load factor (0.75). */ public HashSet() { map = new HashMap<>(); }size( )
/** * Returns the number of elements in this set (its cardinality). * * @return the number of elements in this set (its cardinality) */ public int size() { return map.size(); }isEmpty( )
/** * Returns <tt>true</tt> if this set contains no elements. * * @return <tt>true</tt> if this set contains no elements */ public boolean isEmpty() { return map.isEmpty(); }contains(Object)
public boolean contains(Object o) { return map.containsKey(o); }add(E)
public boolean add(E e) { return map.put(e, PRESENT)==null; }remove(Object)
public boolean remove(Object o) { return map.remove(o)==PRESENT; }OK，这几个方法看完了就没了，一眼就可以看出来 HashSet 的元素就像 HashMap 的 key 一样。换句话说，HashMap 是 实现HashSet 的支撑。这个没啥意思，再来看下相比之下更有意思的 TreeSet
TreeSet
其实大多数类或者接口，看名字就知道有什么主要特性了，Set, 它是一个元素不重复的集合，TreeSet，它就是一个可以基于二叉树对元素进行排序的不可重复集合。TreeSet 是基于 TreeMap 实现的。TreeSet 中的元素支持2种排序方式：自然排序 或者 根据创建 TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法。
成员变量
/** * The backing map. */ private transient NavigableMap<E,Object> m; // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object();构造方法
TreeSet(NavigableMap<E,Object> m) { this.m = m; } public TreeSet() { this(new TreeMap<E,Object>()); } //传入一个进行元素排序的比较器 public TreeSet(Comparator<? super E> comparator) { this(new TreeMap<>(comparator)); } //传入一个集合，将其中的元素添加至TreeSet中 public TreeSet(Collection<? extends E> c) { this(); addAll(c); } //创建TreeSet，并将s中的全部元素都添加到TreeSet中 public TreeSet(SortedSet<E> s) { this(s.comparator()); addAll(s); }排序方式
-
让元素自身具备比较性，需要元素实现Comparable接口，覆盖compareTo方法，
这种方式也称为元素的自然排序，或者叫做默认排序。
-
当元素自身不具备比较性时，或者具备的比较性不是所需要的时候，
需要让集合自身具备比较性。在集合初始化时，就有了比较性
需要定义一个实现了Comparator接口的比较器，覆盖compare方法，并将该类对象作为
参数传递给TreeSet集合的构造函数
add(E)
public boolean add(E e) { return m.put(e, PRESENT)==null; }public V put(K key, V value) { Entry<K,V> t = root; if (t == null) { compare(key, key); // type (and possibly null) check root = new Entry<>(key, value, null); size = 1; modCount++; return null; } 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); } //基于元素自身的比较性进行排序 else { if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; do { parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } Entry<K,V> e = new Entry<>(key, value, parent); if (cmp < 0) parent.left = e; else parent.right = e; fixAfterInsertion(e); size++; modCount++; return null; }这篇内容较少，因为它都是基于两个相关的Map实现的，也比较简单