【Java集合框架】13——HashSet 类

HashSet类实现了Set接口，其背后是一个哈希表，实际上是一个HashMap实例。不保证集合的迭代顺序，这意味着类不保证元素随时间的变化顺序不变。这个类允许使用空元素。这个类还为添加、删除、包含和大小等基本操作提供了恒定的时间性能，前提是哈希函数将元素适当地分散到存储桶中，我们将在本文中进一步介绍这些操作。

HashSet的几个重要特性有:

• 实现set接口。
• HashSet的底层数据结构是Hashtable。
• 因为它实现了Set接口，所以不允许重复的值。
• 在HashSet中插入的对象不保证以相同的顺序插入。对象是根据其散列代码插入的。
• HashSet中允许有NULL元素。
• HashSet还实现了Serializable和Cloneable接口。

HashSet的层次结构如下:

HashSet扩展了抽象集类，并实现了Set， Cloneable和Serializable接口，其中E是该集合维护的元素类型。HashSet的直接子类是LinkedHashSet。

现在为了维护恒定的时间性能，遍历HashSet需要的时间与HashSet实例的大小(元素的数量)加上后面的HashMap实例的“容量”(桶的数量)的总和成正比。因此，如果迭代性能很重要，那么初始容量不要设置得太高(或者负载因子太低)是非常重要的。

• 初始容量:初始容量是指创建哈希表(HashSet内部使用哈希表数据结构)时的桶数。如果当前大小已满，则桶的数量将自动增加。
• 负载因子:负载因子是在HashSet容量自动增加之前允许其达到的满度的度量。当哈希表中的条目数量超过负载因子和当前容量的乘积时，哈希表将被重新哈希(即重新构建内部数据结构)，这样哈希表的存储桶数量大约是原来的两倍。

示例:如果内部容量为16，负载因子为0.75，那么当表中有12个元素时，桶的数量将自动增加。

对性能的影响:负载因子和初始容量是影响HashSet操作性能的两个主要因素。就时间和空间复杂度而言，0.75的负载因子提供了非常有效的性能。如果我们将负载因子值增加更多，那么内存开销将会减少(因为它会减少内部重建操作)，但是，它会影响哈希表中的添加和搜索操作。为了减少重哈希操作，我们应该明智地选择初始容量。如果初始容量大于最大条目数除以负载因子，则不会发生重hash操作。

注意:HashSet中的实现不是同步的，也就是说，如果多个线程同时访问一个哈希集，并且至少有一个线程修改了这个集，那么它必须在外部同步。这通常通过对自然封装该集合的某些对象进行同步来完成。如果不存在这样的对象，则应该使用Collections“包装”集合。synchronizedSet方法。这最好在创建时完成，以防止意外的不同步访问集，如下所示:

Set s = Collections.synchronizedSet(new HashSet(...));

HashSet 类的声明

public class HashSet extends AbstractSet implements Set, Cloneable, Serializable

其中E是存储在HashSet中的元素类型。
HashSet的内部工作方式:Set接口的所有类都由Map在内部备份。HashSet使用HashMap在内部存储它的对象。您一定想知道，要在HashMap中输入一个值，我们需要一个键值对，但在HashSet中，我们只传递了一个值。
存储在HashMap中:实际上，我们在HashSet中插入的值充当映射对象的键，java使用常量变量来表示它的值。因此，在键值对中，所有值都是相同的。

HashSet不仅存储唯一的对象，而且还存储唯一的对象集合，如ArrayList， LinkedList， Vector，…等等。

实例：

    public static void main(String[] args) {
        // 新建hashSet对象
        HashSet set = new HashSet<>();

        // 创建 ArrayList 列表1
        ArrayList list1 = new ArrayList<>();

        // 创建 ArrayList 列表2
        ArrayList list2 = new ArrayList<>();

        // list1 和list2 添加元素
        list1.add(1);
        list1.add(2);
        list2.add(1);
        list2.add(2);
        // 把 两个列表 添加到  HashSet 里面
        set.add(list1);
        set.add(list2);

        // 输出HashSet 的大小
        System.out.println(set);
        // hashSet 去掉重复的元素
        System.out.println(set.size());
    }

输出

[[1, 2]]
1

在存储Object之前，HashSet会使用hashCode()和equals()方法检查是否存在现有的条目。在上面的例子中，如果两个列表具有相同顺序的相同元素，则认为它们是相等的。当您在两个列表上调用hashCode()方法时，它们都将给出相同的散列，因为它们是相等的。

HashSet不存储重复的项目，如果你给了两个相等的对象，那么它只存储第一个，这里是list1。

HashSet类的构造函数

为了创建HashSet，我们需要创建HashSet类的一个对象。HashSet类由各种构造函数组成，这些构造函数允许创建HashSet。下面是这个类中可用的构造函数。

• HashSet()：此构造函数用于构建一个空HashSet对象，其中默认初始容量为16，默认负载因子为0.75。如果我们希望创建一个名为hs的空HashSet，那么，可以这样创建:

HashSet hs = new HashSet();

• HashSet(int initialCapacity):T此构造函数用于构建一个空HashSet对象，其中initialCapacity在对象创建时指定。这里，默认的loadFactor保持0.75。

 HashSet hs = new HashSet(int initialCapacity);

• HashSet(int initialCapacity, float loadFactor)：这个构造函数用于构建一个空的HashSet对象，在创建对象时在其中指定initialCapacity和loadFactor。

HashSet hs = new HashSet(int initialCapacity, float loadFactor);

• HashSet(Collection):该构造函数用于构建包含给定集合中所有元素的HashSet对象。简而言之，当需要从任何Collection对象到HashSet对象进行任何转换时，就使用这个构造函数。如果我们想创建一个名为hs的HashSet，可以这样创建:

HashSet hs = new HashSet(Collection C);

为了向HashSet中添加元素，可以使用add()方法。但是，HashSet中不保留插入顺序。我们需要注意的是，不允许重复元素，并且忽略所有重复元素。

实例：

    public static void main(String[] args) {
        // new HashSet
        HashSet hs = new HashSet();

        // 添加元素
        hs.add("广州");
        hs.add("深圳");
        hs.add("珠海");
        hs.add("珠海"); // HashSet 具有去重功能

        // 打印元素
        System.out.println("HashSet 元素 : " + hs);
    }

输出：

HashSet 元素 : [广州, 珠海, 深圳]

可以使用remove()方法从HashSet中删除这些值。

实例：

    public static void main(String[] args) {
        // new HashSet
        HashSet hs = new HashSet();

        // 添加元素
        hs.add("广州");
        hs.add("深圳");
        hs.add("珠海");

        // 打印元素
        System.out.println("HashSet 添加后元素 : " + hs);

        // 删除 珠海
        hs.remove("珠海");

        // 输出 删除珠海后的元素
        System.out.println("删除珠海后的元素 " + hs);

        // 删除不存在的元素，即返回false
        System.out.println("删除不存在的元素: "
                + hs.remove("东莞"));
    }

输出：

HashSet 添加后元素 : [广州, 珠海, 深圳]
删除珠海后的元素 [广州, 深圳]
删除不存在的元素: false

使用iterator()方法遍历HashSet中的元素。另外，最著名的方法是使用增强的for循环。

实例：

    public static void main(String[] args) {
        // new HashSet
        HashSet hs = new HashSet();

        // 添加元素
        hs.add("广州");
        hs.add("深圳");
        hs.add("珠海");

        // 打印元素
        System.out.println("HashSet 添加后元素 : " + hs);

        // 使用Hash的迭代器
        Iterator itr = hs.iterator();

        // 直到Set中只剩下一个元素为止
        while (itr.hasNext())

            // 遍历元素并打印它们
            System.out.print(itr.next() + ", ");
        System.out.println();

        // 使用增强的for循环进行遍历：for-each
        for (String s : hs)

            // 遍历元素并打印它们
            System.out.print(s + ", ");
        System.out.println();
    }

输出：

HashSet 添加后元素 : [广州, 珠海, 深圳]
广州, 珠海, 深圳, 
广州, 珠海, 深圳, 

HashSet操作的时间复杂度:HashSet的底层数据结构是哈希表。因此，摊销(平均或通常情况)HashSet的添加、删除和查找(包含方法)操作的时间复杂度为O(1)。

Hash 的方法

从类java.util.AbstractSet继承的方法

从类java.util.AbstractCollection继承的方法

接口java.util.Collection中声明的方法

接口java.lang.Iterable中声明的方法

接口java.util.Set中声明的方法

待续