Java8集合系列之Set（六）

所有Set几乎都是内部用一个Map来实现, 因为Map里的KeySet就是一个Set，而value采用假值，全部使用同一个Object即可。

HashSet

构造方法

HashSet底层就是典型的用HashMap来实现的，构造方法如下：

/**
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
 * default initial capacity (16) and load factor (0.75).
 */
public HashSet() {
    map = new HashMap<>();
}

add

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

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

remove

public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

iterator

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

CopyOnWriteArraySet

CopyOnWriteArraySet则以CopyOnWriteArrayList作为底层数据结构，构造方法如下。

构造方法

private final CopyOnWriteArrayList<E> al;
public CopyOnWriteArraySet() {
    al = new CopyOnWriteArrayList<E>();
}

add

public boolean add(E e) {
    return al.addIfAbsent(e);
}

最终调用CopyOnWriteArrayList的addIfAbsent方法，代码如下：

public boolean addIfAbsent(E e) {
    Object[] snapshot = getArray();
    return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
        addIfAbsent(e, snapshot);
}

private boolean addIfAbsent(E e, Object[] snapshot) {
    final ReentrantLock lock = this.lock;
    lock.lock();//上锁
    try {
        Object[] current = getArray();
        int len = current.length;
        //判断数组是否发生变化，如果快照跟当前数组有变化，则判断当前数组是否已经存在所添加元素
        if (snapshot != current) {
            // Optimize for lost race to another addXXX operation
            int common = Math.min(snapshot.length, len);
            for (int i = 0; i < common; i++)
                if (current[i] != snapshot[i] && eq(e, current[i]))
                    return false;
            if (indexOf(e, current, common, len) >= 0)
                    return false;
        }
        Object[] newElements = Arrays.copyOf(current, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

至于remove方法，跟CopyOnWriteArrayList中的remove方法一样，可以参看之前的文章。由以上可以看出CopyOnWriteArrayList对于经常写的操作效率并不高。