HashSet 和 TreeSet

Posted on | In

前言

上一篇重点看了下 HashMap 以及简单说了说 LinkedHashMap，今天看下 HashSet 和 TreeSet。

HashSet

HashSet 很简单，没什么内容。先看下两个属性和几个主要的方法源码：

两个属性

1
2
3
4
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( )

1
2
3
4
5
6
7
/**
 * 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( )

1
2
3
4
5
6
7
8
/**
 * 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( )

1
2
3
4
5
6
7
8
/**
 * 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)

1
2
3
public boolean contains(Object o) {
    return map.containsKey(o);
}

add(E)

1
2
3
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

remove(Object)

1
2
3
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 进行排序。这取决于使用的构造方法。

成员变量

1
2
3
4
5
6
7
/**
 * 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();

构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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)

1
2
3
public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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;
}