Java容器类(3)-Set

主要源码分析,容器类关系图

Posted by zhidaliao on October 22, 2016

This document is not completed and will be updated anytime.

点击查看大图

普通容器类

Collections关系图1

Set

存在相同的元素则不插入。

Set接口主要是增删查改遍历操作。

public interface Set<E> extends Collection<E> {
        
    int size();

    
    boolean isEmpty();

    
    boolean contains(Object o);

    
    Iterator<E> iterator();

    
    Object[] toArray();

    
    <T> T[] toArray(T[] a);


    // Modification Operations

    
    boolean add(E e);

    boolean remove(Object o);

    // Bulk Operations

    
    boolean containsAll(Collection<?> c);

    
    boolean addAll(Collection<? extends E> c);

    
    boolean retainAll(Collection<?> c);

    
    boolean removeAll(Collection<?> c);

    
    void clear();


    // Comparison and hashing

    
    boolean equals(Object o);

    
    int hashCode();
}

SortedSet

SortedSet接口,主要有比较器、截取、返回头尾操作。

子类有:ConcurrentSkipListSet, TreeSet

public interface SortedSet<E> extends Set<E> {
    
    Comparator<? super E> comparator();

    
    SortedSet<E> subSet(E fromElement, E toElement);

    
    SortedSet<E> headSet(E toElement);

    
    SortedSet<E> tailSet(E fromElement);

    
    E first();

    
    E last();
}

只是定义了一个接口,包含了更多样化的操作

public interface NavigableSet<E> extends SortedSet<E> {
    
    // 返回小于e元素的最大值
    E lower(E e);

    
    E floor(E e);

    // 大于或等于指定元素的 最小元素
    E ceiling(E e);

    
    E higher(E e);

    // 获取和移除第一个元素
    E pollFirst();

    
    E pollLast();

    
    Iterator<E> iterator();

    
    NavigableSet<E> descendingSet();

    
    Iterator<E> descendingIterator();

    
    NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement,   boolean toInclusive);
    
    NavigableSet<E> headSet(E toElement, boolean inclusive);

    
    NavigableSet<E> tailSet(E fromElement, boolean inclusive);

    
    SortedSet<E> subSet(E fromElement, E toElement);
 
    SortedSet<E> headSet(E toElement);

    
    SortedSet<E> tailSet(E fromElement);
}

HashSet

底层使用Map数据结构,所有操作都是对Map进行的。使用哈希值做索引。通过Map的键不能重复的特性实现不重复元素的要求

public class HashSet<E>  extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable
{

    private transient HashMap<E,Object> map;

    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }

    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }
    
    // 注意这个构造方法,底层使用的是 LinkedHashMap 数据结构
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

    ...
}

LinkedHashSet

LinkedHashSet 继承自HashSet, 代码量很少, 通过HashSet的源码可以得知,底层使用LinkedHashMap保存,Entry中存在链表指针

public class LinkedHashSet<E> extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

    private static final long serialVersionUID = -2851667679971038690L;
 
    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);
    }
}

EnumSet

建立枚举值的集合,没有什么特别的

public abstract class EnumSet<E extends Enum<E>> extends AbstractSet<E>
    implements Cloneable, java.io.Serializable
{
     
    final Class<E> elementType;

    final Enum[] universe;

    private static Enum[] ZERO_LENGTH_ENUM_ARRAY = new Enum[0];

    EnumSet(Class<E>elementType, Enum[] universe) {
        this.elementType = elementType;
        this.universe    = universe;
    }

    public static <E extends Enum<E>> EnumSet<E> of(E e) {
        EnumSet<E> result = noneOf(e.getDeclaringClass());
        result.add(e);
        return result;
    }

    public static <E extends Enum<E>> EnumSet<E> range(E from, E to) {
        if (from.compareTo(to) > 0)
            throw new IllegalArgumentException(from + " > " + to);
        EnumSet<E> result = noneOf(from.getDeclaringClass());
        result.addRange(from, to);
        return result;
    }
  
    // 返回所有elementType的元素
    private static <E extends Enum<E>> E[] getUniverse(Class<E> elementType) {
        return SharedSecrets.getJavaLangAccess()
                                        .getEnumConstantsShared(elementType);
    }

    ...
}

TreeSet

TreeSet extends `AbstractSet` implements `NavigableSet`

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();

    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }

    public TreeSet() {
        this(new TreeMap<E,Object>());
    }

    public TreeSet() {
        this(new TreeMap<E,Object>());
    }

    public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    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);
    }

    ...

    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
}

可以看出来 TreeSet底层是用 TreeMap 来保存元素

根据add方法可以推断, 值是 Object PRESENT = new Object(); ,一个无意义的对象, 使用 Map的结构用来保持 键值不会重复。

public Iterator<E> iterator() {
    return m.navigableKeySet().iterator();
}

遍历也是使用 TreeMap 的遍历方法 . 使用红黑树保持顺序


同步容器类

collections.synchronizedSet / collections.synchronizedSortedSet

客户端加锁,避免兵法修改异常

SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
      ...
synchronized (s) {
  Iterator i = s.iterator(); // Must be in the synchronized block
  while (i.hasNext())
      foo(i.next());
}

并发容器类

ConcurrentSkipListSet

底层使用 ConcurrentSkipListMap ,具体的介绍可以查看 Map 的那篇文章

public class ConcurrentSkipListSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable {

    private static final long serialVersionUID = -2479143111061671589L;

    private final ConcurrentNavigableMap<E,Object> m;
    
    public ConcurrentSkipListSet() {
        m = new ConcurrentSkipListMap<E,Object>();
    }

    ...
}

CopyOnWriteArraySet

CopyOnWriteArraySet内部持有一个CopyOnWriteArrayList引用,所有操作都是基于对CopyOnWriteArrayList的操作。


public class CopyOnWriteArraySet<E> extends AbstractSet<E>  implements java.io.Serializable {

    private final CopyOnWriteArrayList<E> al;

    ...
}

add方法 ,调用的是 CopyOnWriteArrayList 的 addIfAbsent

public boolean addIfAbsent(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        // Copy while checking if already present.
        // This wins in the most common case where it is not present
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = new Object[len + 1];
        for (int i = 0; i < len; ++i) {
            if (eq(e, elements[i]))
                return false; // exit, throwing away copy
            else
                newElements[i] = elements[i];
        }
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}