HashSet分析

HashSet 是一个不允许存储重复元素的集合，它的实现比较简单，只要理解了 HashMap，HashSet 基本就没什么问题。

成员变量

private transient HashMap<E,Object> map;

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

主要就两个变量:

map ：用于存放最终数据的。
PRESENT ：是所有写入 map 的 value 值。

构造函数

构造函数也很简单，利用 HashMap 初始化了 map

/**
 * 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<>();
}

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

重要方法

1
2
3

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

比较关键的就是这个 add() 方法。可以看出它是将存放的对象当做了 HashMap 的健，value 都是相同的 PRESENT 。由于 HashMap 的 key 是不能重复的，所以每当有重复的值写入到 HashSet 时，value 会被覆盖，但 key 不会受到影响，这样就保证了 HashSet 中只能存放不重复的元素。

TreeSet 与 HashSet 的区别

1、TreeSet 是二差树实现的，Treesetc中的数据是自动排好序的，不允许放入 null 值 2、HashSet 是哈希表实现的，HashSet 中的数据是无序的，可以放入 null，但只能放入一个 null，两者中的值都不能重复，就如数据库中唯一约束。

在 HashSet 中，基本的操作都是由 HashMap 底层实现的，因为 HashSet 底层是用 HashMap 存储数据的。当向HashSet 中添加元素的时候，首先计算元素的hashcode值，然后通过扰动计算和按位与的方式计算出这个元素的存储位置，如果这个位置位空，就将元素添加进去；如果不为空，则用equals方法比较元素是否相等，相等就不添加，否则找一个空位添加。

TreeSet 的底层是 TreeMap 的 keySet()，而 TreeMap 是基于红黑树实现的，红黑树是一种平衡二叉查找树，它能保证任何一个节点的左右子树的高度差不会超过较矮的那棵的一倍。

TreeMap 是按key排序的，元素在插入 TreeSet 时 compareTo() 方法要被调用，所以 TreeSet 中的元素要实现Comparable 接口。TreeSet 作为一种Set，它不允许出现重复元素。TreeSet 是用 compareTo() 来判断重复元素的。

总结

HashSet 的原理比较简单，几乎全部借助于 HashMap 来实现的。即 HashSet 和 HashMap 是命运共同体，一荣俱荣，一损俱损。