Fork me on GitHub

【Java集合】Set源码解析

发表于 | 分类于

HashSet

1
2
3
public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 默认构造函数
public HashSet() 

// 带集合的构造函数
public HashSet(Collection<? extends E> c) {
    //hashMap 负载因子0.75，c.size()/.75f) + 1 计算出来的为总的空间大小，不需要扩容
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

// 指定HashSet初始容量和加载因子的构造函数
public HashSet(int initialCapacity, float loadFactor) 

// 指定HashSet初始容量的构造函数
public HashSet(int initialCapacity) 

// 指定HashSet初始容量和加载因子的构造函数,dummy没有任何作用
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);		//LinkedHashSet使用
}

数据结构

  • HashSet 是一个没有重复元素的集合
  • 由HashMap实现的，不保证元素的顺序
  • 允许使用 null 元素
  • 非线程安全， 用Collections.synchronizedSet分装
1
Set s = Collections.synchronizedSet(new HashSet(...));
  • HashSet通过iterator()返回的迭代器是fail-fast的。
  • 成员变量
1
2
3
4
5
private transient HashMap<E,Object> map;	//基于map实现
// PRESENT是向map中插入key-value对应的value
// 因为HashSet中只需要用到key，而HashMap是key-value键值对；
// 所以，向map中添加键值对时，键值对的值固定是PRESENT
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
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
public Iterator<E> iterator() {
    return map.keySet().iterator();
}

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

//value为PRESENT对象
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

//克隆一个HashSet，并返回Object对象
public Object clone() {
    try {
        HashSet<E> newSet = (HashSet<E>) super.clone();
        newSet.map = (HashMap<E, Object>) map.clone();
        return newSet;
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
}

// java.io.Serializable的写入函数
// 将HashSet的“总的容量，加载因子，实际容量，所有的元素”都写入到输出流中
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    // Write out any hidden serialization magic
    s.defaultWriteObject();

    // Write out HashMap capacity and load factor
    s.writeInt(map.capacity());
    s.writeFloat(map.loadFactor());

    // Write out size
    s.writeInt(map.size());

    // Write out all elements in the proper order.
    for (E e : map.keySet())
        s.writeObject(e);
}

// java.io.Serializable的读取函数
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // Read in any hidden serialization magic
    s.defaultReadObject();

    // Read capacity and verify non-negative.
    int capacity = s.readInt();
    if (capacity < 0) {
        throw new InvalidObjectException("Illegal capacity: " + capacity);
    }

    // Read load factor and verify positive and non NaN.
    float loadFactor = s.readFloat();
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
        throw new InvalidObjectException("Illegal load factor: " + loadFactor);
    }

    // Read size and verify non-negative.
    int size = s.readInt();
    if (size < 0) {
        throw new InvalidObjectException("Illegal size: " + size);
    }

    // Set the capacity according to the size and load factor ensuring that
    // the HashMap is at least 25% full but clamping to maximum capacity.
    capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f),
                              HashMap.MAXIMUM_CAPACITY);

    // Create backing HashMap
    map = (((HashSet<?>)this) instanceof LinkedHashSet ?
           new LinkedHashMap<E,Object>(capacity, loadFactor) :
           new HashMap<E,Object>(capacity, loadFactor));

    // Read in all elements in the proper order.
    for (int i=0; i<size; i++) {
        @SuppressWarnings("unchecked")
        E e = (E) s.readObject();
        map.put(e, PRESENT);
    }
}

TreeSet

1
2
public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//将TreeMap 赋值给NavigableMap
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，并将集合c中的全部元素都添加到TreeSet中
public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}

public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    addAll(s);
}

数据结构

  • TreeSet 是一个有序的，且没有重复元素集合，它的作用是提供有序的Set集合。
  • TreeSet 实现了NavigableSet接口，意味着它支持一系列的导航方法。比如查找与指定目标最匹配项。
  • TreeSet是基于TreeMap实现的。TreeSet中的元素支持2种排序方式：自然排序 或者 根据创建TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法。
  • 非线程安全
  • 成员变量：
1
2
private transient NavigableMap<E,Object> m; 	//NavigableMap对象，基于TreeMap实现（传入new TreeMap<E,Object>()）
private static final Object PRESENT = new Object();	//value所存值

源码分析

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//将集合中的元素赋值给TreeSet
public  boolean addAll(Collection<? extends E> c) {
    // Use linear-time version if applicable
    if (m.size()==0 && c.size() > 0 &&
        c instanceof SortedSet &&
        m instanceof TreeMap) {
        SortedSet<? extends E> set = (SortedSet<? extends E>) c;
        TreeMap<E,Object> map = (TreeMap<E, Object>) m;
        Comparator<?> cc = set.comparator();
        Comparator<? super E> mc = map.comparator();
        if (cc==mc || (cc != null && cc.equals(mc))) {
            map.addAllForTreeSet(set, PRESENT);		// 红黑树添加SortedSet节点
            return true;
        }
    }
    return super.addAll(c);
}

//返回TreeSet的顺序排列的迭代器
public Iterator<E> iterator() {
    return m.navigableKeySet().iterator();
}

//返回TreeSet的逆序排列的迭代器
public Iterator<E> descendingIterator() {
    return m.descendingKeySet().iterator();
}

//添加e到TreeSet
public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}

//删除TreeSet对象
public boolean remove(Object o) {
    return m.remove(o)==PRESENT;
}

//java.io.Serializable的写入函数
//将TreeSet的“比较器、容量，所有的元素值”都写入到输出流中
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    // Write out any hidden stuff
    s.defaultWriteObject();

    // Write out Comparator
    s.writeObject(m.comparator());

    // Write out size
    s.writeInt(m.size());

    // Write out all elements in the proper order.
    for (E e : m.keySet())
        s.writeObject(e);
}

//java.io.Serializable的读取函数：根据写入方式读出
//先将TreeSet的“比较器、容量、所有的元素值”依次读出
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // Read in any hidden stuff
    s.defaultReadObject();

    // Read in Comparator
    @SuppressWarnings("unchecked")
    Comparator<? super E> c = (Comparator<? super E>) s.readObject();

    // Create backing TreeMap
    TreeMap<E,Object> tm = new TreeMap<>(c);
    m = tm;

    // Read in size
    int size = s.readInt();

    tm.readTreeSet(size, s, PRESENT);
}

LinkedHashSet

1
2
3
public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

数据结构

  • LinkedHashSet继承自HashSet，内部使用LinkHashMap
  • 内部元素有序，按插入顺序或者访问顺序