HashSet源码分析

梦里梦外; 2023-01-17 15:57 249阅读 0赞

**阅读本文章之前推荐先阅读博主关于HashMap的文章：  
[HashMap源码分析 + 面试题][HashMap_ _]**

# HashSet源码分析 #

### 文章目录 ###

*  HashSet源码分析
 *   *  一、基本介绍
     *  二、源码分析
     *   *  1. 成员变量
         *  2. 构造方法
         *  3. 添加方法
         *  4. 删除方法
         *  5. 查询方法
         *  6. 遍历方法
     *  三、总结

## 一、基本介绍 ##

*  底层实现基于 HashMap，所以迭代时不能保证按照插入顺序或者其它顺序进行迭代
 *  add、remove、contanins、size 等方法的耗时性能，是不会随着数据量的增加而增加的，这个主要跟 HashMap 底层的数据结构有关，不管数据量多大，不考虑 hash 冲突的情况下，时间复杂度都是 O (1)
 *  线程不安全的，允许null值
 *  迭代过程中，如果数据结构被改变，会快速失败，抛出 `ConcurrentModificationException` 异常
 *  继承体系
    
    ![image-20210428092020110][]
    
    HashSet并没有继承HashMap，所以HashSet是通过调用HashMap的方法从而使用HashMap，这种不采用继承而采用组合的方式的优点如下：
    
     *  继承表示父子类是同一个事物，而 Set 和 Map 本来就是两种事物，所以继承不妥，而且 Java 语法限制子类只能继承一个父类，后续难以扩展
     *  组合更加灵活，可以任意的组合现有的基础类，并且可以在基础类方法的基础上进行扩展、编排等，而且方法命名可以任意命名，无需和基础类的方法名称保持一致

## 二、源码分析 ##

### 1. 成员变量 ###

//把HashMap组合进来，key是Hashset的key，value是下面的PRESENT
    private transient HashMap<E,Object> map;
    
    //HashMap中的虚拟value
    private static final Object PRESENT = new Object();

观察上述源码，可以得出如下结论：

*  使用 HashSet 时，比如 add 方法，只有一个入参，但组合的 Map 的 add 方法却有 key、value 两个入参，Map 的 key 就是 add 的入参，value 就是上述代码中的第二个属性 PRESENT，此处设计非常巧妙，用一个默认值 PRESENT 来代替 Map 的 Value
    
     *  也就是说这个map中所有的value都是一样的
 *  当多个线程访问HashSet时，就会有线程安全问题，因为在后续的所有操作中，并没有加锁

### 2. 构造方法 ###

//底层调用HashMap的构造器
    public HashSet() { 
        map = new HashMap<>();
    }
    
    public HashSet(int initialCapacity) { 
        map = new HashMap<>(initialCapacity);
    }
    
    public HashSet(int initialCapacity, float loadFactor) { 
        map = new HashMap<>(initialCapacity, loadFactor);
    }
    
    /** * 如果给定参数集合的初始容量小于16 ，就按照HashMap默认的16初始化即可 * 如果大于16，就按照指定的值进行初始化 * 指定的值 = 参数集合容量 / 0.75 + 1，可以使得期望的值正好比扩容的阀值还大1，就不会扩容，符合HashMap扩容的公式，可以减少扩容次数，提高效率 */
    public HashSet(Collection<? extends E> c) { 
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }
    //以后的开发过程中，如果要给HashMap中拷贝集合，HashMap的初始化大小可以借鉴这种写法
    
    //非public，只能被同一个包调用，这是LinkedHashSet专属的构造器
    HashSet(int initialCapacity, float loadFactor, boolean dummy) { 
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
        //创建的是LinkedHashMap，非HashMap
    }

### 3. 添加方法 ###

`add(E e)` 方法源码如下：

public boolean add(E e) { 
        //直接调用HashMap的put()方法，把元素本身作为key，把PRESENT作为value
        return map.put(e, PRESENT)==null;
    }

### 4. 删除方法 ###

`remove(Object o)` 方法源码如下：

public boolean remove(Object o) { 
        //直接调用HashMap的remove()方法
        return map.remove(o)==PRESENT;
    }

注意，Map的 `remove` 方法返回的是删除元素的value，而Set的 `remove` 方法返回的是boolean类型，如果是null的话说明没有该元素，如果不是null肯定等于PRESENT

### 5. 查询方法 ###

`contains(Object o)` 方法源码如下：

public boolean contains(Object o) { 
        //调用map的containsKey()方法
        return map.containsKey(o);
    }

### 6. 遍历方法 ###

`iterator()` 方法源码如下：

public Iterator<E> iterator() { 
        //调用map的keySet的迭代器
        return map.keySet().iterator();
    }

## 三、总结 ##

（1）HashSet内部使用HashMap的key存储元素，以此来保证元素不重复

（2）HashSet是无序的，因为HashMap的key是无序的

（3）HashSet中允许取值为null的元素，因为HashMap允许key为null

（4）HashSet是非线程安全的

（5）HashSet没有 `get()` 方法，查询方法是 `contains()` 方法

[HashMap_ _]: https://blog.csdn.net/weixin_49343190/article/details/116081608
[image-20210428092020110]: /images/20221021/d2b80f0e5c4141e09a70cf52579306ae.png