2.2、JDK 源码分析 - HashSet

原创
2022/07/19 12:12
阅读数 63

摘要

前面两篇博文,博主分别为小伙伴们分享了JDK1.7/1.8的HashMap底层原理;本篇博文将继续为大家分享HashSet底层源码;由于HashSet实现较为简单,博主这里只基于JDK1.8进行分享;

介绍

这个类实现了由哈希表(实际上是HashMap实例)支持的Set接口。 它不保证集合的迭代顺序; 特别是,它不能保证顺序会随着时间的推移保持不变。 这个类允许使用空元素。

这个类为基本操作(添加、删除、包含和大小)提供了恒定的时间性能,前提是哈希函数将元素适当地分散到存储桶中。 遍历这个集合所需的时间与HashSet实例的大小(元素的数量)加上后面的HashMap实例的“容量”(桶的数量)的总和成正比。 因此,如果迭代性能很重要,那么初始容量不要设置得太高(或者负载因子太低)是非常重要的。

注意,这个实现不是同步的。 如果多个线程同时访问一个hash set,并且至少有一个线程修改了该散列集,那么它必须在外部进行同步。 这通常通过对自然封装该集合的某些对象进行同步来完成。 如果不存在这样的对象,则应该使用Collections.synchronizedSet方法“包装”。 这最好在创建时完成,以防止意外的对集合的非同步访问: Set s = Collections.synchronizedSet(new HashSet(...));

这个类的迭代器方法返回的迭代器是快速失败的:如果在迭代器创建后的任何时间修改了集合,除了通过迭代器自己的remove方法之外的任何方式,迭代器都会抛出ConcurrentModificationException。 因此,在面对并发修改时,迭代器会快速而干净地失败,而不是冒着在未来某个不确定的时间发生任意的、不确定的行为的风险。请注意,迭代器的快速失败行为不能得到保证,因为一般来说,在存在非同步的并发修改时,不可能做出任何硬保证。 快速失败迭代器尽可能抛出ConcurrentModificationException。 因此,编写依赖此异常来保证其正确性的程序是错误的:迭代器的快速失败行为应该只用于检测错误。

源码解析

(1)、类定义

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();
    ...
}

从上面定义可以看出,HashSet底层是使用HashMap来实现的;并且存数据的时候,HashMap中key就是set中的真实数据对象,HashMap中value的都是虚拟对象PRESENT的引用;

(2)、构造方法

    /**
     * 构造一个新的空集; 后台HashMap实例具有默认的初始容量(16)和负载因子(0.75)。
     */
    public HashSet() {
        map = new HashMap<>();
    }
    /**
     * 构造一个包含指定集合中的元素的新集合。 HashMap是用默认的加载因子(0.75)和足够容纳指定集合中的元素的初始容量创建的。
     *
     * @param C是一个集合,它的元素被放置到这个集合中
     * @throws NullPointerException 如果指定的集合为空
     */
    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);
    }
    /**
     * 构造一个新的空的链接哈希集。 (此包私有构造函数仅用于LinkedHashSet。) 后备HashMap实例是一个LinkedHashMap,
     * 具有指定的初始容量和指定的加载因子。
     *
     * @param      initialCapacity   the initial capacity of the hash map
     * @param      loadFactor        the load factor of the hash map
     * @param      dummy            忽略(区分这  构造函数来自其他int, float构造函数。)
     * @throws     IllegalArgumentException if the initial capacity is less
     *             than zero, or if the load factor is nonpositive
     */
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

由上面的构造方法可以看出,HashSet底层使用的是HashMap,LinkedHashSet底层使用LinkedHashMap来实现。

(3)、iterator方法

    /**
     * 返回一个遍历该集合元素的迭代器。 返回的元素没有特定的顺序。
     */
    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }

此处即表明HashSet的集合对象就是Map中的key集合。

(4)、add方法

    /**
     * 如果指定元素不存在,则将其添加到此集合。
     *
     * @param e element to be added to this set
     * @return 如果此集合尚未包含指定的对象,true
     * element
     */
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

将set要存的对象作为key,PRESENT作为value存进底层map中;如果添加之前不包含该key,则返回true;否则,返回false.

(5)、remove方法

    /**
     * 如果指定元素存在,则从该集合中移除该元素。
     *
     * @param o object to be removed from this set, if present
     * @return 如果集合包含指定的元素,返回true;否则,返回false.
     */
    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }

总结:

1、以上就是HashSet的核心实现,可以看出,HashSet底层实现是靠HashMap来完成的。LinkedHashSet底层实现是靠LinkedHashMap来完成的。

2、HashSet的集合对象其实就是底层Map中的key的集合,底层Map中所有key映射的value都是同一个Object对象.

3、由于HashSet使用的是Hash定位,所以一般在元素较多,且用于判断元素是否存在的这种场景,使用HashSet的效率会比List效率高出很多。

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部