集合框架 Set篇—HashSet、LinkedHashSet、TreeSet、CopyOnWriteArraySet、ConcurrentSkipListSet

  categories:资料  author:

来源:互联网

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



快乐成长 每天进步一点点