深入理解HashSet

题外话

今天下午去面试了一家公司，被问了一个问题，HashSet是因为什么保证元素可以不重复。感觉答的磕磕绊绊的，还是回家想了下这个问题。

源码分析

属性

private transient HashMap<E,Object> map;

构造器

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

public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

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

add方法

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

回顾HashMap的put方法的策略：

public V put(K key, V value) {  
    // 如果键为null
    if (key == null)  
        //设置键key为null的值 
        return putForNullKey(value);  
    //通过键获取hash值  
    int hash = hash(key);  
    //通过hash值获取下标索引  
    int i = indexFor(hash, table.length);  
    // 遍历单链表节点，找到对应的值就覆盖
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
        Object k;  
        // 如果hash值和键都相同的
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
            // 获取旧的键对应的值
            V oldValue = e.value; 
            // 设置指定的值
            e.value = value;  
            e.recordAccess(this);  
            // 返回旧值
            return oldValue;  
        }  
    }  
    // 修改次数加1
    modCount++;  
    //否则就添加新值并且返回为空  
    addEntry(hash, key, value, i);  
    return null;  
}

说明：可以发现HashSet每次放入的值都会被当作key键来处理，然后HashMap中的put方法采用遍历单向链表，对于使用相同的key和相同的key生成的hash值，那么就使用指定的值替换旧值。
iterator方法：遍历Key的iterator

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

说明：可以发现它遍历的是keySet，是键的集合，HashMap中key键重复就更新值，可以保证Key是不重复的，那么HashSet中添加的值就是不重复的。

总结

HashSet为什么存储的值不是重复的，因为其使用的HashMap中的Key是不存在重复的。（对于重复键Key采用更新策略）。