【JDK源码】HashSet&LinkedHashSet源码分析

柔光的暖阳◎ 2023-10-01 11:37 16阅读 0赞

#### 文章目录 ####

*  HashSet源码分析
 *   *  1.简介
     *  2.属性
     *  3.构造方法
     *  4.常用方法
     *   *  4.1 添加元素
         *  4.2 删除元素
         *  4.3 查询元素
         *  4.4 遍历元素
         *  4.5 序列化方法
     *  5.总结
 *  LinkedHashSet源码分析
 *   *  1.简介
     *  2.源码分析
     *  3.总结

## HashSet源码分析 ##

### 1.简介 ###

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-94FAXYPH-1641084441885)(HashSet源码分析.assets/image-20211229154246790.png)\]][img-94FAXYPH-1641084441885_HashSet_.assets_image-20211229154246790.png]

`HashSet`是`Set`的一种实现方式，底层主要使用`HashMap`来确保元素不重复。

HashSet的特点：

*  无序性（存储元素无序）
 *  唯一性（允许使用**null**）
 *  本质上，HashSet底层是通过HashMap来保证唯一性
 *  HashSet没有提供`get()`方法，同HashMap一样，因为Set内部是**无序**的，所以只能通过**迭代**的方式获得

### 2.属性 ###

//内部使用HashMap存储元素
    private transient HashMap<E,Object> map;
    
    //虚拟对象，用来作为value放到map中
    private static final Object PRESENT = new Object();

### 3.构造方法 ###

//内部使用HashMap存储元素
    private transient HashMap<E, Object> map;
    
    //虚拟对象，用来作为value放到map中
    private static final Object PRESENT = new Object();
    
    //无参构造
    public HashSet() {
        
        map = new HashMap<>();
    }
    
    // 把另一个集合的元素全都添加到当前Set中
    // 注意，这里初始化map的时候是计算了它的初始容量的
    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);
    }
    
    // LinkedHashSet专用的方法
    // dummy是没有实际意义的, 只是为了跟上上面那个操持方法签名不同而已
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        
        //调用LinkedHashMap的构造方法
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

从源码可以看出：

1.  构造方法都是调用`HashMap`对应的构造方法。
2.  最后一个构造方法有点特殊，它不是`public`的，意味着它只能被同一个包调用，这是`LinkedHashSet`专属的方法。

### 4.常用方法 ###

#### 4.1 添加元素 ####

//直接调用HashMap的put()方法
    //把元素本身作为key，把PRESENT作为value，也就是这个map中所有的value都是一样的
    public boolean add(E e) {
        
        return map.put(e, PRESENT)==null;
    }

#### 4.2 删除元素 ####

//直接调用HashMap的remove()方法
    public boolean remove(Object o) {
        
        //注意map的remove返回是删除元素的value，而Set的remov返回的是boolean类型
        //这里要检查一下，如果是null的话说明没有该元素，如果不是null肯定等于PRESENT
        return map.remove(o)==PRESENT;
    }

#### 4.3 查询元素 ####

//Set没有get()方法哦，因为get似乎没有意义，不像List那样可以按index获取元素
    public boolean contains(Object o) {
        
    	//这里只要一个检查元素是否存在的方法contains()，直接调用map的containsKey()方法
        return map.containsKey(o);
    }

#### 4.4 遍历元素 ####

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

#### 4.5 序列化方法 ####

**序列化写出方法**

//序列化写出方法
    private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException {
        
        //写出非static非transient方法
        s.defaultWriteObject();
    
        //写出map的容量 
        s.writeInt(map.capacity());
        //写出map的装载因子
        s.writeFloat(map.loadFactor());
    
        //写出元素个数
        s.writeInt(map.size());
    
        //遍历写出所有元素
        for (E e : map.keySet())
            s.writeObject(e);
    }

**序列化读入方法**

//序列化读入方法
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        
        // 读入非static非transient属性
        s.defaultReadObject();
    
        // 读入容量，并检查不能小于0
        int capacity = s.readInt();
        if (capacity < 0) {
        
            throw new InvalidObjectException("Illegal capacity: " +
                                             capacity);
        }
    
        // 读入装载因子，并检查不能小于等于0也不能是NaN(Not a Number)
        float loadFactor = s.readFloat();
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
        
            throw new InvalidObjectException("Illegal load factor: " +
                                             loadFactor);
        }
    
        // 读入元素个数并检查不能小于0
        int size = s.readInt();
        if (size < 0) {
        
            throw new InvalidObjectException("Illegal size: " +
                                             size);
        }
        // 根据元素个数并重新设置容量
        // 这是为了保证map有足够的容量容纳所有元素, 防止无意义的扩容
        capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f),
                                  HashMap.MAXIMUM_CAPACITY);
    
        // 再次检查某些东西, 不重要的代码忽视掉
        SharedSecrets.getJavaOISAccess()
            .checkArray(s, Map.Entry[].class, HashMap.tableSizeFor(capacity));
    
        // 创建map, 检查是不是LinkedHashSet类型
        map = (((HashSet<?>) this) instanceof LinkedHashSet ?
               new LinkedHashMap<E, Object>(capacity, loadFactor) :
               new HashMap<E, Object>(capacity, loadFactor));
    
        // 读入所有元素, 并放入map中
        for (int i = 0; i < size; i++) {
        
            @SuppressWarnings("unchecked")
            E e = (E) s.readObject();
            map.put(e, PRESENT);
        }
    }

### 5.总结 ###

1.  HashSet内部**使用`HashMap`的key存储元素，以此来保证元素不重复**
2.  HashSet是**无序的**，因为HashMap的key是无序的
3.  HashSet中**允许有一个null元素**，因为HashMap允许key为null
4.  HashSet是**非线程安全的**
5.  HashSet是**没有get()方法的**

## LinkedHashSet源码分析 ##

### 1.简介 ###

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DNxEaWlD-1641084441887)(HashSet&LinkedHashSet源码分析.assets/image-20211229165618772.png)\]][img-DNxEaWlD-1641084441887_HashSet_LinkedHashSet_.assets_image-20211229165618772.png]

看出`LinkedHashSet`继承了`HashSet`。实现了`Serializable`和`Cloneable`。

### 2.源码分析 ###

public class LinkedHashSet<E>
            extends HashSet<E>
            implements Set<E>, Cloneable, java.io.Serializable {
        
    
        private static final long serialVersionUID = -2851667679971038690L;
    
        //构造方法，传入容量和转载页因子
        public LinkedHashSet(int initialCapacity, float loadFactor) {
        
            //调用HashSet的构造方法
            super(initialCapacity, loadFactor, true);
        }
    
        //只传入容量，装载因子默认为0.75
        public LinkedHashSet(int initialCapacity) {
        
            super(initialCapacity, .75f, true);
        }
    
        //使用默认容量16，默认转载因子0.75
        public LinkedHashSet() {
        
            super(16, .75f, true);
        }
    
        // 将集合c中的所有元素添加到LinkedHashSet中
        // 好奇怪, 这里计算容量的方式又变了
        // HashSet中使用的是Math.max((int) (c.size()/.75f) + 1, 16)
        // 这一点有点不得其解, 是作者偷懒？
        public LinkedHashSet(Collection<? extends E> c) {
        
            super(Math.max(2 * c.size(), 11), .75f, true);
            addAll(c);
        }
    
        //可分割的迭代器，主要用于多线程并行迭代处理时使用
        @Override
        public Spliterator<E> spliterator() {
        
            return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
        }
    }

### 3.总结 ###

1.  LinkedHashSet**继承自`HashSet`**，它的添加、删除、查询等方法都是直接用的HashSet的，唯一的不同就是它**使用`LinkedHashMap`存储元素。**
2.  LinkedHashSet是**有序的**，它是**按照插入的顺序排序的**
3.  LinkedHashSet**是不支持按访问顺序对元素排序的**，只能按插入顺序排序

关于第三点的解释：

首先，LinkedHashSet所有的构造方法都是调用HashSet的同一个构造方法，如下：

// LinkedHashSet专用的方法
    // dummy是没有实际意义的, 只是为了跟上上面那个操持方法签名不同而已
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        
        //调用LinkedHashMap的构造方法
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

然后，通过调用LinkedHashMap的构造方法初始化map，如下所示：

public LinkedHashMap(int initialCapacity, float loadFactor) {
        
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

可以看到，这里把`accessOrder`写死为false了。所以，LinkedHashSet是不支持按访问顺序对元素排序的，只能按插入顺序排序。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]

[img-94FAXYPH-1641084441885_HashSet_.assets_image-20211229154246790.png]: https://img-blog.csdnimg.cn/c4f79d49376d4e58a666d7065497ee93.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16
[img-DNxEaWlD-1641084441887_HashSet_LinkedHashSet_.assets_image-20211229165618772.png]: https://img-blog.csdnimg.cn/ca5ab8059f9c417d9302e33c1f30857f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/17215132bd1541d8b9ec6cf247303f13.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16