Set的常用实现类源码分析
程序员文章站
2022-04-15 14:38:00
...
Set
的实现基本上是依靠于相应的Map
实现,所以要了解Set
,只需要去分析相应的Map
就可以了。
Set
实现类的继承关系图
HashSet
源码简要分析
翻开源码我们我可以清楚地看到HashSet
中有一个变量map,它的类型是HashMap
。不难想象,HashMap
的键值是一个不可重复的集合,它刚好就可以当做是一个Set
,也不难理解为什么要叫HashSet
。
private transient HashMap<E,Object> map;
public HashSet() {//在构造方法中,new一个HaskMap对象
map = new HashMap<>();
}
在HashSet
中,总共有5个构造方法(包括上面的构造方法)。在其他的方法中,也同样是new一个HashMap
或LinkedHashMap
。如下:
使用HashMap
:
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
使用LinkedHashMap
:此方法将作为LinkedHashSet
中的构造方法主要调用的方法。
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
在看增删改查:基本上是调用HashMap
的相应操作方法。增加元素的时候,值传PRESENT
给HashMap
。
// 用来充当Map键值对中的值
private static final Object PRESENT = new Object();
public boolean contains(Object o) {
return map.containsKey(o);
}
public boolean add(E e) {// 值传PRESENT
return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
public boolean isEmpty() {
return map.isEmpty();
}
public int size() {
return map.size();
}
public Iterator<E> iterator() {
return map.keySet().iterator();
}
public void clear() {
map.clear();
}
从整体上面来看,HashSet
是对HashMap
的二次封装。关键还是在于HashMap
的实现之上。
LinkedHashSet
的源代码分析
它的所有方法以及成员变量如下图所示: LinkedHashSet
继承自HashSet
。因此它是一个对HashSet
的再次封装。它有5个函数,4个是构造函数。而且这些构造函数都将调用HashSet
中的HashSet(int initialCapacity, float loadFactor, boolean dummy)
方法。如下:
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
public LinkedHashSet() {
super(16, .75f, true);
}
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
TreeSet
源代码简要分析
先再来单独看看其继承关系:
再来看其构造函数与重要的成员变量:
// 应该与上面的HashSet类似,用来存储
private transient NavigableMap<E,Object> m;
// 应该是用来填充键值对中的值
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));
}
public TreeSet(Collection<? extends E> c) {
this();
addAll(c);
}
从4个构造方法中,我们可以大致看出,这个NavigableMap
是一个接口,而TreeMap
实现了此接口,并在此处最为元素的实际存储载体。没有用过TreeMap
,但是此处TreeSet
想必是与HashSet
的实现类似的——封装TreeMap
。接着,我们来看其中的一些具体实现:
public int size() {
return m.size();
}
public boolean isEmpty() {
return m.isEmpty();
}
public boolean contains(Object o) {
return m.containsKey(o);
}
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
//后续不再列举...
这个集合是有序的,后续的解读留给TreeMap
吧!