Java 集合框架系列八：JDK 1.8 HashSet 和 LinkedHashSet 详解

我就是我 2022-12-05 01:36 230阅读 0赞

## HashSet 类图 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dZQTE5OTM_size_16_color_FFFFFF_t_70_pic_center]  
HashSet 是在 JDK 1.2 提供的类，是 AbstractSet 的子类。HashSet 是 Set 集合比较常用的实现类。

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable { }

## 类文档解读 ##

老规矩，先通过 HashSet 的类文档了解一下能得到哪些信息。

*  HashSet 是一个基于哈希表的堆 Set 的实现。其内部持有了一个 HashMap 实例。
 *  HashSet 是无序的，这里的无序不是指随机性，而是按照 Hash 算法来存储集合中的元素，因此具有很好的存取和查找性能。
 *  HashSet 最多只允许一个 null 元素。
 *  HashSet 不是线程安全的。
 *  HashSet 返回的迭代器是 fail-fast 策略的。

## HashSet API ##

来看一下 HashSet 提供的方法的具体实现逻辑。

### 成员变量 ###

// 存储元素的数据结构 一个 HashMap 实例
    	private transient HashMap<E,Object> map;
    
        // 由于 HashSet 只需要使用 Key 进行存储，因此 Value 存储的是一个虚拟值
        private static final Object PRESENT = new Object();

到这里大致可以猜到 HashSet 内部使用 HashMap 存储元素的，所以 HashMap 具有的特性 HashSet 都有。

### 构造方法 ###

/** * 创建一个空的 HashMap，默认初始容量是 16，负载因子是 0.75 */
        public HashSet() { 
            map = new HashMap<>();
        }
    
        /** * 将指定集合的元素添加到内部的 HashMap 中，初始长度是指定集合的长度/0.75 + 1 与 16 比较的最大值 * @throws NullPointerException if the specified collection is null */
        public HashSet(Collection<? extends E> c) { 
            map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
            addAll(c);
        }
    
        /** * 创建一个 HashMap 指定初始容量和负载因子 */
        public HashSet(int initialCapacity, float loadFactor) { 
            map = new HashMap<>(initialCapacity, loadFactor);
        }
    
        /** * 创建一个 HashMap 指定初始容量，默认负载因子是 0.75 */
        public HashSet(int initialCapacity) { 
            map = new HashMap<>(initialCapacity);
        }
    
        /** * 使用 LinkedHashMap 创建一个 HashSet 实例，使用指定的初始容量和负载因子 * 此方法是非 public 的，是提供给子类 LinkedHashSet 使用的 * * @param dummy 没有特殊含义，仅仅是与 HashSet(int initialCapacity, float loadFactor) 进行区分 */
        HashSet(int initialCapacity, float loadFactor, boolean dummy) { 
            map = new LinkedHashMap<>(initialCapacity, loadFactor);
        }

### HashSet\#add ###

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

### HashSet\#remove ###

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

### HashSet\#contains ###

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

### HashSet\#clear ###

public void clear() { 
            map.clear();
        }

### HashSet\#size && HashSet\#isEmpty ###

public int size() { 
            return map.size();
        }
        
        public boolean isEmpty() { 
            return map.isEmpty();
        }

### HashSet\#iterator ###

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

可以看到 HashSet 重写的方法内部实际上都使用的是 HashMap 的方法对数据进行操作。

## LinkedHashSet 继承关系 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dZQTE5OTM_size_16_color_FFFFFF_t_70_pic_center 1]  
LinkedHashSet 是 HashSet 的子类，同样不允许元素重复并且非线程安全，它是在 JDK 1.4 才提供的。LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，但它同时使用双向链表维护元素的次序，这使得元素看起来是以插入顺序保存的。因为需要维护双端链表，LinkedHashSet 插入性能略低于 HashSet，但在迭代访问时可以直接对双端链表进行遍历所以性能比 HashSet 好。LinkedHashSet 维护插入顺序的性能成本要比 TreeSet 低。

## LinkedHashSet API ##

public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable { 
    
        /** * 调 HashSet 的构造器创建实例 指定初始容量和负载因子 */
        public LinkedHashSet(int initialCapacity, float loadFactor) { 
            super(initialCapacity, loadFactor, true);
        }
    
        /** * 指定初始容量和负载因子 */
        public LinkedHashSet(int initialCapacity) { 
            super(initialCapacity, .75f, true);
        }
    
        /** * 使用默认的初始容量和负载因子 */
        public LinkedHashSet() { 
            super(16, .75f, true);
        }
        
        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);
        }
    }

可以看到 LinkedHashSet 只重写 HashSet 的 spliterator 方法，其他方法内部具依然使用了 HashSet 的实现，唯一的区别是 LinkedHashSet 在实例化时使用的是 LinkedHashMap。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dZQTE5OTM_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/e837e4c84a674febbf4f0c5438f7e9fe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dZQTE5OTM_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/0ebc9eeb023a4599b96a49b31402f94c.png