集合实现

Set实现被分为通用实现和特殊实现。

通用Set实现

有三种通用的Set实现——HashSet、TreeSet和LinkedHashSet。一般来说，选择使用这三个中的哪一个是很简单的。HashSet比TreeSet快得多（大多数操作的时间复杂度为常数时间对比对数时间），但它没有任何顺序保证。如果你需要使用SortedSet接口中的操作，或者需要按值排序的迭代，使用TreeSet；否则，使用HashSet。很可能你大部分时间都会使用HashSet。

LinkedHashSet在某种意义上介于HashSet和TreeSet之间。它是一个哈希表，其中有一个链接列表，它提供插入顺序的迭代（从最近插入到最近的），并且几乎和HashSet一样快。LinkedHashSet的实现避免了由HashSet提供的不确定的、一般混乱的排序，而不会增加TreeSet所带来的额外开销。

关于HashSet值得注意的一点是，迭代的时间复杂度是条目数量和桶（容量）数量的总和。因此，选择一个过高的初始容量可能会浪费空间和时间。另一方面，选择一个过低的初始容量会浪费时间，因为每次强制增加容量时都需要复制数据结构。如果不指定初始容量，默认为16。在过去，选择一个质数作为初始容量有一些优势。但现在不再如此。内部上，容量总是向上取整为2的幂。初始容量可以通过使用int构造函数来指定。以下代码行分配了一个初始容量为64的HashSet。

Set<String> s = new HashSet<String>(64);

HashSet类还有一个称为负载因子的调优参数。如果你非常关心HashSet的空间消耗，请阅读HashSet的文档以获取更多信息。否则，只需接受默认值；通常默认值是正确的选择。

如果您接受默认的加载因子但想要指定初始容量，请选择一个大约是您期望集合增长到的大小的两倍的数字。如果您的猜测相差很大，可能会浪费一些空间、时间或两者兼而有之，但这不太可能是一个大问题。

LinkedHashSet具有与HashSet相同的调优参数，但迭代时间不受容量的影响。TreeSet没有调优参数。

特殊用途的Set实现

有两个特殊用途的Set实现 — EnumSet和CopyOnWriteArraySet。

EnumSet是一个高性能的Set实现，用于枚举类型。枚举集合的所有成员必须是相同的枚举类型。在内部，它由一个位向量表示，通常是一个单独的long。枚举集合支持对枚举类型范围的迭代。例如，给定一周的枚举声明，您可以遍历工作日。EnumSet类提供了一个静态工厂，使其变得容易。

    for (Day d : EnumSet.range(Day.MONDAY, Day.FRIDAY))
        System.out.println(d);

枚举集合还提供了传统位标志的丰富、类型安全的替代。

    EnumSet.of(Style.BOLD, Style.ITALIC)

CopyOnWriteArraySet是一个由写时复制数组支持的Set实现。所有的修改操作，例如add、set和remove，都通过创建数组的新副本来实现；不需要任何锁定。即使在元素插入和删除的同时进行迭代也是安全的。与大多数Set实现不同，add、remove和contains方法的时间复杂度与集合的大小成正比。这种实现仅适用于很少修改但经常迭代的集合。它非常适合于维护必须防止重复的事件处理程序列表。