Java容器框架源码阅读笔记（三）Set

| |

java.util.Set框架：
Set接口框架

Set

Set对Map进行了包裹,利用Map中key的唯一性保证集合中元素的唯一性，所有的key指向同一个对象。

HashSet

直接用的HashMap，元素的顺序是不确定的，查找删除等操作的时间复杂度为O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13

// 所有key指向这个对象
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

public HashSet() {
    map = new HashMap<>();
}

// 返回值是boolean，可以判断是否插入成功，也就是说是否已经存在相应的元素e
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

LinkedHashSet

直接用的LinkedHashMap,元素的顺序是确定的，查找删除等操作的时间复杂度为O(1)。

1
2
3
4
5
6
public LinkedHashSet() {
    super(16, .75f, true);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

TreeSet

直接用的TreeMap，元素是有序的，查找删除等操作的时间复杂度为O(logn)。元素是有序的，顺序是按照key的自然顺序或者是定义的Comparator。 构建线程安全的TreeSet：SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));

1
2
3
public TreeSet() {
    this(new TreeMap<E,Object>());
}

参考

Related Posts