java基础进阶篇(五)_HashSet------【java源码栈】

一.概述

??对于HashSet而言，它是基于HashMap来实现的，底层采用HashMap来保存元素。HashSet中的元素都存放在HashMap的key上面，而value中的值都是统一的一个private static final Object PRESENT = new Object();。HashSet跟HashMap一样，都是一个存放链表的数组。

二.源码分析

1.HashSet 源码

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

??加上摘自HashSet顶部的一段注释:

/**
 * This class implements the <tt>Set</tt> interface, backed by a hash table
 * (actually a <tt>HashMap</tt> instance).  It makes no guarantees as to the
 * iteration order of the set; in particular, it does not guarantee that the
 * order will remain constant over time.  This class permits the <tt>null</tt>
 * element.
 */

??分析理解下,大致意思是(这捉鸡的English):
??1.HashSet : 内部存储一个泛型元素.
??2.HashSet 实现了Set 接口,提供了所有可选的 Set 操作.
??3.继承自AbstractSet，实现Set接口时需要实现的工作量大大减少了.
??4.实现了Cloneable 接口, 可以调用 clone() 方法来返回实例的 field-for-field 拷贝.
??5.实现了序列化接口,可以序列化
??6.由hash 表进行维护, 底层实际是一个HashMap 的实例对象.
??7.不保证插入时的顺序, HashSet 是有自己的一套排序的.
??8.允许null 元素.
??底层是支持键值对Key-Value 的HashMap, 但HashSet 内部却只支持一个元素, 因为HashSet 只占用了HashMap 的Key 进行数据存储.

2.两个重要成员变量

1.HashMap<E,Object> map

??底层用HashMap 的实例对象来维护:

private transient HashMap<E,Object> map;

2.PRESENT

??HashMap是保存键值对的，但HashSet实际上只保存了key, 因此创建一个PRESENT存储所有的HashSet 元素.

private static final Object PRESENT = new Object();

三.构造方法

1.public HashSet();

??构造一个新的空的HashSet, 底层是构造一个空的容量为16,负载因子是0.75的HashMap.

/**
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
 * default initial capacity (16) and load factor (0.75).
 */
public HashSet() {
    map = new HashMap<>();
}

??比如:

HashSet<Object> set1 = new HashSet<Object>();
set1.add("a");
set1.add("c");
set1.add("b");
set1.add("1");
set1.add("3");
set1.add("2");
System.out.println(set1);

??输出结果:

[a, 1, b, 2, c, 3]

??顺序并非插入时的顺序, HashSet 是按照哈希函数计算出key 的存放坐标. 关于这部分后面章节再单独研究整理.

2.public HashSet(Collection<? extends E> c);

??构造一个包含指定集合中所有元素的新HashSet,

HashSet<Object> set2 = new HashSet<Object>(Arrays.asList("a","b","c"));
System.out.println(set2);

??输出结果:

[a, b, c]

3.public HashSet(int initialCapacity, float loadFactor);

??构造一个新的空set，其底层HashMap实例具有指定的初始容量和加载因子

HashSet<Object> set3 = new HashSet<Object>(10, 0.5f);

4.public HashSet(int initialCapacity);

??构造一个新的空set，其底层HashMap实例具有指定的初始容量和默认的加载因子 (0.75)

HashSet<Object> set4 = new HashSet<Object>(10);

5.特殊的构造方法

??该方法仅用于构造 LinkedHashSet，创建的是 LinkedHashMap 而非之前的 HashMap，用于维护 Set 内元素的顺序, 通过增加一个dummy 参数来调用该方法.

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

??查看源码发现, 该方法除了指定初始容量initialCapacity; 负载因子 loadFactor, 多了一个参数dummy, 仅用于识别构造方法. 底层创建的是LinkedHashMap;

??关于LinkedHashMap后面章节会列出其原理和使用. 在此先简单介绍下. HashMap是无序的，当我们希望有顺序地去存储key-value时，就需要使用LinkedHashMap了, LinkedHashMap 能保证内部key-value是有序的.

四.常用方法

HashSet 的方法很少, 使用相对简单,

1.int size()

??源码如下, 实际是返回底层map的key数量.

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

2.boolean isEmpty()

??源码如下,判断元素数量是否为0, 不能判断null 的情况, 底层调用的是map 的isEmpty方法.

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

3.boolean contains(Object o)

??源码如下, 判断是否包含参数元素, 底层调用map的contains方法.

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

4.boolean add(E e)

??源码如下,添加元素, 不保证插入时候的顺序, 底层调用map的put方法,返回时添加了==null的判断.真出现返回false的情况时, 应该考虑下容量问题了.

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

5.boolean remove(Object o)

??源码如下,删除指定元素, 若该元素存在则返回true,否则返回false.

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

??这里可能有人会疑问为什么map.remove(o)==PRESENT; 这俩会相等???

??思考下HashSet 的特点, 是利用了Map 的key 来存储自己的元素, map.remove(o)返回的是该key对应的value, 而set 没有在map 的value 上赋值, 源码底层默认给了空的Object类型,不是null, 和PRESENT 刚好相等.

// Dummy value to associate with an Object in the backing Map
// 伪造一个值去支持底层的map, 英语捉鸡, 大概就这意思...
private static final Object PRESENT = new Object();

6.void clear()

??源码如下, 清空set 元素, 使其size等于0.

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

7.Object clone()

??源码如下,复制一个set, 注意这里的复制仍然是浅复制, 若泛型不是基本类型的包装类, 则仅拷贝对象, 复制后的对象和复制前是同一个引用地址!

public Object clone() {
    try {
        HashSet<E> newSet = (HashSet<E>) super.clone();
        newSet.map = (HashMap<E, Object>) map.clone();
        return newSet;
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
}

??举例:

HashSet<Object> set1 = new HashSet<Object>();
set1.add("a");
set1.add("c");
set1.add("b");
System.out.println(set1);
HashSet<Object> set2 = (HashSet<Object>) set1.clone();
System.out.println(set2);
System.out.println(set2.equals(set1));

User user = new User("1","tom");
HashSet<User> userSet1 = new HashSet<User>();
userSet1.add(user);
HashSet<User> userSet2 = (HashSet<User>) userSet1.clone();
System.out.println("复制前, 修改user前, userSet1: " + userSet1);
Iterator<User> iterator = userSet1.iterator();
while (iterator.hasNext()) {
    User temp = iterator.next();
    temp.setId("2");
}
System.out.println("复制后, 修改user后, userSet2: " + userSet2);
System.out.println("复制前, 修改user后, userSet1: " + userSet1);

??输出结果:

[a, b, c]
[a, b, c]
true
复制前, 修改user前, userSet1: [User [id=1, name=tom]]
复制后, 修改user后, userSet2: [User [id=2, name=tom]]
复制前, 修改user后, userSet1: [User [id=2, name=tom]]

??复制后修改了userSet1, 把user id从1->2, 发现userSet2也被修改了, 所以慎用!

8.spliterator()

??源码如下, java8 之后出现的迭代器, 支持对集合进行并行遍历, 先列在这儿, 后面我会对多线程并发的情况下数组集合的遍历处理做总结.

public Spliterator<E> spliterator() {
    return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0);
}

9.iterator()

??源码如下, 底层利用了map的iterator 方法.

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