Java8 HashSet 源码阅读

分手后的思念是犯贱 2023-07-03 06:22 14阅读 0赞

### 1. 概述 ###

HashSet 保证元素不重复的集合，查询元素、新增元素、删除元素的时间复杂度均为 O(1)。

HashSet 底层的数据结构为 HashMap，map 中存储的键值对，key 为 Set 集合中的元素，value 使用同一个静态常量（即下面代码中的PRESENT）；

private transient HashMap<E,Object> map;
    
    private static final Object PRESENT = new Object();

HashSet 新增元素使用 HashMap 的 put 方法不断的去替换以前的元素（保证元素不重复），HashMap 的 put 时间复杂度为 O(1)，所以 HashSet 新增元素的时间复杂度也为 O(1)； HashSet 查询是否存在元素使用 HashMap 的 containsKey 方法，所以时间复杂度为 O(1)；HashSet 删除元素 使用 HashMap 的 remove 方法， 时间复杂度也为 O(1);

### 2. 构造函数 ###

无参构造函数，初始化一个空的 hashMap；

public HashSet() {
        
            map = new HashMap<>();
        }

使用集合构造一个set，容器大小为集合大小的4/3倍和16的最大值：

public HashSet(Collection<? extends E> c) {
        
            map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
            addAll(c);
        }

使用初始容量和加载因子：

public HashSet(int initialCapacity, float loadFactor) {
        
            map = new HashMap<>(initialCapacity, loadFactor);
        }

初始容量作为唯一的构造函数：

public HashSet(int initialCapacity) {
        
            map = new HashMap<>(initialCapacity);
        }

default 级别的构造函数，供 LinkedHashSet 使用；

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        
            map = new LinkedHashMap<>(initialCapacity, loadFactor);
        }

### 3. 方法 ###

集合元素的迭代器，返回的数据是无序的：

public Iterator<E> iterator() {
        
            return map.keySet().iterator();
        }

是否包含某元素，调用 HashMap 的 containsKey 方法；

public boolean contains(Object o) {
        
            return map.containsKey(o);
        }

新增元素，使用HashMap的put方法：

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

移除元素，使用HashMap的remove方法：

public boolean remove(Object o) {
        
            return map.remove(o)==PRESENT;
        }

浅拷贝：

@SuppressWarnings("unchecked")
        public Object clone() {
        
            try {
        
                HashSet<E> newSet = (HashSet<E>) super.clone();
                newSet.map = (HashMap<E, Object>) map.clone();
                return newSet;
            } catch (CloneNotSupportedException e) {
        
                throw new InternalError(e);
            }
        }