Set也是Java集合中重要的一部分,我们常见的Set有HashSet,LinkedHashSet,TreeSet,虽然平时可能不是很常用,但是基础还要有必要学习一下的。(以下源码来自jdk1.8.0_20)
HashSet
HashSet其实很简单,源代码量也比较少,学习过HashMap之后基本上看一遍就懂了,关于HashMap可以看一下之前的文章【HashMap源码深度解析】
继承结构
HashSet继承了HashSet,实现了Set接口以及Cloneable, java.io.Serializable接口。
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
成员变量
- HashSet其实是使用HashMap的key集合来实现的,所以有个HashMap成员变量
private transient HashMap<E,Object> map;
- map中的value值,set只需要使用到key集合,所以value使用new Object即可
private static final Object PRESENT = new Object();
构造函数
从HashSet的构造参数其实就是初始化了一个HashMap。
最后一个构造函数不是public声明的,而是default(同包访问权限),所以我们无法使用,这个构造函数是为了给LinkedHashSet重写用的,第三个参数其实没有作用,而是直接调用了LinkedHashMap的两个参数的构造函数,默认以插入顺序排序
public HashSet() {
map = new 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);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
主要方法
- add方法,增加一个元素,调用的HashMap的put方法
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
- contains方法,判断元素是否存在,调用的HashMap的containsKey方法
public boolean contains(Object o) {
return map.containsKey(o);
}
- remove方法,删除一个元素,调用的HashMap的remove方法,返回值和PRESENT比较。(如果不存在则返回null和PRESENT比较返回false)
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
- size方法,返回set大小,调用的HashMap的size方法
public int size() {
return map.size();
}
- isEmpty方法,判断set是否为空,调用HashMap的isEmpty方法
public boolean isEmpty() {
return map.isEmpty();
}
- clear方法,清空set中的元素,调用HashMap的clear方法
public void clear() {
map.clear();
}
- clone方法,复制set,先调用父类Object的clone方法,再调用HashMap的clone方法复制map
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);
}
}
- iterator迭代器,返回的是map的key集合的迭代器
public Iterator<E> iterator() {
return map.keySet().iterator();
}
LinkedHashSet
LinkedHashSet更加简单,继承了HashSet,构造函数调用了上面HashSet的最后一个构造函数,用LinkedHashMap实现,其他主要方法继承自HashSet,没有单独实现。
继承关系
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
构造函数
构造函数都是调用父类HashSet的构造方法,使用LinkedHashMap的key值集合来实现。
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
从上面两种set可以看出来set其实就是用对应的map的key值集合来实现的,TreeSet对应的就是有序Map了,默认是TreeMap。关于TreeMap的构造,增加删除元素之后调整的原理可以参考JAVA集合:TreeMap红黑树深度解析
继承关系
- TreeSet继承了AbstractSet类,并且实现了NavigableSet接口以及Cloneable, java.io.Serializable接口,NavigableSet接口继承了SortedSet接口。
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
成员变量
- 有序map集合,NavigableMap是SortedMap的子类
private transient NavigableMap<E,Object> m;
- map的value值
private static final Object PRESENT = new Object();
构造函数
从构造函数可以看出来TreeSet其实是用有序Map来实现的,默认使用TreeMap。
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);
}
public TreeSet(SortedSet<E> s) {
this(s.comparator());
addAll(s);
}
常用方法
- add方法,增加一个元素,直接调用TreeMap的put方法,e作为key值,value值为PRESENT。
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
- addAll方法,把集合中的元素插入到set中
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);
return true;
}
}
return super.addAll(c);
}
- first方法,获取第一个(最小的)元素,直接调用Map的firstKey,返回最左边的元素
public E first() {
return m.firstKey();
}
- last方法,获取最后一个(最大的)元素,调用Map的lastKey方法,返回最右边的元素
public E last() {
return m.lastKey();
}
- floor方法,获取小于等于给定元素的最大元素,调用Map的floorKey方法
public E floor(E e) {
return m.floorKey(e);
}
以默认的TreeMap为例
public K floorKey(K key) {
return keyOrNull(getFloorEntry(key));
}
final Entry<K,V> getFloorEntry(K key) {
Entry<K,V> p = root;
while (p != null) { //根节点不为null,进入循环,否则直接返回null
int cmp = compare(key, p.key);
if (cmp > 0) { //如果key大于当前节点
if (p.right != null) //如果right不为null,说明有更大的节点,继续循环right节点
p = p.right;
else //否则说明当前节点最大,并且小于key,直接返回
return p;
} else if (cmp < 0) { //如果key小于当前节点,则查找左子树
if (p.left != null) { //如果left不为null,继续循环left
p = p.left;
} else { //否则查找比当前节点更小的节点(向上查找)
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.left) { //如果当前节点是左孩子,说明父节点较大,继续向上查找
ch = parent;
parent = parent.parent;
} //直到节点是右孩子,此时的父节点比当前节点小,继续循环父节点
return parent;
}
} else //如果相等,直接返回
return p;
}
return null;
}
- ceiling方法,获取大于给定元素的最小元素,调用Map的getCeilingEntry方法
public E ceiling(E e) {
return m.ceilingKey(e);
}
以TreeMap为例,此方法和上面的getFloorEntry方法正好相反
public K ceilingKey(K key) {
return keyOrNull(getCeilingEntry(key));
}
final Entry<K,V> getCeilingEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp < 0) {
if (p.left != null)
p = p.left;
else
return p;
} else if (cmp > 0) {
if (p.right != null) {
p = p.right;
} else {
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
return parent;
}
} else
return p;
}
return null;
}
- higher方法,获取大于给定元素的最小元素,此方法和getCeilingEntry方法一样
public E higher(E e) {
return m.higherKey(e);
}
- lower方法,返回小于给定元素的最大元素,调用Map的getLowerEntry方法,和getFloorEntry方法一样
public E lower(E e) {
return m.lowerKey(e);
}
- pollFirst方法,返回第一个元素并删除,调用Map的pollFirstEntry方法
public E pollFirst() {
Map.Entry<E,?> e = m.pollFirstEntry();
return (e == null) ? null : e.getKey();
}
以TreeMap为例,获取第一个元素,如果不为null,则删除,如果为null,则新建一个entry返回
public Map.Entry<K,V> pollFirstEntry() {
Entry<K,V> p = getFirstEntry();
Map.Entry<K,V> result = exportEntry(p);
if (p != null)
deleteEntry(p);
return result;
}
static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
return (e == null) ? null :
new AbstractMap.SimpleImmutableEntry<>(e);
}
- pollLast方法,返回最后一个元素并删除,和pollFirst对应
public E pollLast() {
Map.Entry<E,?> e = m.pollLastEntry();
return (e == null) ? null : e.getKey();
}
- contains方法,判断是否含有给定的元素,调用Map的containsKey方法
public boolean contains(Object o) {
return m.containsKey(o);
}
- remove方法,删除给定的元素,调用Map的remove方法
public boolean remove(Object o) {
return m.remove(o)==PRESENT;
}
- clear方法,清空set中的元素,调用Map的clear方法
public void clear() {
m.clear();
}
- isEmpty方法,判断set是否为空,调用Map的isEmpty方法
public boolean isEmpty() {
return m.isEmpty();
}
- iterator迭代器,返回Map的key值集合的迭代器
public Iterator<E> iterator() {
return m.navigableKeySet().iterator();
}
- subSet,获取子set
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive) {
return new TreeSet<>(m.subMap(fromElement, fromInclusive,
toElement, toInclusive));
}
总结
- HashSet其实是使用HashMap的key值集合来实现的,所以不能有重复的元素。
- LinkedHashSet继承了HashSet,用LinkedHashMap的key值集合来实现其功能,所以不能有重复元素,并且以插入元素的顺序排序。
- TreeSet是使用有序的Map来实现的,默认使用的是TreeMap。
Set其实就是Map的key集合,用Map来实现Set,所以掌握了Map基本上就学会了Set。