HashSet源码解析-Java8

一.HashSet介绍

　　对于HashSet，用不着太多的介绍，可以先看一个简单的算法题：有一个数组，需要在O(n)的时间复杂度内，找出哪些数据是重复的。

　　上面这个问题，没有限制空间复杂度，则可以使用Map来完成，像下面这样做：

public List<String> findDuplicateData(String[] arr) {
    List<String> res = new ArrayList<>();
    Map<String, Boolean> map = new HashMap<>();

    for (String str : arr) {
        if (map.get(str) != Boolean.TRUE) {
            // 如果map中已经存在该str，则表示重复了，将其加入结果集合中
            res.add(str);

        } else {
            // 如果map中不存在str，则将其加入map，value为Boolean.TRUE
            map.put(str, Boolean.TRUE);
        }
    }

    return res;
}

　　上面在使用map的时候，可以看到，其实Map的value都始终都是Boolean.TRUE，这个时候，设置value其实很多余。

　　这个时候就可以使用HashSet来完成，相对来说更加好理解：

public List<String> findDuplicateData(String[] arr) {
    List<String> res = new ArrayList<>();
    Set<String> set = new HashSet<>();

    for (String str : arr) {
        if (set.contains(str)) {
            // 如果集合中已经存在该str，则表示重复了，将其加入结果集合中
            res.add(str);

        } else {
            // 如果集合中不存在str，则将其加入集合
            set.add(str);
        }
    }

    return res;
}

　　其实对于HashSet，并没有太多需要介绍的，他的特点如下：

　　1.增删改查set中的元素，时间复杂度都为O(1)；

　　2.不会出现重复元素；

　　3.顺序是不确定的；

　　这些特点通过后面看了HashSet的源码，也就明白了。

二.HashSet源码解析　

2.1 HashSet的原理概览

　　先简单的对HashSet的原理提一下，方便后面对源码的理解。

　　HashSet内部其实是基于HashMap的，上面我们使用map来完成put操作，value需要自定义；而在HashSet中，value是常量（一个Object对象）。

2.2 HashSet的属性

　　HashSet其实就只有两个属性，一个是map属性，用来保存HashSet.add()的数据；add的数据作为map的key，value则是PRESENT常量（一个普通Object对象）。

/**
 * 存放数据的map
 */
private transient HashMap<E,Object> map;

/**
 * map属性在put时的value
 */
private static final Object PRESENT = new Object();

2.3 构造方法

　　HashSet的构造方法，做的主要工作就是初始化map属性，将其赋值为一个HashMap。　　

/**
 * 实例化HashSet，并且创建HashMap（使用默认初始容量16和默认负载因子0.75）
 */
public HashSet() {
    map = new HashMap<>();
}

/**
 * 实例化HashSet，并且创建HashMap（使用自定义的初始容量和默认的负载因子0.75）
 */
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}


/**
 * 实例化HashSet，并且创建HashMap（使用自定义的初始容量和负载因子）
 */
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

/**
 * 实例化HashSet，并且创建HashMap（使用自定义的初始容量和负载因子）
 * 第3个参数时dummy（傀儡），如果有自己的额外需求，可以修改源码进行定制化
 */
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

2.4 add操作

　　HashSet.add()接口，将新元素加入到set集合中，内部其实是加入到HashMap中。

/**
 * 加入一个元素到set中（其实是加入到HashSet的map属性中）
 * 
 * @return true:set不包含该元素； false:set已经包含该元素
 */
public boolean add(E e) {
    // 调用HashMap的put方法，也就是将加入的元素作为key，PRESENT常量作为value
    return map.put(e, PRESENT) == null;
}

2.5 contains操作

/**
 * 判断元素是否存在于set集合中，内部其实是调用map的接口，判断是否存在该key的节点
 */
public boolean contains(Object o) {
    return map.containsKey(o);
}

2.6 remove操作

/**
 * 从set集合中移除某个元素，实际是移除HashMap中key为该元素的节点
 * 
 * @return true:成功移除元素； false:移除元素失败（未找到要移除的元素）
 */
public boolean remove(Object o) {
    return map.remove(o) == PRESENT;
}

2.7 size操作

/**
 * 返回set中的元素个数（也就是返回HashMap中的元素个数）
 */
public int size() {
    return map.size();
}

三.总结

　　看了上面HashSet的源码，其实可以发现，HashSet其实就是利用HashMap，在HashMap上套了一层壳。使用HashMap也能完成HashSet的工作，但是HashSet在某些时候对于代码的可读性更加好。

　　原文地址：https://www.cnblogs.com/-beyond/p/13428580.html