麦溪·在路上 | 麦溪·在路上

前面，我们已经系统的对List和Map进行了学习。接下来，我们开始可以学习Set。相信经过Map的了解之后，学习Set会容易很多。毕竟，Set的实现类都是基于Map来实现的(HashSet是通过HashMap实现的，TreeSet是通过TreeMap实现的)。

首先，我们看看Set架构。

public interface Set<E> extends Collection<E> {
    
    int size();

    boolean isEmpty();
    
    boolean contains(Object o);
    
    Iterator<E> iterator();
    
    Object[] toArray();
    
    <T> T[] toArray(T[] a);
    
    boolean add(E e);
    
    boolean remove(Object o);
    
    boolean containsAll(Collection<?> c);
    
    boolean addAll(Collection<? extends E> c);
    
    boolean retainAll(Collection<?> c);
    
    boolean removeAll(Collection<?> c);
    
    void clear();
    
    boolean equals(Object o);
    
    int hashCode();
}

(01) Set 是继承于Collection的接口。它是一个不允许有重复元素的集合。

(02) AbstractSet 是一个抽象类，它继承于AbstractCollection，AbstractCollection实现了Set中的绝大部分函数，为Set的实现类提供了便利。

(03) HastSet 和 TreeSet 是Set的两个实现类。

HashSet依赖于HashMap，它实际上是通过HashMap实现的。HashSet中的元素是无序的。

TreeSet依赖于TreeMap，它实际上是通过TreeMap实现的。TreeSet中的元素是有序的。

HashSet基础学习

HashSet 是一个没有重复元素的集合。

它是由HashMap实现的，不保证元素的顺序，而且HashSet允许使用 null 元素。

HashSet是非同步的。如果多个线程同时访问一个哈希 set，而其中至少一个线程修改了该 set，那么它必须保持外部同步。这通常是通过对自然封装该 set 的对象执行同步操作来完成的。如果不存在这样的对象，则应该使用 Collections.synchronizedSet 方法来“包装” set。最好在创建时完成这一操作，以防止对该 set 进行意外的不同步访问：

HashSet的构造函数

// 默认构造函数
public HashSet() 

// 带集合的构造函数
public HashSet(Collection<? extends E> c) 

// 指定HashSet初始容量和加载因子的构造函数
public HashSet(int initialCapacity, float loadFactor) 

// 指定HashSet初始容量的构造函数
public HashSet(int initialCapacity) 

// 指定HashSet初始容量和加载因子的构造函数,dummy没有任何作用
HashSet(int initialCapacity, float loadFactor, boolean dummy)

HashSet数据结构

我们来看一下HashSet的继承关系

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

(01) HashSet继承于AbstractSet，并且实现了Set接口。

(02) HashSet的本质是一个”没有重复元素”的集合，它是通过HashMap实现的。HashSet中含有一个”HashMap类型的成员变量”map，HashSet的操作函数，实际上都是通过map实现的。

为了更了解HashSet的原理，下面对HashSet源码代码作出分析。

HashSet遍历方式

4.1 通过Iterator遍历HashSet

第一步：根据iterator()获取HashSet的迭代器。

第二步：遍历迭代器获取各个元素。

// 假设set是HashSet对象
for(Iterator iterator = set.iterator();
       iterator.hasNext(); ) { 
    iterator.next();
}

4.2 通过for-each遍历HashSet

第一步：根据toArray()获取HashSet的元素集合对应的数组。
第二步：遍历数组，获取各个元素。

// 假设set是HashSet对象，并且set中元素是String类型
String[] arr = (String[])set.toArray(new String[0]);
for (String str:arr)
    System.out.printf("for each : %s\n", str);

TreeSet基础学习

TreeSet简介

TreeSet 是一个有序的集合，它的作用是提供有序的Set集合。它继承于AbstractSet抽象类，实现了NavigableSet, Cloneable, java.io.Serializable接口。

TreeSet 继承于AbstractSet，所以它是一个Set集合，具有Set的属性和方法。

TreeSet 实现了NavigableSet接口，意味着它支持一系列的导航方法。比如查找与指定目标最匹配项。

TreeSet 实现了Cloneable接口，意味着它能被克隆。

TreeSet 实现了java.io.Serializable接口，意味着它支持序列化。

TreeSet是基于TreeMap实现的。TreeSet中的元素支持2种排序方式：自然排序或者根据创建TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法。

TreeSet为基本操作（add、remove 和 contains）提供受保证的 log(n) 时间开销。

另外，TreeSet是非同步的。它的iterator 方法返回的迭代器是fail-fast的。

TreeSet的构造函数

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    // 默认构造函数。使用该构造函数，TreeSet中的元素按照自然排序进行排列。
    TreeSet()

    // 创建的TreeSet包含collection
    TreeSet(Collection<? extends E> collection)

    // 指定TreeSet的比较器
    TreeSet(Comparator<? super E> comparator)

    // 创建的TreeSet包含set
    TreeSet(SortedSet<E> set)
}

文章参考：https://www.cnblogs.com/skywang12345/p/3311268.html