Java 中的 HashSet 底层实现

Java 中的 HashSet 底层实现

• 1、HashSet 的底层实现
• 2、 HashSet 的特点
• 3、 总结

HashSet 是 Java 集合框架中的一个重要成员，它提供了不存储重复元素的集合。但是，你有没有好奇过 HashSet 是如何实现这一特性的呢？本文将带你深入了解 HashSet 的底层实现机制。

1、HashSet 的底层实现

HashSet 的实现是基于 HashMap 的。当我们创建一个 HashSet 对象时，实际上是在背后初始化了一个 HashMap 对象。

但是，HashSet 和 HashMap 的使用方式并不完全相同，这是因为 HashSet 隐藏了 HashMap 的某些复杂性，只暴露了简单的集合操作接口。

HashSet 不允许值重复，这是如何实现的呢？ 关键在于 HashSet 是如何存储其元素的。在 HashSet 中，元素是作为 HashMap 的 key 存储的，而 HashMap 的 value 则是一个固定的对象（在 Java 8 及以后的版本中，这个固定的对象通常是一个名为 PRESENT 的静态常量对象）。

示例：

package com.mypackage;  import java.util.HashMap; import java.util.Map;  public class MyHashSet<E> {     // 使用 HashMap 存储元素，这里将 key 视为 HashSet 中的元素     private Map<E, Object> map;      // 静态常量，模拟 HashSet 中的 PRESENT     private static final Object PRESENT = new Object();      // 构造函数，初始化 HashMap     public MyHashSet() {         map = new HashMap<>();     }      // 添加元素到 HashSet 中     public boolean add(E e) {         // 如果 put 方法返回 null，表示该 key 尚未在 HashMap 中存在         return map.put(e, PRESENT) == null;     }      // 从 HashSet 中移除元素     public boolean remove(E e) {         // 如果 remove 方法返回 true，表示该 key 在 HashMap 中存在并且已被移除         return map.remove(e) != null;     }      // 检查 HashSet 是否包含某个元素     public boolean contains(E e) {         // 如果 get 方法返回非 null 值，表示该 key 在 HashMap 中存在         return map.containsKey(e);     }      // 为了展示 HashSet 的内容，我们提供一个简单的方法来打印它     public void printSet() {         for (E e : map.keySet()) {             System.out.println(e);         }     }      // 主函数，用于测试 MyHashSet     public static void main(String[] args) {         MyHashSet<String> myHashSet = new MyHashSet<>();         myHashSet.add("apple");         myHashSet.add("banana");         myHashSet.add("apple"); // 这将不会添加，因为 "apple" 已经存在         System.out.println(myHashSet.contains("apple")); // 输出：true         System.out.println(myHashSet.contains("orange")); // 输出：false         myHashSet.remove("banana");         myHashSet.printSet(); // 输出：apple     } }  

2、 HashSet 的特点

• 无序性：HashSet 不保证元素的迭代顺序与插入顺序相同。这是因为 HashSet 是基于 HashMap 实现的，而 HashMap 本身不保证映射的顺序。
• 元素唯一性：HashSet 中的元素是唯一的，不允许重复。这是通过 HashMap 的 key 唯一性保证的。
• 性能：HashSet 的查找、添加和删除操作的时间复杂度通常为 O(1)，但在最坏的情况下可能会达到 O(n)（当哈希冲突严重，导致链表或红黑树过长时）。

3、 总结

HashSet 的底层实现是基于 HashMap 的，通过利用 HashMap 的 key 唯一性来保证集合中元素的唯一性。HashSet 隐藏了 HashMap 的复杂性，只提供了简单的集合操作接口，使得我们可以更加方便地使用它来处理不重复的元素集合。