HashSet 底层实现详解

【Java】如何保证集合的线程安全？

1. HashSet 整体结构

2. 核心源码解析

// HashSet 的关键源码
public class HashSet<E> extends AbstractSet<E> 
                       implements Set<E>, Cloneable, java.io.Serializable {
    
    // 底层使用 HashMap 存储
    private transient HashMap<E, Object> map;
    
    // 虚拟值，所有键都映射到这个对象
    private static final Object PRESENT = new Object();
    
    // 构造方法 - 创建底层 HashMap
    public HashSet() {
        map = new HashMap<>();
    }
    
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }
    
    // 添加元素 - 实际上是把元素作为 key 放入 HashMap
    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }
    
    // 删除元素
    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }
    
    // 检查包含
    public boolean contains(Object o) {
        return map.containsKey(o);
    }
    
    // 大小
    public int size() {
        return map.size();
    }
}

3. 添加元素的过程

4. 内存结构示意图

5. 完整示例代码

import java.util.HashSet;
import java.util.HashMap;

public class HashSetInternal {
    public static void main(String[] args) {
        // 创建 HashSet
        HashSet<String> set = new HashSet<>();
        
        // 添加元素 - 底层调用 HashMap.put(element, PRESENT)
        set.add("Apple");
        set.add("Banana");
        set.add("Apple"); // 重复元素，不会添加
        
        // 删除元素 - 底层调用 HashMap.remove(element)
        set.remove("Banana");
        
        // 检查包含 - 底层调用 HashMap.containsKey(element)
        boolean hasApple = set.contains("Apple");
        
        System.out.println("Set size: " + set.size()); // 1
        System.out.println("Contains Apple: " + hasApple); // true
        
        // 模拟 HashSet 的底层实现
        demonstrateInternalWorkings();
    }
    
    public static void demonstrateInternalWorkings() {
        System.out.println("\n=== HashSet 底层实现模拟 ===");
        
        // 这就是 HashSet 底层的 HashMap
        HashMap<String, Object> internalMap = new HashMap<>();
        final Object PRESENT = new Object(); // 模拟 PRESENT
        
        // 模拟 add 操作
        System.out.println("添加 Apple: " + (internalMap.put("Apple", PRESENT) == null));
        System.out.println("添加 Banana: " + (internalMap.put("Banana", PRESENT) == null));
        System.out.println("再次添加 Apple: " + (internalMap.put("Apple", PRESENT) == null));
        
        // 模拟 contains 操作
        System.out.println("包含 Apple: " + internalMap.containsKey("Apple"));
        
        // 模拟 remove 操作
        System.out.println("删除 Banana: " + (internalMap.remove("Banana") == PRESENT));
        
        System.out.println("最终Map大小: " + internalMap.size());
        System.out.println("Map内容: " + internalMap.keySet());
    }
}

6. HashSet 特性总结

7. HashSet 与其他 Set 实现对比

// 不同 Set 实现的底层结构
HashSet<String> hashSet = new HashSet<>();        // 底层: HashMap
LinkedHashSet<String> linkedSet = new LinkedHashSet<>(); // 底层: LinkedHashMap  
TreeSet<String> treeSet = new TreeSet<>();        // 底层: TreeMap (红黑树)

// 性能特点:
// - HashSet: 最快，但不保证顺序
// - LinkedHashSet: 保持插入顺序，稍慢
// - TreeSet: 自动排序，最慢

关键理解点：

1. HashSet 只是 HashMap 的包装：所有操作都委托给 HashMap
2. 值存储机制：所有元素作为 HashMap 的 key，value 都是同一个 PRESENT 对象
3. 内存效率：PRESENT 是静态常量，所有 HashSet 实例共享，节省内存
4. 性能特征：继承 HashMap 的所有特性，包括 O(1) 时间复杂度的基本操作