HashSet 保证元素唯一性的原理

源代码分析

实际上 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).
     */
    public HashSet() {
        map = new HashMap<>();
    } 
    
    ...
} 

具体要看 HashSet 的 add () 方法是如何进行判重的，代码如下：

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

可以看到，元素直接存在 map 里面了。

元素值是 map 的 key，map 的 value 则是前面提到的 PRESENT 变量，这个变量只作为放入 map 时的一个占位符而存在，所以没什么实际用处。

HashSet 元素以 HashMap 的键值形式存放，因为 Map 当中键值是不可重复的，所以 HashSet 中的元素也是唯一的。

HashMap 又是怎么保证 Key 是唯一的呢？我们看一下它的 put () 方法：

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable (threshold);
    }
    if (key == null)
        return putForNullKey (value);
    int hash = hash (key);
    int i = indexFor (hash, table.length);
    for (Entry<K,V> e = table [i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals (k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess (this);
            return oldValue;
        }
    }
 
    modCount++;
    addEntry (hash, key, value, i);
    return null;
}

代码的主要操作是：先调用对象的 hashCode () 方法得到一个哈希值，然后在集合中查找是否有哈希值相同的对象

• 如果没有哈希值相同的对象，就直接存入集合
• 如果有哈希值相同的对象，就和哈希值相同的对象逐个进行 equals () 比较，比较结果为 false 就存入对象，为 true 则不存 key，仅更新 value

总结

1. HashSet 原理

• 我们使用 Set 集合都是需要去掉重复元素的，如果在存储的时候逐个使用 equals () 方法进行比较，效率很低。HashSet 底层是一个哈希表，不同的元素哈希值一般是不相同的，元素按照不同的哈希值进行存储，这样可以减少元素比较的次数，降低了使用 equals () 方法的次数。
• 当 HashSet 调用 add () 方法存储对象的时候，先调用对象的 hashCode () 方法得到一个哈希值，然后在集合中查找是否有哈希值相同的对象。
• 如果没有哈希值相同的对象就直接存入集合。
• 如果有哈希值相同的对象，就和哈希值相同的对象逐个进行 equals () 比较，比较结果为 false 就存入，true 则不存。

2. 将自定义类的对象存入 HashSet 去重复

类中必须重写 hashCode () 和 equals () 方法

• hashCode (): 属性相同的对象返回值必须相同，属性不同的返回值尽量不同（提高效率）。
• equals (): 属性相同返回 true, 属性不同返回 false, 返回 false 的时候存储（注意存储自定义对象去重时必须同时重写 hashCode () 和 equals () 方法，因为 equals 方法默认是按照对象地址值比较的）。

代码示例

public static void main(String [] args) {
    Person p1 = new Person ("Bob", 20);
    Person p2 = new Person ("Bob", 20);
    Person p3 = new Person ("Alice", 21);
    Person p4 = new Person ("Mike", 22);
 
    Set<Person> set = new HashSet<>();
    set.add (p1);
    set.add (p2);
    set.add (p3);
    set.add (p4);
 
    System.out.println (set.size ());
    System.out.println (set);
}

代码中 p1 和 p2 内容完全相同，但实际上它们是不同的对象，它们的默认的哈希值是不同的，所以 HashSet 会直接将 p1 和 p2 存进集合。这不满足我们集合去重的目的，所以需要重写 Person 类的 hashCode () 方法，使得 p1 和 p2 的哈希值相同，进而能够调用 equals () 方法进行进一步的比较。

在使用默认的 equals () 方法进行判断时，是按照对象的地址值比较的，如下所示：

public boolean equals(Object obj) {
    return (this == obj);
}

显然 p1 和 p2 的地址不同，判断结果是 false，这两个元素仍然可以一起存入集合，还是没有达到集合去重的目的。因此 equals () 方法也需要进行重写。

可以使用 IDE 自动重写 hashCode () 和 equals () 方法：

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass () != o.getClass ()) return false;
    Person person = (Person) o;
    return age == person.age &&
            Objects.equals (name, person.name);
}
 
@Override
public int hashCode() {
    return Objects.hash (name, age);
}

• 重写之后的 hashCode () 方法，对象内容完全一致的形况下，得到的哈希值也是一致的。
• 重写之后的 equals () 方法，对象内容完全一致的形况下，返回的结果是 true。

所以，HashSet 添加 p1 和 p2 时，因为其内容完全一致，所以哈希值也相同，进而调用 equals () 方法，得到返回结果 true，所以两个内容相同的元素只能存入一个，达到了集合去重的目的。