三.实现

在讲完了Java集合框架中的基本接口后，现在我们来学习这些接口的实现。本文描述了以下几种实现：

通用实现——最常用的实现，专为日常使用而设计。

专用实现——专门为一些特殊场景设计，性能、限制或行为可能与通用实现不同。

并发实现——旨在支持高并发性。

包装实现——包装其他类型的实现（通常是通用实现），以增加或限制功能。

便捷实现——通常是通过静态工厂方法提供的迷你实现，为特殊集合（例如单例集）的实现提供方便、有效的替代方案。

抽象实现——可以理解为骨架实现，有助于方便、快速地构建自定义实现。

下面将依次对第二节中提到的接口的实现进行介绍。在介绍实现时，由于之前已经对各接口中定义的方法做了说明，因此不再重复阐述，只是描述各实现类的特点和注意事项。

进群：697699179可以获取Java、大数据各类入门学习资料！

这是我的微信公众号【编程study】各位大佬有空可以关注下，每天更新Java、大数据学习方法，感谢！

学习中遇到问题有不明白的地方，推荐加小编Java|大数据学习群：697699179内有视频教程 ，直播课程 ，等学习资料，期待你的加入

1.Set实现

通用实现

Java平台中提供的Set接口的通用实现是HashSet、TreeSet和LinkedHashSet。HashSet将元素存在一个哈希表中，是性能最佳的实现，但是它不能保证迭代的顺序。TreeSet将元素存储在一个红黑树中，根据元素的值来进行排序，它比HashSet慢得多。LinkedHashSet同时具备了链表和哈希表的特点，使用链表来保存插入顺序，使用哈希表来快速定位元素，也就是说它的遍历顺序和插入顺序是一致的，但同时它的成本也是最高的。在实际使用过程中，可以灵活选择这几种Set。如果对遍历的顺序没有要求或者不需要遍历，可以选择HashSet；如果在遍历时需要按照元素的值进行排序，可以选择TreeSet；如果需要按照插入顺序遍历，可以选择LinkedHashSet。

实际上，有关这些实现类还有很多实现细节没有介绍。由于本系列是基础教程，因此不再过多深入。后续会推出阅读Java源码的系列，届时将会对Java中部分常用的类的源码进行详细介绍，敬请期待。

专用实现

Java提供了两个Set接口的专用实现——EnumSet和CopyOnWriteArraySet。

EnumSet是为枚举类型提供的高性能实现。EnumSet的所有成员必须具有相同的枚举类型。下面是EnumSet类中提供的构造EnumSet的工厂方法：

EnumSet内部维护了一个存储该枚举类型所有成员的数组，还有一个表示每个枚举成员是否存在于集合内的“位向量”，这个“位向量”可能是long也可能是long数组。因为每个枚举对象都有一个序号，因此位向量使用序号对应的位上的0或1来表示该对象是否存在于集合中。例如，现在我们有一个关于星期的枚举类型：

public enum Day {

    SUNDAY, MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY

}

我们使用of方法来创建一个EnumSet实例：

Set<Day> days = EnumSet.of(Day.TUESDAY, Day.FRIDAY);

那么对于这个EnumSet来说，它的位向量是下面这样的：

实际上，EnumSet是一个抽象类。java.util包中提供了它的两个子类，分别是RegularEnumSet和JumboEnumSet，RegularEnumSet使用一个long变量来表示位向量，而JumboEnumSet则使用long数组来表示位向量。在使用EnumSet的工厂方法构建实例时，它会自己选择使用哪个子类，而无需我们关心。

现在来看另外一个专用实现——CopyOnWriteArraySet。在介绍这个类之前，首先我们要了解一下CopyOnWrite的概念。这个术语的字面意思是在写的时候复制，实际上也是这么做的。在修改某个数据时，我们先拷贝一份副本，在副本上进行写操作，然后再替换之前的数据。这样可以避免在写数据时，因为加锁而造成其他读线程等待的情况。CopyOnWriteArraySet内部使用数组来保存元素，当对集合进行修改操作时（例如add、set或remove等），它会先将数组拷贝出一个副本，然后对这个副本进行操作，最后再将对原数组的引用指向新的数组。实际上，CopyOnWriteArraySet内部使用了下文中List接口的实现类CopyOnWriteArrayList来保存元素，而CopyOnWriteArrayList才是真正使用数组来实现的。

正是由于这个机制，CopyOnWriteArraySet具有以下特点：

它适用于读操作远远多于写操作的场景，因为写操作代价较高，它通常意味着复制整个底层数组；

它是线程安全的；

迭代器不支持remove操作；

读进程有可能读到的是过时的数据；

读写进程之间没有竞争，但是写进程之间还是需要加锁。

2.List实现

通用实现

Java集合框架中提供了两个List集合的通用实现——ArrayList和LinkedList。ArrayList内部使用数组实现，因此它的访问速度非常快。但正是由于它内部使用数组，因此在指定位置处添加或删除元素时需要移动后面所有的元素。需要注意的是，它并不是线程安全的。不过，可以使用Collections类的synchronizedList方法来将一个ArrayList转换为线程安全的对象。

如果需要频繁地在List的开头添加或删除元素并且元素的个数非常多时，则应考虑使用LinkedList。它是使用链表来实现的，因此它的添加和删除元素操作非常快。但正是由于链式结构，因此它的访问速度则需要花费线性时间。此外，LinkedList还实现了Deque，因此它支持Deque接口中定义的操作。

在使用List时，要充分考量程序的性能，来选择使用ArrayList还是LinkedList。一般来说，ArrayList更快。

专用实现

Java提供了两个List接口的专用实现——Vector和CopyOnWriteArrayList。

Vector是线程安全的List，并且它比经过Collections.synchronizedList处理过的ArrayList还要快一点。但是Vector中含有大量的遗留代码，毕竟它从Java1.0就开始存在了，当时还没有集合框架。从Java1.2开始，这个类被改进以实现List接口，使其成为Java集合框架的一员。因此，在使用Vector时，应该尽量使用List接口去操作。

CopyOnWriteArrayList的原理在上文中对CopyOnWriteArraySet的介绍中已经做了说明，这里不再赘述。

3.Map实现

通用实现

Map接口的三个通用实现分别是HashMap、TreeMap和LinkedHashMap。如果你想要最快的速度而不关心迭代顺序，请使用HashMap。如果需要SortMap操作或按键排序的迭代顺序，请使用TreeMap。如果需要接近HashMap的速度和按插入顺序迭代，请使用LinkedHashMap。这三个实现和Set接口中的三个通用实现非常类似。

虽然LinkedHashMap默认是按照插入顺序来排序，但是可以在构造LinkedHashMap实例时指定另外一种排序规则。这种规则按照最近对每个键值对的访问次数来排序，通过这种Map可以很方便地构建LRU缓存（Least Recently Used，一种缓存策略）。LinkedHashMap还提供了removeEldestEntry方法，通过覆盖该方法，可以定义何时删除旧缓存。例如，假如我们的缓存最多只允许100个元素，在缓存中的元素个数达到100个之后，每次添加新元素时都要清除旧元素，从而保持100个元素的稳定状态，可以像下面这样：

private static final int MAX_ENTRIES = 100;

protected boolean removeEldestEntry(Map.Entry eldest) {

    return size() > MAX_ENTRIES;

}

实际上，还有一个Map接口的通用实现——Hashtable（注意小写）。它也是从Java1.0开始就存在的一个“元老”。从Java1.2开始，它被改进以实现Map接口。它是线程安全的，但是由于效率较低，单线程时可以使用HashMap来代替，多线程时又可以使用下文中的ConcurrentHashMap来代替，因此这个类现在已经不再推荐使用。

专用实现

Java提供了三个Map接口的专用实现——EnumMap，WeakHashMap和IdentityHashMap。

EnumMap用在那些需要将枚举元素作为键的映射中，它的底层是使用数组来实现的。EnumMap是一个Map与枚举键一起使用的高性能实现。该实现将Map接口的丰富性和安全性与数组的速度相结合。如果要将枚举映射到值，则应始优先考虑EnumMap。

WeakHashMap只存储对其键的弱引用。JVM提供了四种类型的引用，分别是强引用、弱引用、软引用和虚引用，可以让程序员来决定某些对象的生命周期，有利于JVM进行垃圾回收。在进行垃圾回收时，若某个对象只具有弱引用，它一定会被回收。因此，当WeakHashMap中的键不再被外部引用时，JVM将会对它进行回收，该键值对也会消失。

IdentityHashMap在比较键时使用引用相等性代替对象相等性。在正常的Map实现中，当key1.equals(key2)返回true时，我们就认为这两个key是相等的；而在IdentityHashMap中，只有当key1==key2时，才认为这两个key是相等的。

并发实现

ConcurrentHashMap时Java提供的一个高并发、高性能的Map实现，它位于java.util.concurrent包中。这个实现在执行读操作时不需要加锁。因为这个类旨在作为Hashtable的替代品，因此，除了实现ConcurrentMap接口外（为线程安全Map定义的接口），它还保留了大量Hashtable中的遗留代码。因此，在使用ConcurrentHashMap时，应该尽量使用ConcurrentMap或Map接口去操作。

4.Queue实现

通用实现

Queue接口的通用实现包括LinkedList和PriorityQueue。

我们已经在List实现中介绍了LinkedList，为什么还要在Queue实现中再次提到它呢？这是因为LinkedList同时实现了List接口和Deque接口，而Deque接口又是Queue的子接口。因此，LinkedList可以算是List、Queue和Deque的实现。当我们使用不同的接口去引用LinkedList实例时，它就会表现出不同的行为。

PriorityQueue用来表示基于堆结构的优先级队列。它使用指定的排序规则来对元素进行排序，而不是按照队列默认的先进先出的顺序。在对PriorityQueue进行遍历时，迭代器不保证以任何特定顺序遍历优先级队列的元素。如果需要有序遍历，可以使用Arrays.sort(pq.toArray())。

并发实现

java.util.concurrent包中提供了一组Queue实现类，这些类都是线程安全的，因此可以在多线程中使用。这些类都实现了BlockingQueue接口，这个接口继承了Queue接口并且增加了一些额外的操作，支持当获取队列元素但是队列为空时，会阻塞等待队列中有元素再返回或超时返回；也支持添加元素时，如果队列已满，那么等到队列可以放入新元素时再放入或超时返回。

下表是BlockingQueue接口中操作元素的方法，除了继承自Queue接口的抛出异常和返回特定值的形式外，又增加了阻塞和超时两种形式：

下面是BlockingQueue接口的实现类：

LinkedBlockingQueue——由链式节点实现的有界FIFO阻塞队列。

ArrayBlockingQueue——由数组实现的有界FIFO阻塞队列。

PriorityBlockingQueue——由堆实现的无界阻塞优先级队列。

DelayQueue——支持延时获取元素的无界阻塞队列。

SynchronousQueue——同步阻塞队列，无容量，它的每个插入操作都要等待其他线程相应的移除操作，反之亦然。

此外，java.util.concurrent包中还定义了TransferQueue接口，它是BlockingQueue的子接口。在添加元素时，除了BlockingQueue中定义的方法，TransferQueue还定义了transfer和tryTransfer方法。transfer方法在传递元素时，若存在消费者，则立即将元素传递给消费者，否则将元素插入到队列尾部；tryTransfer方法在传递元素时，若存在消费者，则立即将元素传递给消费者，否则将元素插入到队列尾部，若在指定的时间内元素没有被消费者获取，则将该元素从队列中移除并返回false。TransferQueue接口有一个基于链式节点的无界实现——LinkedTransferQueue。

5.Deque实现

通用实现

Deque接口的通用实现包括LinkedList和ArrayDeque。ArrayDeque使用可调整大小的数组实现，而 LinkedList则是链表实现。

LinkedList允许null元素，而ArrayDeque则不允许。在效率方面，ArrayDeque比LinkedList两端的添加和删除操作更高效。LinkedList的最佳使用方式是在迭代期间删除元素。不过LinkedList并不是迭代的理想结构，并且它比ArrayDeque占用更多的内存。此外，无论是LinkedList还是ArrayDeque均不支持多个线程的并发访问。

并发实现

LinkedBlockingDeque类是Deque接口的并发实现。和BlockingQueue相同，它在获取双端队列元素但是队列为空时，会阻塞等待队列中有元素再返回或超时返回；也支持在双端添加元素时，如果队列已满，那么等到队列可以放入新元素时再放入或超时返回。

6.包装实现

位于java.utils包中的Collections也是Java集合框架的一员，但它不是任意一种集合，而是一个包装类。它包含各种有关集合操作的静态方法，这个类不能实例化。它就像一个工具类，服务于集合框架。

这个类提供了很多的静态工厂方法，通过这些方法，可以提供具有某些特性的集合（例如空集合，同步集合，不可变集合等），或者包装指定的集合，使之具有某些特性。下面对这个类中的一些方法进行介绍。

同步包装器

同步包装器将自动同步（线程安全）特性添加到任意集合上。Collection，Set，List，Map，SortedSet和 SortedMap接口都有一个静态工厂方法。

public static <T> Collection<T> synchronizedCollection(Collection<T> c);

public static <T> Set<T> synchronizedSet(Set<T> s);

public static <T> List<T> synchronizedList(List<T> list);

public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m);

public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s);

public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m);

每一个方法都会返回指定集合的包装对象，这个集合是线程安全的。所有对于集合的操作都应该通过这个集合来完成，保证这一点最简单的方法就是不再保留对原集合的引用。

面对并发访问，用户必须在迭代时手动同步返回的集合。这是因为迭代是通过对集合的多次访问来完成的，而返回的集合虽然是同步的，但是它只能保证每一次对集合的操作都是线程安全的，而不能保证对于几个的多次操作也是安全的，因此这些操作必须组成一个单独的原子操作。以下是迭代通过包装器返回的同步集合的习惯用法：

Collection<Type> c = Collections.synchronizedCollection(myCollection);

synchronized(c) {

    for (Type e : c)

        foo(e);

}

有关synchronized关键字和多线程的内容会在之后的文章中进行介绍。

不可变包装器

不可变包装器可以使集合变为不可变集合，从而具有只读属性，任何会对集合进行改变的操作都会抛出一个UnsupportedOperationException。与同步包装器一样，六个核心接口中的每一个都有一个静态工厂方法：

public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c);

public static <T> Set<T> unmodifiableSet(Set<? extends T> s);

public static <T> List<T> unmodifiableList(List<? extends T> list);

public static <K,V> Map<K, V> unmodifiableMap(Map<? extends K, ? extends V> m);

public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<? extends T> s);

public static <K,V> SortedMap<K, V> unmodifiableSortedMap(SortedMap<K, ? extends V> m);

为了保证集合的绝对不变性，应该在获取集合的不可变包装后，不再保留对原集合的引用。

7.便捷实现

本节描述了几种便捷实现，当您不需要集合的全部功能时，它们比通用实现更方便，更高效。本节中的所有实现都是通过静态工厂方法提供的。

数组的列表视图

Arrays.asList方法可以接受一个数组并返回该数组的列表视图。对于集合的改变会应用在数组上，反之亦然。集合的大小就是数组的大小且不能更改，如果再集合视图上调用可能会修改集合大小的方法将会抛出一个UnsupportedOperationException。

这个实现的一般用途是作为数组和集合之间的桥梁。它允许我们将数组传递给需要Collection或List的方法。这种实现还有一个用途，如果我们需要固定大小的List，它比任何通用实现都要高效：

List<String> list = Arrays.asList(new String[size]);

指定元素的集合

下面的方法可以根据指定的元素来创建集合：

Arrays.asList(T... a)——返回包含指定的若干个元素的不可变List。

Collections.nCopies(int n, T o)——返回包含n个指定元素o的不可变List（这些元素都是o的引用）。

Collections.singleton(T o)——返回只包含该对象的不可变Set。

空集合或空映射

Collections类提供了返回空Set、List和Map的方法，它们分别是emptySet()、emptyList()和emptyMap()。