Set集合中不含有重复的元素，插入重复的元素会失败。常用的有HashSet LinkedHashSet TreeSet。HashSet是无序的集合，LinkedHashSet中的排序和插入成功的顺序一致重复插入，TreeSet中元素是有序排列的，排序的依据是自身的comparator如果为null则根据key从小到大排序。HashSet和LinkedHashSet都是支持插入null的，TreeSet是否支持视comparator的情况，如果comparator不支持比较null的大小或者没有自定义的comparator则不支持插入null
HashSet
HashSet是基于HashMap实现的Set集合，所以支持插入null，但是不保持任何顺序。add成功时返回true，add已有元素时返回false。remove已有元素成功时返回true，remove不存在的元素时失败返回false。和HashMap一样是非线程安全类
public static void main(String args[]){
Set<String> set = new HashSet<>();
System.out.println(set.add("123"));//true
System.out.println(set.add("123"));//false
System.out.println(set.add(null));//true
System.out.println(set.remove(null));//true
System.out.println(set.remove(null));//false
}
定义与构造函数
首先从定义上来看，HashSet实现的是Set接口，Set是一种没有重复元素的集合，比如HashMap的KeySet就是一种Set集合
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
从属性中可以看出，他是基于HashMap来实现的，PRESENT是Map跟底层Map相关联的虚拟值，实际上所有对HashSet的操作底层都可以理解为value=PRESENT的对HashMap的操作，后面几个方法中会用到
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
然后来看构造函数，无参构造默认构建一个大小为16，负载因子为0.75的HashMap；复制构造时取c/0.75+1和16中的较大值作为大小，负载因子0.75；可以单独设定初始大小，负载因子取默认的0.75，也可以同时指定负载因子；最后一种HashSet(int initialCapacity, float loadFactor, boolean dummy)是内部方法只有LinkedHashSet使用，构建一个链表式HashSet，底层是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);
}
对集合的操作函数
上面提到了，HashSet底层是基于HashMap的KeySet，所有value都是PRESENT，所以只需要增加参数后复用HashMap的操作即可完成大部分对HashSet的操作
//返回迭代器
public Iterator<E> iterator() {
return map.keySet().iterator();
}
//返回元素个数
public int size() {
return map.size();
}
//返回集合是否为空
public boolean isEmpty() {
return map.isEmpty();
}
//返回Set中是否含有某个对象，底层通过HashMap.containKey实现
public boolean contains(Object o) {
return map.containsKey(o);
}
//添加元素e，对于底层来说相等于添加键值对(e,PRESENT)，因为map.put会返回旧元素值，而set中不含有重复值，所以若直接map中不存在e则返回null此时函数返回true；而已有e时返回的是e，函数返回值为false
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
//移除某个对象，map.remove方法移除了已有的键值对返回的是value的值，对于Set来说也就是PRESENT，所以返回PRESENT相当于移除成功返回true
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
//直接清除map中的所有对象
public void clear() {
map.clear();
}
clone方法就是先复制一个空的HashSet，然后通过map.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);//因为HashSet和HashMap都实现了clone接口，这个错误理论上不会出现
}
}
spliterator基于HashMap.KeySpliterator生成一个初始大小为空的分裂器
public Spliterator<E> spliterator() {
return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0);
}
序列化函数
writeObject基本上就是HashMap的基础上去掉了value值的写入。readObject先读取基本参数，并调整大小保证集合至少有0.25的负载率，最后新建底层的Map并读取元素插入集合。
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// 写入隐藏的序列化对象
s.defaultWriteObject();
// 写入HashMap的大小和负载因子
s.writeInt(map.capacity());
s.writeFloat(map.loadFactor());
// 写入元素个数
s.writeInt(map.size());
// 依次写入所有元素
for (E e : map.keySet())
s.writeObject(e);
}
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// 读取隐藏的序列化对象
s.defaultReadObject();
// 读取大小并检验不是负值
int capacity = s.readInt();
if (capacity < 0) {
throw new InvalidObjectException("Illegal capacity: " +
capacity);
}
// 读取负载因子，并检验是正数且不是NaN
float loadFactor = s.readFloat();
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new InvalidObjectException("Illegal load factor: " +
loadFactor);
}
// 读取元素个数并检验是非负数
int size = s.readInt();
if (size < 0) {
throw new InvalidObjectException("Illegal size: " +
size);
}
// 重设大小，HashMap的大小需要至少有25%的负载率
capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f),
HashMap.MAXIMUM_CAPACITY);
// 创建底层HashMap，若本身是LinkedHashSet则创建LinkedHashSet
map = (((HashSet<?>)this) instanceof LinkedHashSet ?
new LinkedHashMap<E,Object>(capacity, loadFactor) :
new HashMap<E,Object>(capacity, loadFactor));
// 从流中顺序读取所有元素，并以map.put(e, PRESENT)的方式加入到map中
for (int i=0; i<size; i++) {
@SuppressWarnings("unchecked")
E e = (E) s.readObject();
map.put(e, PRESENT);
}
}
LinkedHashSet
LinkedHashSet是基于LinkedHashMap实现的，所以也支持插入null并且可以保持元素的顺序一定和插入顺序是一致的，同时插入同一个元素而失败时不会影响排序。整个集合完全是基于其他类实现的，所以代码非常少。先看一下关键的构造函数部分，基本上如前面HashSet中提到，这个true的参数除了鉴别重载类型外没有实际意义，而LinkedHashMap在新建时没有给出accessOrder参数所以默认是插入顺序。复制构造这里有些不同，初始大小是c的元素个数2倍和11中的较大值，而不是一般的16
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);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
分裂器是重写过的，Spliterator.DISTINCT | Spliterator.ORDERED代表这个分裂器的集合是不重复的且有序的
public Spliterator<E> spliterator() {
return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
}
TreeSet
TreeSet是一个排序Set，并且他在没有重写过支持null的comparator的情况下是不支持插入null的
public static void main(String args[]){
Set<String> set = new TreeSet<>();
System.out.println(set.add("123"));//true
System.out.println(set.add("123"));//false
//System.out.println(set.add(null));报错
//System.out.println(set.remove(null));报错
System.out.println(set.remove("123"));//true
System.out.println(set.remove("123"));//false
}
定义与构造函数
首先我们可以看到TreeSet实现的接口就和HashSet不同，是NavigableSet说明这是一个有序排列的Set，底层基于TreeMap实现的NavigableMap接口，同时也是使用一个内存中共享的PRESENT作为虚假的value值。
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
private transient NavigableMap<E,Object> m;
private static final Object PRESENT = new Object();
之前在TreeMap解析中提到过比较器的问题，如果不在构造时给出新的构造器，则默认根据key的大小来排序，此时若key是不能比较类或抛出错误。构造函数可以看出除非在构造时直接给出comparator或者根据SortedSet进行复制构造，否则都是按key自身来进行排序
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);
}
集合操作函数
TreeSet除了可以返回升序的迭代器外，还可以返回降序的迭代器和降序的Set，在TreeMap中分析过，这里的遍历是对红黑树的中序遍历，而降序迭代器只是改变了指针移动的顺序，对于descendingSet来说因为TreeMap.descendingMap()是返回的自身而新建的TreeSet中只是将这个返回结果设为m，所以对descendingSet的操作会直接反映到原本的TreeSet上面。
public Iterator<E> iterator() {
return m.navigableKeySet().iterator();
}
public Iterator<E> descendingIterator() {
return m.descendingKeySet().iterator();
}
public NavigableSet<E> descendingSet() {
return new TreeSet<>(m.descendingMap());
}
add和remove操作和HashSet的设计一样以PRESENT作为虚假的value值进行操作，由于TreeMap在使用key默认排序时不支持以null作为key，所以对于没有设置comparator时插入null会抛出java.lang.NullPointerException错误
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return m.remove(o)==PRESENT;
}
然后是addAll方法，在自身的底层集合为空，c不为空，c是SortedMap，自身的底层集合是TreeMap时可以通过addAllForTreeSet调用buildFromSorted来完成线性时间的构建，否则只能一个个插入树中，一次插入时间复杂度为O(lgn)，n是size大小
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) {//自身的底层集合为空，c不为空，c是SortedMap，自身的底层集合是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))) {//双方的comparator相等
map.addAllForTreeSet(set, PRESENT);
return true;
}
}
return super.addAll(c);
}
//仅供TreeSet使用
void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
try {
buildFromSorted(set.size(), set.iterator(), null, defaultVal);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
下边几个子集函数，参数中int的XXElement都是下标类参数，Inclusive代表这个下标元素本身是否包含在截取范围内，因为TreeMap中所有子集操作都是基于自身而没有复制元素，所以对于以下这些子集的修改都会反映到TreeSet上面
//截取fromElement到toElement间，Inclusive为true时为下标自身包含在范围内
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive) {
return new TreeSet<>(m.subMap(fromElement, fromInclusive,
toElement, toInclusive));//fromElement、toElement是截取的下标范围，Inclusive为true时本身也包括在内
}
//截取小于（inclusive为true时为小于等于）toElement的子集
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
return new TreeSet<>(m.headMap(toElement, inclusive));
}
//截取大于（inclusive为true时为小于等于）fromElement的子集
public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
return new TreeSet<>(m.tailMap(fromElement, inclusive));
}
//截取包含从fromElement开始到不含toElement结束的子集
public SortedSet<E> subSet(E fromElement, E toElement) {
return subSet(fromElement, true, toElement, false);
}
//截取小于toElement的子集
public SortedSet<E> headSet(E toElement) {
return headSet(toElement, false);
}
//截取大于等于fromElement的子集
public SortedSet<E> tailSet(E fromElement) {
return tailSet(fromElement, true);
}
下面几个都是查询方法，直接通过TreeMap对应的函数来寻找指定的值
public E first() {
return m.firstKey();//返回最小的元素
}
public E last() {
return m.lastKey();//返回最大的元素
}
public E lower(E e) {
return m.lowerKey(e);//返回大于e的元素中最小的
}
public E floor(E e) {
return m.floorKey(e);//返回小于e的元素中最大的
}
public E ceiling(E e) {
return m.ceilingKey(e);//返回大于等于e的元素中最小的
}
public E higher(E e) {
return m.higherKey(e);//返回小于等于e的元素中最大的
}
poll在查询的基础上如果查找成功会删除对应的元素，只能从最小和最大的开始删除
public E pollFirst() {
Map.Entry<E,?> e = m.pollFirstEntry();//删除最小的结点
return (e == null) ? null : e.getKey();
}
public E pollLast() {
Map.Entry<E,?> e = m.pollLastEntry();//删除最大的结点
return (e == null) ? null : e.getKey();
}
TreeMap的clone方法复制了底层的集合但没有复制元素本身，也就是说对树的操作相互之间不影响，但是对相同元素的操作是相互影响的。比如说Set中的元素是一个bean，将原TreeSet中第一个元素的某个属性修改了，clone出的TreeSet中的第一个元素也会改变，这点前面两个Set类也是同样的。
public Object clone() {
TreeSet<E> clone;
try {
clone = (TreeSet<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
clone.m = new TreeMap<>(m);//复制出一个新的TreeMap
return clone;
}
序列化
writeObject比较容易看懂，就是依次写入比较器、元素个数和每个元素，元素的顺序是树的中序遍历顺序
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// 写入任何隐藏的部分
s.defaultWriteObject();
// 写入比较器
s.writeObject(m.comparator());
// 写入元素个数
s.writeInt(m.size());
// 根据迭代器的顺序也就是key从小到大写入所有元素
for (E e : m.keySet())
s.writeObject(e);
}
readObject先读取比较器和大小，然后通过TreeMap.readTreeSet从流中读取构建一个TreeMap
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// 读入隐藏部分
s.defaultReadObject();
// 读入比较器
@SuppressWarnings("unchecked")
Comparator<? super E> c = (Comparator<? super E>) s.readObject();
// 创建一个TreeMap设为m
TreeMap<E,Object> tm = new TreeMap<>(c);
m = tm;
// 读入元素个数
int size = s.readInt();
tm.readTreeSet(size, s, PRESENT);
}
//只有TreeSet.readObject调用
void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
throws java.io.IOException, ClassNotFoundException {
buildFromSorted(size, null, s, defaultVal);//从流中读取构建一个TreeMap
}
