【Java集合】探究HashSet的底层实现 加入相同元素是否会覆盖？javaStevenL的博客-

HashSet是一个常见的集合类，底层使用HashMap实现。那么HashSet如何保证元素不重复呢？如果多次放入equals()为true的相同元素会覆盖吗？今天来探究一下源码
首先，来看看HashSet的无参构造函数

 /**      * Constructs a new, empty set; the backing {@code HashMap} instance has      * default initial capacity (16) and load factor (0.75).      */ public HashSet() {         map = new HashMap<>(); } 

很简单，new一个HashMap。
当然了，HashSet也提供了其他构造函数，指定初始容量和装载因子等，也是调用了HashMap的相应构造方法。

/**      * Constructs a new, empty set; the backing {@code HashMap} 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 {@code HashMap} 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); } 

再来看看HashSet如何添加元素？

 /**      * Adds the specified element to this set if it is not already present.      * More formally, adds the specified element {@code e} to this set if      * this set contains no element {@code e2} such that      * {@code Objects.equals(e, e2)}.      * If this set already contains the element, the call leaves the set      * unchanged and returns {@code false}.      *      * @param e element to be added to this set      * @return {@code true} if this set did not already contain the specified      * element      */ public boolean add(E e) { return map.put(e, PRESENT)==null; } 

向map中添加元素，元素作为key，PRESENT作为value，返回是否添加成功。map中key唯一，因此set中的元素也唯一了。这里不免有疑问，PRESENT是什么呢？来看看PRESENT的定义。

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

原来PRESENT是一个常量，一个空的Object类型实例对象，只是为了占住value的位置，并无实际作用。
接下来看看HashMap的put方法。

 /**      * Associates the specified value with the specified key in this map.      * If the map previously contained a mapping for the key, the old      * value is replaced.      *      * @param key key with which the specified value is to be associated      * @param value value to be associated with the specified key      * @return the previous value associated with {@code key}, or      *         {@code null} if there was no mapping for {@code key}.      *         (A {@code null} return can also indicate that the map      *         previously associated {@code null} with {@code key}.)      */ public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } 

只是简单调用了putVal()方法，继续看putVal()的实现。

 /**      * Implements Map.put and related methods.      *      * @param hash hash for key      * @param key the key      * @param value the value to put      * @param onlyIfAbsent if true, don't change existing value      * @param evict if false, the table is in creation mode.      * @return previous value, or null if none      */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {         Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0)             n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null)             tab[i] = newNode(hash, key, value, null); else {             Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))                 e = p; else if (p instanceof TreeNode)                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) {                         p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break;                     p = e; } } if (e != null) { // existing mapping for key                 V oldValue = e.value; if (!onlyIfAbsent || oldValue == null)                     e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } 

从源码看到，HashMap保证key的不重复性，对于重复的key，HashMap会根据参数onlyIfAbsent的设置和原value是否为空两个条件来判断是否替换新value，但要注意的是，我们前面已经看到，对于HashSet，这个value只是个空的Object类的对象，没有任何实际作用，HashSet中的元素实际上是存储在key上的。针对重复的key，HashMap只有对于value的处理，并不会替换key，因此在HashSet中加入相同元素不会覆盖。

为了更清晰认识这点，我又做了个简单实验，来看看代码。

import java.util.HashSet; import java.util.Iterator; import java.util.Set; public class HashSetTest{ public static void main(String[] args) {         User user1 = new User(1,"abc",20);         User user2= new User(1,"def",20);         Set<User> set = new HashSet<>();         set.add(user1);         set.add(user2);         Iterator<User> iterator = set.iterator(); while(iterator.hasNext()) System.out.println(iterator.next()); } } class User{ private int id; private String name; private int age; @Override public int hashCode() { return 17*id + 17*age; } @Override public String toString() { return "User{" + "id=" + id + ", name='" + name + ''' + ", age=" + age + '}'; } public User(int id, String name, int age) { this.id = id; this.name = name; this.age = age; } @Override public boolean equals(Object obj) {         User userObj = (User) obj; return this.id==userObj.id && this.age==userObj.age; } } 

这里，User类有三个成员变量：id、name、age，重写的hashcode()和equals()都只依赖于两个成员变量：id、age，因此在HashSet中，会判断user1、user2是相同对象，我们就能通过name的不同判断是否进行了覆盖。
来看看输出结果：

User{id=1, name='abc', age=20} 

到这里，也验证了之前在源码中看到的，向HashSet中加入相同元素不会进行覆盖。因为HashSet底层使用HashMap实现，元素存在HashMap的key中。在HashMap中，多次put相同的key，只会覆盖value，而不存在key的情况。