HashSet详解

大家好，欢迎来到IT知识分享网。

HashSet

HashSet是基于HashMap来实现的，支持快速查找，但不支持有序性操作。实现了Set接口，同时还实现了序列化和可克隆化。Set不允许存储重复的元素，即集合中的元素是唯一的。当试图添加一个已经存在的元素时，add方法会返回false，并且集合不会发生改变。

public class HashSetExample { 
    public static void main(String[] args) { 
    // 创建一个 HashSet 实例 HashSet<String> set = new HashSet<>(); // 添加元素 set.add("Apple"); set.add("Banana"); set.add("Orange"); // 打印 HashSet System.out.println("HashSet: " + set); // 尝试添加重复元素 boolean added = set.add("Apple"); System.out.println("Added duplicate element: " + added); // 输出: false // 删除元素 set.remove("Banana"); System.out.println("After removing 'Banana': " + set); } } 

去重原理

HashSet内部实际上是由一个HashMap实例支持的，其中HashMap的键值对中的键存储了HashSet中的元素，而值则是一个占位对象，用来表示键已经存在。

当调用HashSet的add(E e)方法添加元素时，首先会调用元素e的 hashCode方法获取其哈希码。HashSet根据哈希码确定元素在内部HashMap的存储位置。如果该位置上已经存在一个元素，则使用 equals 方法比较新元素e与已存在的元素是否相等。如果equals方法返回true，则认为新元素与已存在元素相同，不进行添加操作，返回false。如果equals方法返回false，则说明哈希码冲突，但实际上是不同的对象，此时将新元素添加到 HashSet中，返回true。如果该位置上不存在任何元素，则直接将新元素添加到HashSet中，并返回true。

简单来说，HashSet利用对象的哈希码和equals方法来确保集合中不存储重复的元素。当添加新元素时，先计算其哈希码确定存储位置，如果位置上已存在相同哈希码且通过equals方法比较相等的元素，则不添加，否则添加新元素到集合中。

HashSet添加方法的实现源码如下：

// hashmap 中 put() 返回 null 时，表示操作成功 public boolean add(E e) { 
    return map.put(e, PRESENT)==null; } // 返回值：如果插入位置没有元素则返回 null，否则返回上一个元素 public V put(K key, V value) { 
    return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { 
    Node<K, V>[] tab; Node<K, V> p; int n, i; //如果哈希表为空，调用 resize() 创建一个哈希表，并用变量 n 记录哈希表长度 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; / * 如果指定参数 hash 在表中没有对应的桶，即为没有碰撞 * Hash函数，(n - 1) & hash 计算 key 将被放置的槽位 * (n - 1) & hash 本质上是 hash % n 位运算更快 */ if ((p = tab[i = (n - 1) & hash]) == null) // 直接将键值对插入到 map 中即可 tab[i] = newNode(hash, key, value, null); else { 
   // 桶中已经存在元素 Node<K, V> e; K k; // 比较桶中第一个元素(数组中的结点)的 hash 值相等，key 相等 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 将第一个元素赋值给 e，用 e 来记录 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; } // 链表节点的<key, value>与 put 操作<key, value> // 相同时，不做重复操作，跳出循环 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 找到或新建一个 key 和 hashCode 与插入元素相等的键值对，进行 put 操作 if (e != null) { 
    // existing mapping for key // 记录 e 的 value V oldValue = e.value; / * onlyIfAbsent 为 false 或旧值为 null 时，允许替换旧值 * 否则无需替换 */ if (!onlyIfAbsent || oldValue == null) e.value = value; // 访问后回调 afterNodeAccess(e); // 返回旧值 return oldValue; } } // 更新结构化修改信息 ++modCount; // 键值对数目超过阈值时，进行 rehash if (++size > threshold) resize(); // 插入后回调 afterNodeInsertion(evict); return null; } 

从上述源码可以看出，当将一个键值对放入HashMap时，首先根据key的hashCode()返回值决定该Entry的存储位置。如果有两个key的hash值相同，则会判断这两个元素key的equals()是否相同，如果相同就返回true，说明是重复键值对，那么HashSet中add方法的返回值会是false，表示HashSet添加元素失败。因此，如果向HashSet中添加一个已经存在的元素，新添加的集合元素不会覆盖已有元素，从而保证了元素的不重复。如果不是重复元素，put方法最终会返回null，传递到HashSet的add方法就是添加成功。

equals与hashCode

因为HashSet底层用到了equals和hashCode方法，如果对象中的equals和hashCode方法没有正确地重写，可能会导致HashSet在判断元素相等性时出现问题，从而允许添加相同的元素。

equals()地址比较是通过对象的哈希值来比较的。hash值是由hashCode方法产生的，hashCode属于Object类的本地方法，默认使用==比较两个对象，如果equals()相等，hashcode一定相等，如果hashcode相等，equals不一定相等。所以在覆盖equals方法时应当总是覆盖hashCode方法，保证等价的两个对象散列值也相等。

下面的代码中，新建了两个等价的对象，并将它们添加到HashSet中。我们希望将这两个对象当成一样的，只在集合中添加一个对象，但是因为EqualExample没有实现hashCode方法，因此这两个对象的散列值是不同的，最终导致集合添加了两个等价的对象。

public class MainTest { 
    public static void main(String[] args) { 
    EqualExample e1 = new EqualExample(1, 1, 1); EqualExample e2 = new EqualExample(1, 1, 1); // true System.out.println(e1.equals(e2)); HashSet<EqualExample> set = new HashSet<>(); set.add(e1); set.add(e2); // 2 System.out.println(set.size()); } } 

所以在覆盖equals方法时应当总是覆盖hashCode方法，保证等价的两个对象散列值也相等。

线程安全

HashSet和ArrayList类似，也是线程不安全的集合类，也会出现ConcurrentModificationException异常。代码演示线程不安全示例：

public class MainTest { 
    public static void main(String[] args) { 
    HashSet<String> set = new HashSet<>(); for(int i=0; i< 10; i++) { 
    new Thread(() -> { 
    set.add(UUID.randomUUID().toString()); System.out.println(set); },String.valueOf(i)).start(); } } } 

HashSet线程不安全的解决方案通常是使用CopyOnWriteArraySet。这种集合在读操作远多于写操作的场景中非常有用，因为它通过每次修改创建集合的副本来实现线程安全。CopyOnWriteArraySet是Java中一种线程安全的Set实现，内部使用了CopyOnWriteArrayList来存储元素。

private final CopyOnWriteArrayList<E> al; / * Creates an empty set. */ public CopyOnWriteArraySet() { 
    al = new CopyOnWriteArrayList<E>(); } 

因为底层用CopyOnWriteArrayList存储，所以写操作开销大，每次修改都会创建数组副本，适用场景有限。不适用于写操作频繁的场景，否则会导致高昂的内存和时间开销。与CopyOnWriteArrayList不同的是，CopyOnWriteArraySet不允许包含重复元素。如果尝试添加一个已经存在的元素，集合将保持不变，所以该集合在线程不安全的情况下可替代HashSet。

public class CopyOnWriteArraySetExample { 
    public static void main(String[] args) { 
    // 创建一个 CopyOnWriteArraySet Set<String> cowSet = new CopyOnWriteArraySet<>(); // 添加元素 cowSet.add("Apple"); cowSet.add("Banana"); cowSet.add("Apple"); // 不允许重复元素 // 读取元素 System.out.println("Set: " + cowSet); // 迭代元素 for (String fruit : cowSet) { 
    System.out.println(fruit); } // 添加新元素 cowSet.add("Grapes"); System.out.println("After adding Grapes: " + cowSet); // 删除元素 cowSet.remove("Banana"); System.out.println("After removing Banana: " + cowSet); } }