“合抱之木 生于毫末 九层之台 起于累土 千里之行 始于足下”

前言

JDK 版本1.7

Collection 大家族

来源Java Collections Framework

HashSet 继承树

分析

概述

HashSet它是基于HashMap实现的，HashSet底层使用HashMap来保存所有元素，因此HashSet的实现比较简单，相关HashSet的操作，基本上都是直接调用底层HashMap的相关方法来完成，我们应该为保存到HashSet中的对象覆盖hashCode()和equals()来保证

HashSet继承AbstractSet类，实现Set、Cloneable、Serializable接口。其中AbstractSet提供 Set 接口的骨干实现，从而最大限度地减少了实现此接口所需的工作。

成员变量

    static final long serialVersionUID = -5024744406713321676L;

    // 保存数据的Map
    private transient HashMap<E,Object> map;

    // 用来保存Map的Value值
    private static final Object PRESENT = new Object();

构造方法

    /**
     * 构造一个HashSet使用默认的参数
     */
    public HashSet() {
        map = new HashMap<>();
    }

    /**
     * 构造一个空的HashSet并把c的数据全部放入
     *
     * @param c 集合
     * @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);
    }

    /**
     * 构造一个空的HashSet使用指定容量和加载系数
     *
     * @param      initialCapacity   指定容量
     * @param      loadFactor        指定加载系数
     * @throws     IllegalArgumentException
     */
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }

    /**
     * 构造一个空的HashSet使用指定容量
     *
     * @param      initialCapacity   指定容量
     * @throws     IllegalArgumentException
     */
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }

    /**
     * 访问权限为包权限，不对外公开
     * 以指定指定容量和指定加载系数构造一个新的HashSet
     *
     * @param      initialCapacity   指定容量
     * @param      loadFactor        指定加载系数
     * @param      dummy             dummy 为标识 该构造函数主要作用是对LinkedHashSet起到一个支持作用
     * @throws     IllegalArgumentException
     */
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

方法

HashSet底层使用了HashMap实现,使其的实现过程变得非常简单,他仅使用了HashMap的Key用来存放数据,Value存放的是一个空对象,了解了HashMap的原理,HashSet的原理就一目了然了。

HashMap 的put()方法添加key-value时，当新put()HashMap的Entry中key与集合中原有Entry的key相同（hashCode()返回值相等，通过equals()比较也返回 true),新添加的Entry的value会将覆盖原来Entry的value(HashSet中的value都是PRESENT),但key不会有任何改变,因此如果向HashSet中添加一个已经存在的元素时,新添加的集合元素将不会被放入HashMap中,原来的元素也不会有任何改变,这也就满足了Set中元素不重复的特性。

    /**
     * 添加一个元素
     *
     * @param e 元素
     */
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
    /**
     * 删除一个元素
     *
     * @param o 元素
     */
    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }
    /**
     * 判断元素是否在集合中
     *
     * @param o 元素
     */
    public boolean contains(Object o) {
        return map.containsKey(o);
    }

遍历

    /**
     * 获取Map中的keys
     *
     */
    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }

总结

HashSet的实现算是简单的,原因在于他直接使用了HashMap做底层存储,HashMap算比较复杂的集合,踩着巨人的肩膀,

著作权声明

本文首次发布于 Binux Blog，转载请保留以上链接