来源：互联网
Set
---------
1.HashSet
2.LinkedHashSet
3.TreeSet
4.CopyOnWriteArraySet
5.ConcurrentSkipListSet
---------------------HashSet-------------------------
HashSet实现了AbstractSet，由下面的HashSet源码容易看出，其内部依赖于HashMap的实现。其迭代顺序是不能保证的，元素存储是无序的。
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable{
/*----------成员变量-------------*/
private transient HashMap<E,Object>map;//内部的实现依赖于HashMap
// 一个Object对象作为HashMap中value值的填充，该值对set来说是没有什么意义的
private static final Object PRESENT = new Object();
/*------------------------------*/
/*----------构造方法-------------*/
/**
*创建一个空的集合，实际上创建一个空的HashMap
*/
public HashSet() {
map = new HashMap<E,Object>();
}
/**
* 把集合作为set的初始化数据，并对对应的HashMap的容量进行指定
*/
public HashSet(Collection<? extends E> c) {
map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
/**
* 指定初始容量及负载因子（这些概念可以参考HashMap的实现部分）
*/
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<E,Object>(initialCapacity, loadFactor);
}
/**
* 指定初始容量（默认负载因子为0.75）
*/
public HashSet(int initialCapacity) {
map = new HashMap<E,Object>(initialCapacity);
}
/**
*创建一个以LinkedHashMap为实现的LinkedHashSet时，调用该构造方法
*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = newLinkedHashMap<E,Object>(initialCapacity, loadFactor);
}
/*------------------------------*/
/**
* 通过HashMap的keySet返回一个无序的迭代器Iterator
*/
public Iterator<E> iterator() {
return map.keySet().iterator();
}
/**
* 集合中元素的个数
*/
public int size() {
return map.size();
}
/**
* 判断集合是否为空
*/
public boolean isEmpty() {
return map.isEmpty();
}
/**
*是否包含某个元素
*/
public boolean contains(Object o) {
return map.containsKey(o);
}
/**
* 添加元素的操作
*/
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
/**
* 删除元素的操作
*/
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
/**
* 清空集合
*/
public void clear() {
map.clear();
}
/**
* 返回一个集合的“浅拷贝”对象
*/
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();
}
}
/**
* 持久化集合时的写操作
*/
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 (Iterator i=map.keySet().iterator(); i.hasNext(); )
s.writeObject(i.next());
}
/**
* 持久化集合时的读操作
*/
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
s.defaultReadObject();
// Read in HashMap capacity and load factor and create backing HashMap
int capacity = s.readInt();
float loadFactor = s.readFloat();
map = (((HashSet)this) instanceof LinkedHashSet ? new LinkedHashMap<E,Object>(capacity, loadFactor) :
new HashMap<E,Object>(capacity, loadFactor));
// Read in size
int size = s.readInt();
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
E e = (E) s.readObject();
map.put(e, PRESENT);
}
}
}
---------------------LinkedHashSet-------------------------
//下面就是LinkedHashSet的主要实现，内部出了构造方法，没有其他的任何代码，LinkedHashSet是HashSet的实现，
//通过调用HashSet中的构造方法，其背后是依赖于LinkedHashMap实现的，所以可以保持集合的元素的插入的顺序。
public class LinkedHashSet<E> extends HashSet<E>implements Set<E>, Cloneable, java.io.Serializable {
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-------------------------
//TreeSet，一个排序的Set集合，底层依赖于TreeMap的实现
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable{
private transient NavigableMap<E,Object> m; //TreeMap也实现了NavigableMap接口
private static final Object PRESENT = new Object(); //一个虚拟的填充值用的对象（对set集合没有实际意义）
/*--------------构造方法--------------*/
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
public TreeSet() {
this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<E,Object>(comparator));
}
public TreeSet(Collection<? extends E> c) {
this();
addAll(c);
}
public TreeSet(SortedSet<E> s) {
this(s.comparator());
addAll(s);
}
/*------------------------------------*/
/**
* 返回升序（asc）排列集合的迭代器
*/
public Iterator<E> iterator() {
return m.navigableKeySet().iterator();
}
/**
* 返回降序（desc）排列集合的迭代器
*/
public Iterator<E> descendingIterator() {
return m.descendingKeySet().iterator();
}
/**
* 返回一个降序的Set集合
*/
public NavigableSet<E> descendingSet() {
return new TreeSet(m.descendingMap());
}
/**
* 元素个数size
*/
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;
}
/**
*移除元素
*/
public boolean remove(Object o) {
return m.remove(o)==PRESENT;
}
/**
* 清空集合
*/
public void clear() {
m.clear();
}
/**
* 把给定的集合中的元素添加到set集合中（依赖于TreeMap的实现）
*/
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<? super E> cc = (Comparator<? super E>) 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);
}
/*--以下是由于实现-NavigableSet和SortedSet接口而实现的一些方法，根据方法名很容易判断其作用，不再一一说明----*/
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
return new TreeSet<E>(m.subMap(fromElement, fromInclusive, toElement, toInclusive));
}
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
return new TreeSet<E>(m.headMap(toElement, inclusive));
}
public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
return new TreeSet<E>(m.tailMap(fromElement, inclusive));
}
public SortedSet<E> subSet(E fromElement, E toElement) {
return subSet(fromElement, true, toElement, false);
}
public SortedSet<E> headSet(E toElement) {
return headSet(toElement, false);
}
public SortedSet<E> tailSet(E fromElement) {
return tailSet(fromElement, true);
}
public Comparator<? super E> comparator() {
return m.comparator();
}
public E first() {
return m.firstKey();
}
public E last() {
return m.lastKey();
}
// NavigableSet API methods
public E lower(E e) {
return m.lowerKey(e);
}
public E floor(E e) {
return m.floorKey(e);
}
public E ceiling(E e) {
return m.ceilingKey(e);
}
public E higher(E e) {
return m.higherKey(e);
}
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();
}
//writeObject readObject等方法没有一一列出
}
--------------------CopyOnWriteArraySet----------------
CopyOnWriteArraySet是一个依赖CopyOnWriteArrayList实现的 Set集合。因此，它共享以下相同的基本属性：
-它最适合于具有以下特征的应用程序：set 大小通常保持很小，只读操作远多于可变操作，需要在遍历期间防止线程间的冲突。
-它是线程安全的。
-因为通常需要复制整个基础数组，所以可变操作（add、set 和 remove 等等）的开销很大。
-迭代器不支持可变 remove 操作。
-使用迭代器进行遍历的速度很快，并且不会与其他线程发生冲突。在构造迭代器时，迭代器依赖于不变的数组快照。
//CopyOnWriteArraySet的源码实现
public class CopyOnWriteArraySet<E> extends AbstractSet<E> implements java.io.Serializable {
private final CopyOnWriteArrayList<E> al;//内部实现所依赖的CopyOnWriteArrayList对象
/**
* 空构造
*/
public CopyOnWriteArraySet() {
al = new CopyOnWriteArrayList<E>();
}
/**
* 传入集合变量的构造
*/
public CopyOnWriteArraySet(Collection<? extends E> c) {
al = new CopyOnWriteArrayList<E>();
al.addAllAbsent(c);
}
/**
* 通过调用CopyOnWriteArrayList的方法，实现该Set集合的操作
*/
public int size() {
return al.size();
}
public boolean isEmpty() {
return al.isEmpty();
}
public boolean contains(Object o) {
return al.contains(o);
}
public Object[] toArray() {
return al.toArray();
}
public <T> T[] toArray(T[] a) {
return al.toArray(a);
}
public void clear() {
al.clear();
}
public boolean remove(Object o) {
return al.remove(o);
}
public boolean add(E e) {
return al.addIfAbsent(e);//这就保证了Set集合不存在相同的元素
}
public boolean containsAll(Collection<?> c) {
return al.containsAll(c);
}
public boolean addAll(Collection<? extends E> c) {
return al.addAllAbsent(c) > 0;
}
public boolean removeAll(Collection<?> c) {
return al.removeAll(c);
}
public boolean retainAll(Collection<?> c) {
return al.retainAll(c);
}
public Iterator<E> iterator() {
return al.iterator();
}
/**
* 重写Set的equals方法：作用是比较两个set集合的是否相等
*/
public boolean equals(Object o) {
if (o == this) //如果是同一个set对象,就相等
return true;
if (!(o instanceof Set))//不是Set类别，不可能相等
return false;
Set<?> set = (Set<?>)(o);
Iterator<?> it = set.iterator();
// 下面的算法复杂度为O(n^2)，所以CopyOnWriteArraySet过大的情况效率会比较低，不推荐。
// Use a single snapshot of underlying array
Object[] elements = al.getArray();
int len = elements.length;
// Mark matched elements to avoid re-checking
boolean[] matched = new boolean[len];
int k = 0;
//通过迭代比较每一个元素是否和al.getArray()获得的数组元素是否相同
outer: while (it.hasNext()) {
if (++k > len)
return false;
Object x = it.next();
for (int i = 0; i < len; ++i) {
if (!matched[i] && eq(x, elements[i])) {
matched[i] = true;
continue outer;
}
}
return false;
}
return k == len;
}
/**
* 考虑null的情况下，判断equals
*/
private static boolean eq(Object o1, Object o2) {
return (o1 == null ? o2 == null : o1.equals(o2));
}
}
-------------------ConcurrentSkipListSet--------------------------
ConcurrentSkipListSet 是一个基于 ConcurrentSkipListMap 的可缩放并发 NavigableSet 实现。set 的元素可以根据它们的自然顺序进行排序，也可以根据创建 set 时所提供的 Comparator 进行排序，具体取决于使用的构造方法。
此实现为 contains、add、remove 操作及其变体提供预期平均 log(n) 时间开销。多个线程可以安全地并发执行插入、移除和访问操作。
//ConcurrentSkipListSet的源码实现
public class ConcurrentSkipListSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable {
private final ConcurrentNavigableMap<E,Object> m;//基于 ConcurrentSkipListMap
/*---------------------------构造方法-----------------------------*/
public ConcurrentSkipListSet() {
m = new ConcurrentSkipListMap<E,Object>();
}
public ConcurrentSkipListSet(Comparator<? super E> comparator) {
m = new ConcurrentSkipListMap<E,Object>(comparator);
}
public ConcurrentSkipListSet(Collection<? extends E> c) {
m = new ConcurrentSkipListMap<E,Object>();
addAll(c);
}
public ConcurrentSkipListSet(SortedSet<E> s) {
m = new ConcurrentSkipListMap<E,Object>(s.comparator());
addAll(s);
}
ConcurrentSkipListSet(ConcurrentNavigableMap<E,Object> m) {
this.m = m;
}
/*-----------------------------------------------------------------*/
public ConcurrentSkipListSet<E> clone() {
ConcurrentSkipListSet<E> clone = null;
try {
clone = (ConcurrentSkipListSet<E>) super.clone();
clone.setMap(new ConcurrentSkipListMap(m));
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
return clone;
}
/* ----------------基于 ConcurrentSkipListMap，实现该Set集合的操作 -------------- */
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.putIfAbsent(e, Boolean.TRUE) == null;
}
public boolean remove(Object o) {
return m.remove(o, Boolean.TRUE);
}
public void clear() {
m.clear();
}
public Iterator<E> iterator() {
return m.navigableKeySet().iterator();
}
public Iterator<E> descendingIterator() {
return m.descendingKeySet().iterator();
}
/* ---------------- 重写AbstractSet 的equals方法-------------- */
public boolean equals(Object o) {
// Override AbstractSet version to avoid calling size()
if (o == this)
return true;
if (!(o instanceof Set))
return false;
Collection<?> c = (Collection<?>) o;
try {
return containsAll(c) && c.containsAll(this);
} catch (ClassCastException unused) {
return false;
} catch (NullPointerException unused) {
return false;
}
}
public boolean removeAll(Collection<?> c) {
// Override AbstractSet version to avoid unnecessary call to size()
boolean modified = false;
for (Iterator<?> i = c.iterator(); i.hasNext(); )
if (remove(i.next()))
modified = true;
return modified;
}
/* ---------------- 实现NavigableSet接口的操作-------------- */
public E lower(E e) {
return m.lowerKey(e);
}
public E floor(E e) {
return m.floorKey(e);
}
public E ceiling(E e) {
return m.ceilingKey(e);
}
public E higher(E e) {
return m.higherKey(e);
}
public E pollFirst() {
Map.Entry<E,Object> e = m.pollFirstEntry();
return e == null? null : e.getKey();
}
public E pollLast() {
Map.Entry<E,Object> e = m.pollLastEntry();
return e == null? null : e.getKey();
}
/* ---------------- 实现SortedSet接口的操作 -------------- */
public Comparator<? super E> comparator() {
return m.comparator();
}
public E first() {
return m.firstKey();
}
public E last() {
return m.lastKey();
}
public NavigableSet<E> subSet(E fromElement,boolean fromInclusive, E toElement, boolean toInclusive) {
return new ConcurrentSkipListSet<E>(m.subMap(fromElement, fromInclusive, toElement, toInclusive));
}
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
return new ConcurrentSkipListSet<E>(m.headMap(toElement, inclusive));
}
public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
return new ConcurrentSkipListSet<E>(m.tailMap(fromElement, inclusive));
}
public NavigableSet<E> subSet(E fromElement, E toElement) {
return subSet(fromElement, true, toElement, false);
}
public NavigableSet<E> headSet(E toElement) {
return headSet(toElement, false);
}
public NavigableSet<E> tailSet(E fromElement) {
return tailSet(fromElement, true);
}
public NavigableSet<E> descendingSet() {
return new ConcurrentSkipListSet(m.descendingMap());
}
// Support for resetting map in clone
private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long mapOffset;
static {
try {
mapOffset = unsafe.objectFieldOffset(ConcurrentSkipListSet.class.getDeclaredField("m"));
} catch (Exception ex) { throw new Error(ex); }
}
private void setMap(ConcurrentNavigableMap<E,Object> map) {
unsafe.putObjectVolatile(this, mapOffset, map);
}
}
http://hi.baidu.com/yao1111yao/item/6f812cde91f1921ed78ed091
