HashSet

（底層是HashMap）

Set不允許元素重復。

基于HashMap實現，無容量限制。

是非線程安全的。

成員變量

private transient HashMap<E,Object> map;

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

?

構造方法

/*** 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<>();
}
public HashSet(int initialCapacity) {map = new HashMap<>(initialCapacity);
}
public HashSet(int initialCapacity, float loadFactor) {map = new HashMap<>(initialCapacity, loadFactor);
}

添加

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

刪除

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

?

遍歷

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

?

包含

public boolean contains(Object o) {return map.containsKey(o);
}

?

TreeSet

（底層是TreeMap）

基于TreeMap實現，支持排序（自然排序?或者?根據創建TreeSet 時提供的 Comparator 進行排序）。

是非線程安全的。

?

成員變量

/**
?* The backing map.
?*/
private transient NavigableMap<E,Object> m;

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

?

構造方法

public TreeSet() {this(new TreeMap<E,Object>());
}public TreeSet(Comparator<? super E> comparator) {this(new TreeMap<>(comparator));
}

?

添加

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

刪除

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

遍歷

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

包含

public boolean contains(Object o) {return m.containsKey(o);
}

獲取開頭

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 TreeSet<>(m.subMap(fromElement, fromInclusive,toElement,?? toInclusive));
}

默認是含頭不含尾

public SortedSet<E> subSet(E fromElement, E toElement) {return subSet(fromElement, true, toElement, false);
}

LinkedHashSet

（繼承自HashSet，底層是LinkedHashMap）

LinkedHashSet繼承自HashSet，源碼更少、更簡單，唯一的區別是LinkedHashSet內部使用的是LinkHashMap。這樣做的意義或者好處就是LinkedHashSet中的元素順序是可以保證的，也就是說遍歷序和插入序是一致的。

類聲明

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

構造方法

public LinkedHashSet(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor, true);
}/*** Constructs a new, empty linked hash set with the specified initial* capacity and the default load factor (0.75).** @param?? initialCapacity?? the initial capacity of the LinkedHashSet* @throws? IllegalArgumentException if the initial capacity is less*????????????? than zero*/
public LinkedHashSet(int initialCapacity) {super(initialCapacity, .75f, true);
}/*** Constructs a new, empty linked hash set with the default initial* capacity (16) and load factor (0.75).*/
public LinkedHashSet() {super(16, .75f, true);
}

?

super指的是HashSet的default訪問級別的構造方法

/*** Constructs a new, empty linked hash set.? (This package private* constructor is only used by LinkedHashSet.) The backing* HashMap instance is a LinkedHashMap with the specified initial* capacity and the specified load factor.** @param????? initialCapacity?? the initial capacity of the hash map* @param????? loadFactor??????? the load factor of the hash map* @param????? dummy???????????? ignored (distinguishes this*???????????? constructor from other int, float constructor.)* @throws???? IllegalArgumentException if the initial capacity is less*???????????? than zero, or if the load factor is nonpositive*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

BitSet

（位集，底層是long數組，用于替代List<Boolean>）

BitSet是位操作的對象，值只有0或1即false和true，內部維護了一個long數組，初始只有一個long，所以BitSet最小的size是64（8個字節64個位，可以存儲64個數字），當隨著存儲的元素越來越多，BitSet內部會動態擴充，最終內部是由N個long來存儲，這些針對操作都是透明的。

默認情況下，BitSet的所有位都是false即0。

不是線程安全的。

用1位來表示一個數據是否出現過，0為沒有出現過，1表示出現過。使用的時候既可根據某一個是否為0表示，此數是否出現過。

一個1GB的空間，有8*1024*1024*1024 = 8.58*10^9bit，也就是1GB的空間可以表示85億多個數。

常見的應用是那些需要對海量數據進行一些統計工作的時候，比如日志分析、用戶數統計等等，如統計40億個數據中沒有出現的數據，將40億個不同數據進行排序，海量數據去重等等。

JDK選擇long數組作為BitSet的內部存儲結構是出于性能的考慮，因為BitSet提供and和or這種操作，需要對兩個BitSet中的所有bit位做and或者or，實現的時候需要遍歷所有的數組元素。使用long能夠使得循環的次數降到最低，所以Java選擇使用long數組作為BitSet的內部存儲結構。

去重示例

public static void containChars(String str) {BitSet used = new BitSet();for (int i = 0; i < str.length(); i++)used.set(str.charAt(i)); // set bit for char?StringBuilder sb = new StringBuilder();sb.append("[");int size = used.size();for (int i = 0; i < size; i++) {if (used.get(i)) {sb.append((char) i);}}sb.append("]");System.out.println(sb.toString());
}public static void main(String[] args) {containChars("abcdfab");
}

?[abcdf]

排序示例

public static void sortArray(int[] array) {BitSet bitSet = new BitSet(2 << 13);// 雖然可以自動擴容，但盡量在構造時指定估算大小,默認為64?System.out.println("BitSet size: " + bitSet.size());for (int i = 0; i < array.length; i++) {bitSet.set(array[i]);}//剔除重復數字后的元素個數?int bitLen = bitSet.cardinality();//進行排序，即把bit為true的元素復制到另一個數組?int[] orderedArray = new int[bitLen];int k = 0;for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) {orderedArray[k++] = i;}System.out.println("After ordering: ");for (int i = 0; i < bitLen; i++) {System.out.print(orderedArray[i] + "\t");}
}public static void main(String[] args) {int[] array = new int[]{423, 700, 9999, 2323, 356, 6400, 1, 2, 3, 2, 2, 2, 2};sortArray(array);
}

BitSet size: 16384

After ordering:

1???? 2???? 3???? 356 423 700 2323????? 6400????? 9999

CopyOnWriteArraySet

（底層是CopyOnWriteArrayList）

基于CopyOnWriteArrayList實現，其唯一的不同是在add時調用的是CopyOnWriteArrayList的addIfAbsent方法。

在每次add的時候都要進行數組的遍歷，因此其性能會略低于CopyOnWriteArrayList。