Java中Set集合是如何实现添加元素保证不重复的？

Java中Set集合是如何实现添加元素保证不重复的？

Set集合是一个无序的不可以重复的集合。今天来看一下为什么不可以重复。

Set是一个接口，最常用的实现类就是HashSet，今天我们就拿HashSet为例。

先简单介绍一下HashSet类

HashSet类实现了Set接口， 其底层其实是包装了一个HashMap去实现的。HashSet采用HashCode算法来存取集合中的元素，因此具有比较好的读取和查找性能。

先看下HashSet的几个构造方法。

// 默认构造函数 底层创建一个HashMap
    public HashSet() {
        // 调用HashMap的默认构造函数，创建map
        map = new HashMap<E,Object>();
    }

    // 带集合的构造函数
    public HashSet(Collection<? extends E> c) {
        // 创建map。
        map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
        // 将集合(c)中的全部元素添加到HashSet中
        addAll(c);
    }

    // 指定HashSet初始容量和加载因子的构造函数
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<E,Object>(initialCapacity, loadFactor);
    }

    // 指定HashSet初始容量的构造函数
    public HashSet(int initialCapacity) {
        map = new HashMap<E,Object>(initialCapacity);
    }

    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
    }

再来看HashSet中的声明。

private transient HashMap<E,Object> map;
 // 用来匹配Map中后面的对象的一个虚拟值
private static final Object PRESENT = new Object();

接下来就是我们的重点HashSet的add()方法，贴上源码。

    /**
     * 将元素e添加到HashSet中，也就是将元素e作为Key放入HashMap中
     *
     * @param e 要添加到HashSet中的元素
     * @return true 如果不包含该元素
     */
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

从源码我们可以看出HashSet的add()方法又调用了HashMap中的put()方法，那我们再跳转到HashMap中的put()方法中。

    public V put(K key, V value) {
        // 倒数第二个参数false：表示允许旧值替换
        // 最后一个参数true：表示HashMap不处于创建模式
        return putVal(hash(key), key, value, false, true);
    }

HashMap中的put()方法又调用了putVal()方法来实现功能，再看putVal()的源码。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K, V>[] tab;
        Node<K, V> p;
        int n, i;