HashSet源码分析
底层是HashMap
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable { static final long serialVersionUID = -5024744406713321676L; 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). * 使用HashMap的默认容量大小16和默认加载因子0.75初始化map，构造一个HashSet.
*/ public HashSet() { map = new HashMap<>(); } /** * Constructs a new set containing the elements in the specified collection. The <tt>HashMap</tt> is created with default load factor * (0.75) and an initial capacity sufficient to contain the elements in the specified collection. * * @param c the collection whose elements are to be placed into this set * @throws NullPointerException if the specified collection is null */ public HashSet(Collection<? extends E> c) { map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); addAll(c); } /** * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has 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 * @throws IllegalArgumentException if the initial capacity is less than zero, or if the load factor is nonpositive */ public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<>(initialCapacity, loadFactor); } /** * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has the specified initial capacity and default load factor (0.75). * * @param initialCapacity the initial capacity of the hash table * @throws IllegalArgumentException if the initial capacity is less than zero */ public HashSet(int initialCapacity) { map = new HashMap<>(initialCapacity); } /** * 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); } }
EnumSet源码分析
底层是Enum.
public abstract class EnumSet<E extends Enum<E>> extends AbstractSet<E> implements Cloneable, java.io.Serializable { /** * The class of all the elements of this set. */ final Class<E> elementType; /** * All of the values comprising T. (Cached for performance.) */ 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; } }
TreeSet源码分析
底层是TreeMap，而TreeMap底层数据结构是红黑树。
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable { /** * 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(); /** * Constructs a set backed by the specified navigable map. */ TreeSet(NavigableMap<E,Object> m) { this.m = m; } /** * Constructs a new, empty tree set, sorted according to the natural ordering of its elements. */ public TreeSet() { this(new TreeMap<E,Object>()); } /** * Constructs a new, empty tree set, sorted according to the specified comparator. * @param comparator the comparator that will be used to order this set. * If {@code null}, the {@linkplain Comparable natural ordering} of the elements will be used. */ public TreeSet(Comparator<? super E> comparator) { this(new TreeMap<>(comparator)); } /** * Constructs a new tree set containing the elements in the specified collection, sorted according to the <i>natural ordering</i> of its elements. * @param c collection whose elements will comprise the new set * @throws ClassCastException if the elements in {@code c} are * not {@link Comparable}, or are not mutually comparable * @throws NullPointerException if the specified collection is null */ public TreeSet(Collection<? extends E> c) { this(); addAll(c); } /** * Constructs a new tree set containing the same elements and using the same ordering as the specified sorted set. * @param s sorted set whose elements will comprise the new set * @throws NullPointerException if the specified sorted set is null */ public TreeSet(SortedSet<E> s) { this(s.comparator()); addAll(s); } }
LinkedHashSet源码分析
底层是LinkedHashMap
public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable { private static final long serialVersionUID = -2851667679971038690L; /** * Constructs a new, empty linked hash set with the specified initial capacity and load factor. * 构造方法继承自HashSet中生成的的LinkedHashMap * @param initialCapacity the initial capacity of the linked hash set * @param loadFactor the load factor of the linked hash set * @throws IllegalArgumentException if the initial capacity is less than zero, or if the load factor is nonpositive */ 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); } /** * Constructs a new linked hash set with the same elements as the specified collection. The linked hash set is created with an initial * capacity sufficient to hold the elements in the specified collection and the default load factor (0.75). * * @param c the collection whose elements are to be placed into this set * @throws NullPointerException if the specified collection is null */ public LinkedHashSet(Collection<? extends E> c) { super(Math.max(2*c.size(), 11), .75f, true); addAll(c); } @Override public Spliterator<E> spliterator() { return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED); } }
总结
1、Set 的内部实现其实是一个 Map，即HashSet的内部实现是一个HashMap，TreeSet的内部实现是一个TreeMap，LinkedHashSet的内部实现是一个LinkedHashMap。
2、允许Null值，且只有一个。
3、但是 Set 中只有一个元素，又是怎么变成(key,value)的呢？ 以 HashSet 的 add 方法为例：
public boolean add(E e) { return map.put(e, PRESENT)==null; }
原来是，把添加到 Set 中的元素作为内部实现 map 的 key，然后用一个常量对象 PRESENT 对象，作为value。所有的 HashSet 共用同一个PRESENT对象，所有的 TreeSet 共用同一个 PRESENT对象，所有的 LinkedHashSet 共用同一个 PRESENT 对象。这是因为 Set 的元素不可重复和 Map 的 key 不可重复有相同特点。Map 有一个方法 keySet() 可以返回所有 key。