万字长文深入理解 java 中的集合 - 附 PDF 下载

程序那些事

关注

发布于: 2020 年 10 月 26 日

1. 前言

集合是用来存储多个数据的，除了基本类型之外，集合应该是 java 中最最常用的类型了。java 中的集合类型一般都集中在 java.util 包和 java.util.concurrent 包中。

其中 util 包中的集合类是基础的集合类，而 concurrent 包中的集合类是为并发特别准备的集合类。

集合类的父类有两个，一个是 java.util.Collection, 一个是 java.util.Map。

先看下 Collection 的定义：

public interface Collection<E> extends Iterable<E> {}

复制代码

Collection 继承自 Iterable 接口，表示所有的 Collection 都是可遍历的。并且 Collection 中可以保存一种数据类型。

再看下 Map 的定义：

public interface Map<K, V> {}

复制代码

可以看到 Map 是一个顶级的接口，里面可以保持两种数据类型，分别是 key 和 value。

其中 Collection 是 List,Set 和 Queue 的父类，这样就组成了集合的四大类型：List，Queue，Set 和 Map，接下来我们将会一一的进行讲解。

2. List

先看下 List 的定义：

public interface List<E> extends Collection<E> {}

复制代码

List 是一个接口，继承自 Collection，表示的是一个有序的链表，常用的 list 有 ArrayList,LinkedList 等等。

2.1 fail-safe fail-fast 知多少

我们在使用集合类的时候，通常会需要去遍历集合中的元素，并在遍历中对其中的元素进行处理。这时候我们就要用到 Iterator,经常写程序的朋友应该都知道，在 Iterator 遍历的过程中，是不能够修改集合数据的，否则就会抛出 ConcurrentModificationException。

因为 ConcurrentModificationException 的存在，就把 Iterator 分成了两类，Fail-fast 和 Fail-safe。

2.1.1 Fail-fast Iterator

Fail-fast 看名字就知道它的意思是失败的非常快。就是说如果在遍历的过程中修改了集合的结构，则就会立刻报错。

Fail-fast 通常在下面两种情况下抛出 ConcurrentModificationException：

单线程的环境中

如果在单线程的环境中，iterator 创建之后，如果不是通过 iterator 自身的 remove 方法，而是通过调用其他的方法修改了集合的结构，则会报错。

多线程的环境中

如果一个线程中创建了 iterator,而在另外一个线程中修改了集合的结构，则会报错。

我们先看一个 Fail-fast 的例子：

        Map<Integer,String> users = new HashMap<>();
        users.put(1, "jack");        users.put(2, "alice");        users.put(3, "jone");
        Iterator iterator1 = users.keySet().iterator();
        //not modify key, so no exception        while (iterator1.hasNext())        {            log.info("{}",users.get(iterator1.next()));            users.put(2, "mark");        }

复制代码

上面的例子中，我们构建了一个 Map，然后遍历该 map 的 key，在遍历过程中，我们修改了 map 的 value。

运行发现，程序完美执行，并没有报任何异常。

这是因为我们遍历的是 map 的 key，只要 map 的 key 没有被手动修改，就没有问题。

再看一个例子：

Map<Integer,String> users = new HashMap<>();
        users.put(1, "jack");        users.put(2, "alice");        users.put(3, "jone");
        Iterator iterator1 = users.keySet().iterator();
        Iterator iterator2 = users.keySet().iterator();        //modify key,get exception        while (iterator2.hasNext())        {            log.info("{}",users.get(iterator2.next()));            users.put(4, "mark");        }

复制代码

上面的例子中，我们在遍历 map 的 key 的同时，对 key 进行了修改。这种情况下就会报错。

2.1.2 Fail-fast 的原理

为什么修改了集合的结构就会报异常呢？

我们以 ArrayList 为例，来讲解下 Fail-fast 的原理。

在 AbstractList 中，定义了一个 modCount 变量：

protected transient int modCount = 0;

复制代码

在遍历的过程中都会去调用 checkForComodification()方法来对 modCount 进行检测：

      public E next() {            checkForComodification();            try {                int i = cursor;                E next = get(i);                lastRet = i;                cursor = i + 1;                return next;            } catch (IndexOutOfBoundsException e) {                checkForComodification();                throw new NoSuchElementException();            }        }

复制代码

如果检测的结果不是所预期的，就会报错：

        final void checkForComodification() {            if (modCount != expectedModCount)                throw new ConcurrentModificationException();        }

复制代码

在创建 Iterator 的时候会复制当前的 modCount 进行比较，而这个 modCount 在每次集合修改的时候都会进行变动，最终导致 Iterator 中的 modCount 和现有的 modCount 是不一致的。

        public void set(E e) {            if (lastRet < 0)                throw new IllegalStateException();            checkForComodification();
            try {                AbstractList.this.set(lastRet, e);                expectedModCount = modCount;            } catch (IndexOutOfBoundsException ex) {                throw new ConcurrentModificationException();            }        }

复制代码

注意，Fail-fast 并不保证所有的修改都会报错，我们不能够依赖 ConcurrentModificationException 来判断遍历中集合是否被修改。

2.1.3 Fail-safe Iterator

我们再来讲一下 Fail-safe，Fail-safe 的意思是在遍历的过程中，如果对集合进行修改是不会报错的。

Concurrent 包下面的类型都是 Fail-safe 的。看一个 ConcurrentHashMap 的例子：

Map<Integer,String> users = new ConcurrentHashMap<>();
        users.put(1, "jack");        users.put(2, "alice");        users.put(3, "jone");
        Iterator iterator1 = users.keySet().iterator();
        //not modify key, so no exception        while (iterator1.hasNext())        {            log.info("{}",users.get(iterator1.next()));            users.put(2, "mark");        }
        Iterator iterator2 = users.keySet().iterator();        //modify key,get exception        while (iterator2.hasNext())        {            log.info("{}",users.get(iterator2.next()));            users.put(4, "mark");        }

复制代码

上面的例子完美执行，不会报错。

2.2 Iterator to list 的三种方法

集合的变量少不了使用 Iterator，从集合 Iterator 非常简单，直接调用 Iterator 方法就可以了。

那么如何从 Iterator 反过来生成 List 呢？今天教大家三个方法。

2.2.1 使用 while

最简单最基本的逻辑就是使用 while 来遍历这个 Iterator，在遍历的过程中将 Iterator 中的元素添加到新建的 List 中去。

如下面的代码所示：

    @Test    public void useWhile(){        List<String> stringList= new ArrayList<>();        Iterator<String> stringIterator= Arrays.asList("a","b","c").iterator();        while(stringIterator.hasNext()){            stringList.add(stringIterator.next());        }        log.info("{}",stringList);    }

复制代码

2.2.2 使用 ForEachRemaining

Iterator 接口有个 default 方法：

    default void forEachRemaining(Consumer<? super E> action) {        Objects.requireNonNull(action);        while (hasNext())            action.accept(next());    }

复制代码

实际上这方法的底层就是封装了 while 循环，那么我们可以直接使用这个 ForEachRemaining 的方法：

    @Test    public void useForEachRemaining(){        List<String> stringList= new ArrayList<>();        Iterator<String> stringIterator= Arrays.asList("a","b","c").iterator();        stringIterator.forEachRemaining(stringList::add);        log.info("{}",stringList);    }

复制代码

2.2.3 使用 stream

我们知道构建 Stream 的时候，可以调用 StreamSupport 的 stream 方法：

public static <T> Stream<T> stream(Spliterator<T> spliterator, boolean parallel)

复制代码

该方法传入一个 spliterator 参数。而 Iterable 接口正好有一个 spliterator()的方法：

    default Spliterator<T> spliterator() {        return Spliterators.spliteratorUnknownSize(iterator(), 0);    }

复制代码

那么我们可以将 Iterator 转换为 Iterable，然后传入 stream。

仔细研究 Iterable 接口可以发现，Iterable 是一个 FunctionalInterface，只需要实现下面的接口就行了：

Iterator<T> iterator();

复制代码

利用 lambda 表达式，我们可以方便的将 Iterator 转换为 Iterable：

Iterator<String> stringIterator= Arrays.asList("a","b","c").iterator();        Iterable<String> stringIterable = () -> stringIterator;

复制代码

最后将其换行成为 List：

List<String> stringList= StreamSupport.stream(stringIterable.spliterator(),false).collect(Collectors.toList());        log.info("{}",stringList);

复制代码

2.3 asList 和 ArrayList 不得不说的故事

提到集合类，ArrayList 应该是用到的非常多的类了。这里的 ArrayList 是 java.util.ArrayList，通常我们怎么创建 ArrayList 呢？

2.3.1 创建 ArrayList

看下下面的例子：

List<String> names = new ArrayList<>();

复制代码

上面的方法创建了一个 ArrayList，如果我们需要向其中添加元素的话，需要再调用 add 方法。

通常我们会使用一种更加简洁的办法来创建 List：

    @Test    public void testAsList(){        List<String> names = Arrays.asList("alice", "bob", "jack");        names.add("mark");
    }

复制代码

看下 asList 方法的定义：

    public static <T> List<T> asList(T... a) {        return new ArrayList<>(a);    }

复制代码

很好，使用 Arrays.asList，我们可以方便的创建 ArrayList。

运行下上面的例子，奇怪的事情发生了，上面的例子居然抛出了 UnsupportedOperationException 异常。

java.lang.UnsupportedOperationException    at java.util.AbstractList.add(AbstractList.java:148)    at java.util.AbstractList.add(AbstractList.java:108)    at com.flydean.AsListUsage.testAsList(AsListUsage.java:18)

复制代码

2.3.2 UnsupportedOperationException

先讲一下这个异常，UnsupportedOperationException 是一个运行时异常，通常用在某些类中并没有实现接口的某些方法。

为什么上面的 ArrayList 调用 add 方法会抛异常呢？

2.3.3 asList

我们再来详细的看一下 Arrays.asList 方法中返回的 ArrayList：

private static class ArrayList<E> extends AbstractList<E>        implements RandomAccess, java.io.Serializable

复制代码

可以看到，Arrays.asList 返回的 ArrayList 是 Arrays 类中的一个内部类，并不是 java.util.ArrayList。

这个类继承自 AbstractList，在 AbstractList 中 add 方法是这样定义的：

    public void add(int index, E element) {        throw new UnsupportedOperationException();    }

复制代码

好了，我们的问题得到了解决。

2.3.4 转换

我们使用 Arrays.asList 得到 ArrayList 之后，能不能将其转换成为 java.util.ArrayList 呢？答案是肯定的。

我们看下下面的例子：

    @Test    public void testList(){        List<String> names = new ArrayList<>(Arrays.asList("alice", "bob", "jack"));        names.add("mark");    }

复制代码

上面的例子可以正常执行。

在 java 中有很多同样名字的类，我们需要弄清楚他们到底是什么，不要混淆了。

2.4 Copy ArrayList 的四种方式

ArrayList 是我们经常会用到的集合类，有时候我们需要拷贝一个 ArrayList，今天向大家介绍拷贝 ArrayList 常用的四种方式。

2.4.1 使用构造函数

ArrayList 有个构造函数，可以传入一个集合：

    public ArrayList(Collection<? extends E> c) {        elementData = c.toArray();        if ((size = elementData.length) != 0) {            // c.toArray might (incorrectly) not return Object[] (see 6260652)            if (elementData.getClass() != Object[].class)                elementData = Arrays.copyOf(elementData, size, Object[].class);        } else {            // replace with empty array.            this.elementData = EMPTY_ELEMENTDATA;        }    }

复制代码

上面的代码我们可以看出，底层实际上调用了 Arrays.copyOf 方法来对数组进行拷贝。这个拷贝调用了系统的 native arraycopy 方法，注意这里的拷贝是引用拷贝，而不是值的拷贝。这就意味着这如果拷贝之后对象的值发送了变化，源对象也会发生改变。

举个例子：

    @Test    public void withConstructor(){        List<String> stringList=new ArrayList<>(Arrays.asList("a","b","c"));        List<String> copyList = new ArrayList<>(stringList);        copyList.set(0,"e");        log.info("{}",stringList);        log.info("{}",copyList);
        List<CustBook> objectList=new ArrayList<>(Arrays.asList(new CustBook("a"),new CustBook("b"),new CustBook("c")));        List<CustBook> copyobjectList = new ArrayList<>(objectList);        copyobjectList.get(0).setName("e");        log.info("{}",objectList);        log.info("{}",copyobjectList);    }

复制代码

运行结果：

22:58:39.001 [main] INFO com.flydean.CopyList - [a, b, c]22:58:39.008 [main] INFO com.flydean.CopyList - [e, b, c]22:58:39.009 [main] INFO com.flydean.CopyList - [CustBook(name=e), CustBook(name=b), CustBook(name=c)]22:58:39.009 [main] INFO com.flydean.CopyList - [CustBook(name=e), CustBook(name=b), CustBook(name=c)]

复制代码

我们看到对象的改变实际上改变了拷贝的源。而 copyList.set(0,”e”)实际上创建了一个新的 String 对象，并把它赋值到 copyList 的 0 位置。

2.4.2 使用 addAll 方法

List 有一个 addAll 方法，我们可以使用这个方法来进行拷贝：

    @Test    public void withAddAll(){
        List<CustBook> objectList=new ArrayList<>(Arrays.asList(new CustBook("a"),new CustBook("b"),new CustBook("c")));        List<CustBook> copyobjectList = new ArrayList<>();        copyobjectList.addAll(objectList);        copyobjectList.get(0).setName("e");        log.info("{}",objectList);        log.info("{}",copyobjectList);    }

复制代码

同样的拷贝的是对象的引用。

2.4.3 使用 Collections.copy

同样的，使用 Collections.copy 也可以得到相同的效果，看下代码：

    @Test    public void withCopy(){        List<CustBook> objectList=new ArrayList<>(Arrays.asList(new CustBook("a"),new CustBook("b"),new CustBook("c")));        List<CustBook> copyobjectList = new ArrayList<>(Arrays.asList(new CustBook("d"),new CustBook("e"),new CustBook("f")));        Collections.copy(copyobjectList, objectList);        copyobjectList.get(0).setName("e");        log.info("{}",objectList);        log.info("{}",copyobjectList);    }

复制代码

2.4.4 使用 stream

我们也可以使用 java 8 引入的 stream 来实现：

    @Test    public void withStream(){
        List<CustBook> objectList=new ArrayList<>(Arrays.asList(new CustBook("a"),new CustBook("b"),new CustBook("c")));        List<CustBook> copyobjectList=objectList.stream().collect(Collectors.toList());        copyobjectList.get(0).setName("e");        log.info("{}",objectList);        log.info("{}",copyobjectList);
    }

复制代码

好了，四种方法讲完了，大家要注意四种方法都是引用拷贝，在使用的时候要小心。

3. Map

先看下 Map 的定义：

public interface Map<K, V> {}

复制代码

Map 是一个 key-value 对的集合，其中 key 不能够重复，但是 value 可以重复。常用的 Map 有 TreeMap 和 hashMap。

3.1 深入理解 HashMap 和 TreeMap 的区别

HashMap 和 TreeMap 是 Map 家族中非常常用的两个类，两个类在使用上和本质上有什么区别呢？本文将从这两个方面进行深入的探讨，希望能揭露其本质。

3.1.1 HashMap 和 TreeMap 本质区别

先看 HashMap 的定义：

public class HashMap<K,V> extends AbstractMap<K,V>    implements Map<K,V>, Cloneable, Serializable

复制代码

再看 TreeMap 的定义：

public class TreeMap<K,V>    extends AbstractMap<K,V>    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

复制代码

从类的定义来看，HashMap 和 TreeMap 都继承自 AbstractMap，不同的是 HashMap 实现的是 Map 接口，而 TreeMap 实现的是 NavigableMap 接口。NavigableMap 是 SortedMap 的一种，实现了对 Map 中 key 的排序。

这样两者的第一个区别就出来了，TreeMap 是排序的而 HashMap 不是。

再看看 HashMap 和 TreeMap 的构造函数的区别。

public HashMap(int initialCapacity, float loadFactor)

复制代码

HashMap 除了默认的无参构造函数之外，还可以接受两个参数 initialCapacity 和 loadFactor。

HashMap 的底层结构是 Node 的数组：

transient Node<K,V>[] table

复制代码

initialCapacity 就是这个 table 的初始容量。如果大家不传 initialCapacity，HashMap 提供了一个默认的值：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

复制代码

当 HashMap 中存储的数据过多的时候，table 数组就会被装满，这时候就需要扩容，HashMap 的扩容是以 2 的倍数来进行的。而 loadFactor 就指定了什么时候需要进行扩容操作。默认的 loadFactor 是 0.75。

static final float DEFAULT_LOAD_FACTOR = 0.75f;

复制代码

再来看几个非常有趣的变量：

static final int TREEIFY_THRESHOLD = 8;static final int UNTREEIFY_THRESHOLD = 6;static final int MIN_TREEIFY_CAPACITY = 64;

复制代码

上面的三个变量有什么用呢？在 java 8 之前，HashMap 解决 hashcode 冲突的方法是采用链表的形式，为了提升效率，java 8 将其转成了 TreeNode。什么时候会发送这个转换呢？

这时候就要看这两个变量 TREEIFY_THRESHOLD 和 UNTREEIFY_THRESHOLD。

有的同学可能发现了，TREEIFY_THRESHOLD 为什么比 UNTREEIFY_THRESHOLD 大 2 呢？其实这个问题我也不知道，但是你看源代码的话，用到 UNTREEIFY_THRESHOLD 时候，都用的是<=,而用到 TREEIFY_THRESHOLD 的时候，都用的是>= TREEIFY_THRESHOLD – 1，所以这两个变量在本质上是一样的。

MIN_TREEIFY_CAPACITY 表示的是如果 table 转换 TreeNode 的最小容量，只有 capacity >= MIN_TREEIFY_CAPACITY 的时候才允许 TreeNode 的转换。

TreeMap 和 HashMap 不同的是，TreeMap 的底层是一个 Entry：

private transient Entry<K,V> root

复制代码

他的实现是一个红黑树，方便用来遍历和搜索。

TreeMap 的构造函数可以传入一个 Comparator，实现自定义的比较方法。

public TreeMap(Comparator<? super K> comparator) {        this.comparator = comparator;    }

复制代码

如果不提供自定义的比较方法，则使用的是 key 的 natural order。

3.1.2 排序区别

我们讲完两者的本质之后，现在举例说明，先看下两者对排序的区别：

    @Test    public void withOrder(){        Map<String, String> books = new HashMap<>();        books.put("bob", "books");        books.put("c", "concurrent");        books.put("a", "a lock");        log.info("{}",books);    }

复制代码

    @Test    public void withOrder(){        Map<String, String> books = new TreeMap<>();        books.put("bob", "books");        books.put("c", "concurrent");        books.put("a", "a lock");        log.info("{}",books);    }

复制代码

同样的代码，一个使用了 HashMap，一个使用了 TreeMap，我们会发现 TreeMap 输出的结果是排好序的，而 HashMap 的输出结果是不定的。

3.1.3 Null 值的区别

HashMap 可以允许一个 null key 和多个 null value。而 TreeMap 不允许 null key，但是可以允许多个 null value。

    @Test    public void withNull() {        Map<String, String> hashmap = new HashMap<>();        hashmap.put(null, null);        log.info("{}",hashmap);    }

复制代码

    @Test    public void withNull() {        Map<String, String> hashmap = new TreeMap<>();        hashmap.put(null, null);        log.info("{}",hashmap);    }

复制代码

HashMap 会报出： NullPointerException。

3.1.4 性能区别

HashMap 的底层是 Array，所以 HashMap 在添加，查找，删除等方法上面速度会非常快。而 TreeMap 的底层是一个 Tree 结构，所以速度会比较慢。

另外 HashMap 因为要保存一个 Array，所以会造成空间的浪费，而 TreeMap 只保存要保持的节点，所以占用的空间比较小。

HashMap 如果出现 hash 冲突的话，效率会变差，不过在 java 8 进行 TreeNode 转换之后，效率有很大的提升。

TreeMap 在添加和删除节点的时候会进行重排序，会对性能有所影响。

3.1.5 共同点

两者都不允许 duplicate key,两者都不是线程安全的。

3.2 深入理解 HashMap 和 LinkedHashMap 的区别

我们知道 HashMap 的变量顺序是不可预测的，这意味着便利的输出顺序并不一定和 HashMap 的插入顺序是一致的。这个特性通常会对我们的工作造成一定的困扰。为了实现这个功能，我们可以使用 LinkedHashMap。

3.2.1 LinkedHashMap 详解

先看下 LinkedHashMap 的定义：

public class LinkedHashMap<K,V>    extends HashMap<K,V>    implements Map<K,V>

复制代码

LinkedHashMap 继承自 HashMap，所以 HashMap 的所有功能在 LinkedHashMap 都可以用。

LinkedHashMap 和 HashMap 的区别就是新创建了一个 Entry:

    static class Entry<K,V> extends HashMap.Node<K,V> {        Entry<K,V> before, after;        Entry(int hash, K key, V value, Node<K,V> next) {            super(hash, key, value, next);        }    }

复制代码

这个 Entry 继承自 HashMap.Node，多了一个 before，after 来实现 Node 之间的连接。

通过这个新创建的 Entry，就可以保证遍历的顺序和插入的顺序一致。

3.2.2 插入

下面看一个 LinkedHashMap 插入的例子：

    @Test    public void insertOrder(){        LinkedHashMap<String, String> map = new LinkedHashMap<>();        map.put("ddd","desk");        map.put("aaa","ask");        map.put("ccc","check");        map.keySet().forEach(System.out::println);    }

复制代码

输出结果：

dddaaaccc

复制代码

可以看到输出结果和插入结果是一致的。

3.2.3 访问

除了遍历的顺序，LinkedHashMap 还有一个非常有特色的访问顺序。

我们再看一个 LinkedHashMap 的构造函数：

    public LinkedHashMap(int initialCapacity,                         float loadFactor,                         boolean accessOrder) {        super(initialCapacity, loadFactor);        this.accessOrder = accessOrder;    }

复制代码

前面的两个参数 initialCapacity，loadFactor 我们之前已经讲过了，现在看最后一个参数 accessOrder。

当 accessOrder 设置成为 true 的时候，就开启了 access-order。

access order 的意思是，将对象安装最老访问到最新访问的顺序排序。我们看个例子：

    @Test    public void accessOrder(){        LinkedHashMap<String, String> map = new LinkedHashMap<>(16, .75f, true);        map.put("ddd","desk");        map.put("aaa","ask");        map.put("ccc","check");        map.keySet().forEach(System.out::println);        map.get("aaa");        map.keySet().forEach(System.out::println);    }

复制代码

输出结果：

dddaaacccdddcccaaa

复制代码

我们看到，因为访问了一次“aaa“，从而导致遍历的时候排到了最后。

3.2.4 removeEldestEntry

最后我们看一下 LinkedHashMap 的一个特别的功能 removeEldestEntry。这个方法是干什么的呢？

通过重新 removeEldestEntry 方法，可以让 LinkedHashMap 保存特定数目的 Entry,通常用在 LinkedHashMap 用作缓存的情况。

removeEldestEntry 将会删除最老的 Entry，保留最新的。

ublic class CustLinkedHashMap<K, V> extends LinkedHashMap<K, V> {
    private static final int MAX_ENTRIES = 10;
    public CustLinkedHashMap(            int initialCapacity, float loadFactor, boolean accessOrder) {        super(initialCapacity, loadFactor, accessOrder);    }
    @Override    protected boolean removeEldestEntry(Map.Entry eldest) {        return size() > MAX_ENTRIES;    }}

复制代码

看上面的一个自定义的例子，上面的例子我们创建了一个保留 10 个 Entry 节点的 LinkedHashMap。

3.2.5 总结

LinkedHashMap 继承自 HashMap，同时提供了两个非常有用的功能。

3.3 EnumMap 和 EnumSet

一般来说我们会选择使用 HashMap 来存储 key-value 格式的数据，考虑这样的特殊情况，一个 HashMap 的 key 都来自于一个 Enum 类，这样的情况则可以考虑使用本文要讲的 EnumMap。

3.3.1 EnumMap

先看一下 EnumMap 的定义和 HashMap 定义的比较：

public class EnumMap<K extends Enum<K>, V> extends AbstractMap<K, V>    implements java.io.Serializable, Cloneable

复制代码

public class HashMap<K,V> extends AbstractMap<K,V>    implements Map<K,V>, Cloneable, Serializable

复制代码

我们可以看到 EnumMap 几乎和 HashMap 是一样的，区别在于 EnumMap 的 key 是一个 Enum。

下面看一个简单的使用的例子：

先定义一个 Enum：

public enum Types {    RED, GREEN, BLACK, YELLO}

复制代码

再看下怎么使用 EnumMap：

    @Test    public void useEnumMap(){        EnumMap<Types, String> activityMap = new EnumMap<>(Types.class);        activityMap.put(Types.BLACK,"black");        activityMap.put(Types.GREEN,"green");        activityMap.put(Types.RED,"red");    }

复制代码

其他的操作其实和 hashMap 是类似的，我们这里就不多讲了。

3.3.2 什么时候使用 EnumMap

因为在 EnumMap 中，所有的 key 的可能值在创建的时候已经知道了，所以使用 EnumMap 和 hashMap 相比，可以提升效率。

同时，因为 key 比较简单，所以 EnumMap 在实现中，也不需要像 HashMap 那样考虑一些复杂的情况。

3.3.3 EnumSet

跟 EnumMap 很类似，EnumSet 是一个 set，然后 set 中的元素都是某个 Enum 类型。

EnumSet 是一个抽象类，要创建 EnumSet 类可以使用 EnumSet 提供的两个静态方法，noneOf 和 allOf。

先看一个 noneOf：

    public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) {        Enum<?>[] universe = getUniverse(elementType);        if (universe == null)            throw new ClassCastException(elementType + " not an enum");
        if (universe.length <= 64)            return new RegularEnumSet<>(elementType, universe);        else            return new JumboEnumSet<>(elementType, universe);    }

复制代码

noneOf 传入一个 Enum 类，返回一个空的 Enum 类型的 EnumSet。

从上面的代码我们可以看到 EnumSet 有两个实现，长度大于 64 的时候使用 JumboEnumSet，小有 64 的时候使用 RegularEnumSet。

注意，JumboEnumSet 和 RegularEnumSet 不建议直接使用，他是内部使用的类。

再看一下 allOf：

public static <E extends Enum<E>> EnumSet<E> allOf(Class<E> elementType) {        EnumSet<E> result = noneOf(elementType);        result.addAll();        return result;    }

复制代码

allOf 很简单，先调用 noneOf 创建空的 set，然后调用 addAll 方法将所有的元素添加进去。

3.3.4 总结

EnumMap 和 EnumSet 对特定的 Enum 对象做了优化，可以在合适的情况下使用。

3.4 SkipList 和 ConcurrentSkipListMap 的实现

一开始听说 SkipList 我是一脸懵逼的，啥？还有 SkipList？这个是什么玩意。

后面经过我的不断搜索和学习，终于明白了 SkipList 原来是一种数据结构，而 java 中的 ConcurrentSkipListMap 和 ConcurrentSkipListSet 就是这种结构的实现。

接下来就让我们一步一步的揭开 SkipList 和 ConcurrentSkipListMap 的面纱吧。

3.4.1 SkipList

先看下维基百科中 SkipList 的定义：

SkipList 是一种层级结构。最底层的是排序过的最原始的 linked list。

往上是一层一层的层级结构，每个底层节点按照一定的概率出现在上一层 list 中。这个概率叫做 p，通常 p 取 1/2 或者 1/4。

先设定一个函数 f，可以随机产生 0 和 1 这两个数，并且这两个数出现的几率是一样的，那么这时候的 p 就是 1/2。

对每个节点，我们这样操作：

我们运行一次 f，当 f=1 时，我们将该节点插入到上层 layer 的 list 中去。当 f=0 时，不插入。

举个例子，上图中的 list 中有 10 个排序过的节点，第一个节点默认每层都有。对于第二个节点，运行 f=0，不插入。对于第三个节点，运行 f=1,将第三个节点插入 layer 1，以此类推，最后得到的 layer 1 list 中的节点有：1，3，4，6，9。

然后我们再继续往上构建 layer。最终得到上图的 SkipList。

通过使用 SkipList，我们构建了多个 List，包含不同的排序过的节点，从而提升 List 的查找效率。

我们通过下图能有一个更清晰的认识：

每次的查找都是从最顶层开始，因为最顶层的节点数最少，如果要查找的节点在 list 中的两个节点中间，则向下移一层继续查找，最终找到最底层要插入的位置，插入节点，然后再次调用概率函数 f，决定是否向上复制节点。

其本质上相当于二分法查找，其查找的时间复杂度是 O(logn)。

3.4.2 ConcurrentSkipListMap

ConcurrentSkipListMap 是一个并发的 SkipList，那么它具有两个特点，SkipList 和 concurrent。我们分别来讲解。

SkipList 的实现

上面讲解了 SkipList 的数据结构，接下来看下 ConcurrentSkipListMap 是怎么实现这个 skipList 的：

ConcurrentSkipListMap 中有三种结构，base nodes,Head nodes 和 index nodes。

base nodes 组成了有序的链表结构，是 ConcurrentSkipListMap 的最底层实现。

    static final class Node<K,V> {        final K key;        volatile Object value;        volatile Node<K,V> next;
        /**         * Creates a new regular node.         */        Node(K key, Object value, Node<K,V> next) {            this.key = key;            this.value = value;            this.next = next;        }    }

复制代码

上面可以看到每个 Node 都是一个 k，v 的 entry，并且其有一个 next 指向下一个节点。

index nodes 是构建 SkipList 上层结构的基本节点：

    static class Index<K,V> {        final Node<K,V> node;        final Index<K,V> down;        volatile Index<K,V> right;
        /**         * Creates index node with given values.         */        Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {            this.node = node;            this.down = down;            this.right = right;        }    }

复制代码

从上面的构造我们可以看到，Index 节点包含了 Node 节点，除此之外，Index 还有两个指针，一个指向同一个 layer 的下一个节点，一个指向下一层 layer 的节点。

这样的结构可以方便遍历的实现。

最后看一下 HeadIndex，HeadIndex 代表的是 Head 节点：

    static final class HeadIndex<K,V> extends Index<K,V> {        final int level;        HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {            super(node, down, right);            this.level = level;        }    }

复制代码

HeadIndex 和 Index 很类似，只不过多了一个 level 字段，表示所在的层级。

在 ConcurrentSkipListMap 初始化的时候，会初始化 HeadIndex：

head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),null, null, 1);

复制代码

我们可以看到 HeadIndex 中的 Node 是 key=null，value=BASE_HEADER 的虚拟节点。初始的 level=1。

concurrent 的实现

接下来，我们再看一下并发是怎么实现的：

基本上并发类都是通过 UNSAFE.compareAndSwapObject 来实现的，ConcurrentSkipListMap 也不例外。

假如我们有三个节点，b-n-f。现在需要删除节点 n。

第一步，使用 CAS 将 n 的 valu 的值从 non-null 设置为 null。这个时候，任何外部的操作都会认为这个节点是不存在的。但是那些内部的插入或者删除操作还是会继续修改 n 的 next 指针。

第二步，使用 CAS 将 n 的 next 指针指向一个新的 marker 节点，从这个时候开始，n 的 next 指针将不会指向任何其他的节点。

我们看下 marker 节点的定义：

        Node(Node<K,V> next) {            this.key = null;            this.value = this;            this.next = next;        }

复制代码

我们可以看到 marker 节点实际上是一个 key 为 null，value 是自己的节点。

第三步，使用 CAS 将 b 的 next 指针指向 f。从这一步起，n 节点不会再被其他的程序访问，这意味着 n 可以被垃圾回收了。

我们思考一下为什么要插入一个 marker 节点，这是因为我们在删除的时候，需要告诉所有的线程，节点 n 准备被删除了，因为 n 本来就指向 f 节点，这个时候需要一个中间节点来表示这个准备删除的状态。

4. Queue

先看下 Queue 的定义：

public interface Queue<E> extends Collection<E> {}

复制代码

Queue 表示的是队列，其特点就是先进先出。常用的 Queue 有 DelayQueue，BlockingQueue 等等。

4.1 java 中的 Queue 家族

java 中 Collection 集合有三大家族 List，Set 和 Queue。当然 Map 也算是一种集合类，但 Map 并不继承 Collection 接口。

List，Set 在我们的工作中会经常使用，通常用来存储结果数据，而 Queue 由于它的特殊性，通常用在生产者消费者模式中。

现在很火的消息中间件比如：Rabbit MQ 等都是 Queue 这种数据结构的展开。

今天这篇文章将带大家进入 Queue 家族。

4.1.1 Queue 接口

先看下 Queue 的继承关系和其中定义的方法：

Queue 继承自 Collection，Collection 继承自 Iterable。

Queue 有三类主要的方法，我们用个表格来看一下他们的区别：

方法类型方法名称方法名称区别 Insertaddoffer 两个方法都表示向 Queue 中添加某个元素，不同之处在于添加失败的情况，add 只会返回 true，如果添加失败，会抛出异常。offer 在添加失败的时候会返回 false。所以对那些有固定长度的 Queue，优先使用 offer 方法。Removeremovepoll 如果 Queue 是空的情况下，remove 会抛出异常，而 poll 会返回 null。Examineelementpeek 获取 Queue 头部的元素，但不从 Queue 中删除。两者的区别还是在于 Queue 为空的情况下，element 会抛出异常，而 peek 返回 null。

注意，因为对 poll 和 peek 来说 null 是有特殊含义的，所以一般来说 Queue 中禁止插入 null，但是在实现中还是有一些类允许插入 null 比如 LinkedList。
尽管如此，我们在使用中还是要避免插入 null 元素。

4.1.2 Queue 的分类

一般来说 Queue 可以分为 BlockingQueue，Deque 和 TransferQueue 三种。

BlockingQueue

BlockingQueue 是 Queue 的一种实现，它提供了两种额外的功能：

当当前 Queue 是空的时候，从 BlockingQueue 中获取元素的操作会被阻塞。
当当前 Queue 达到最大容量的时候，插入 BlockingQueue 的操作会被阻塞。

BlockingQueue 的操作可以分为下面四类：

操作类型 Throws exceptionSpecial valueBlocksTimes outInsertadd(e)offer(e)put(e)offer(e, time, unit)Removeremove()poll()take()poll(time, unit)Examineelement()peek()not applicablenot applicable

第一类是会抛出异常的操作，当遇到插入失败，队列为空的时候抛出异常。

第二类是不会抛出异常的操作。

第三类是会 Block 的操作。当 Queue 为空或者达到最大容量的时候。

第四类是 time out 的操作，在给定的时间里会 Block，超时会直接返回。

BlockingQueue 是线程安全的 Queue,可以在生产者消费者模式的多线程中使用，如下所示：

 class Producer implements Runnable {   private final BlockingQueue queue;   Producer(BlockingQueue q) { queue = q; }   public void run() {     try {       while (true) { queue.put(produce()); }     } catch (InterruptedException ex) { ... handle ...}   }   Object produce() { ... } }
 class Consumer implements Runnable {   private final BlockingQueue queue;   Consumer(BlockingQueue q) { queue = q; }   public void run() {     try {       while (true) { consume(queue.take()); }     } catch (InterruptedException ex) { ... handle ...}   }   void consume(Object x) { ... } }
 class Setup {   void main() {     BlockingQueue q = new SomeQueueImplementation();     Producer p = new Producer(q);     Consumer c1 = new Consumer(q);     Consumer c2 = new Consumer(q);     new Thread(p).start();     new Thread(c1).start();     new Thread(c2).start();   } }

复制代码

最后，在一个线程中向 BlockQueue 中插入元素之前的操作 happens-before 另外一个线程中从 BlockQueue 中删除或者获取的操作。

Deque

Deque 是 Queue 的子类，它代表 double ended queue，也就是说可以从 Queue 的头部或者尾部插入和删除元素。

同样的，我们也可以将 Deque 的方法用下面的表格来表示，Deque 的方法可以分为对头部的操作和对尾部的操作：

方法类型 Throws exceptionSpecial valueThrows exceptionSpecial valueInsertaddFirst(e)offerFirst(e)addLast(e)offerLast(e)RemoveremoveFirst()pollFirst()removeLast()pollLast()ExaminegetFirst()peekFirst()getLast()peekLast()

和 Queue 的方法描述基本一致，这里就不多讲了。

当 Deque 以 FIFO (First-In-First-Out)的方法处理元素的时候，Deque 就相当于一个 Queue。

当 Deque 以 LIFO (Last-In-First-Out)的方式处理元素的时候，Deque 就相当于一个 Stack。

TransferQueue

TransferQueue 继承自 BlockingQueue，为什么叫 Transfer 呢？因为 TransferQueue 提供了一个 transfer 的方法，生产者可以调用这个 transfer 方法，从而等待消费者调用 take 或者 poll 方法从 Queue 中拿取数据。

还提供了非阻塞和 timeout 版本的 tryTransfer 方法以供使用。

我们举个 TransferQueue 实现的生产者消费者的问题。

先定义一个生产者：

@Slf4j@Data@AllArgsConstructorclass Producer implements Runnable {    private TransferQueue<String> transferQueue;
    private String name;
    private Integer messageCount;
    public static final AtomicInteger messageProduced = new AtomicInteger();
    @Override    public void run() {        for (int i = 0; i < messageCount; i++) {            try {                boolean added = transferQueue.tryTransfer( "第"+i+"个", 2000, TimeUnit.MILLISECONDS);                log.info("transfered {} 是否成功: {}","第"+i+"个",added);                if(added){                    messageProduced.incrementAndGet();                }            } catch (InterruptedException e) {                log.error(e.getMessage(),e);            }        }        log.info("total transfered {}",messageProduced.get());    }}

复制代码

在生产者的 run 方法中，我们调用了 tryTransfer 方法，等待 2 秒钟，如果没成功则直接返回。

再定义一个消费者：

@Slf4j@Data@AllArgsConstructorpublic class Consumer implements Runnable {
    private TransferQueue<String> transferQueue;
    private String name;
    private int messageCount;
    public static final AtomicInteger messageConsumed = new AtomicInteger();
    @Override    public void run() {        for (int i = 0; i < messageCount; i++) {            try {                String element = transferQueue.take();                log.info("take {}",element );                messageConsumed.incrementAndGet();                Thread.sleep(500);            } catch (InterruptedException e) {                log.error(e.getMessage(),e);            }        }        log.info("total consumed {}",messageConsumed.get());    }
}

复制代码

在 run 方法中，调用了 transferQueue.take 方法来取消息。

下面先看一下一个生产者，零个消费者的情况：

    @Test    public void testOneProduceZeroConsumer() throws InterruptedException {
        TransferQueue<String> transferQueue = new LinkedTransferQueue<>();        ExecutorService exService = Executors.newFixedThreadPool(10);        Producer producer = new Producer(transferQueue, "ProducerOne", 5);
        exService.execute(producer);
        exService.awaitTermination(50000, TimeUnit.MILLISECONDS);        exService.shutdown();    }

复制代码

输出结果：

[pool-1-thread-1] INFO com.flydean.Producer - transfered 第0个 是否成功: false[pool-1-thread-1] INFO com.flydean.Producer - transfered 第1个 是否成功: false[pool-1-thread-1] INFO com.flydean.Producer - transfered 第2个 是否成功: false[pool-1-thread-1] INFO com.flydean.Producer - transfered 第3个 是否成功: false[pool-1-thread-1] INFO com.flydean.Producer - transfered 第4个 是否成功: false[pool-1-thread-1] INFO com.flydean.Producer - total transfered 0

复制代码

可以看到，因为没有消费者，所以消息并没有发送成功。

再看下一个有消费者的情况：

    @Test    public void testOneProduceOneConsumer() throws InterruptedException {
        TransferQueue<String> transferQueue = new LinkedTransferQueue<>();        ExecutorService exService = Executors.newFixedThreadPool(10);        Producer producer = new Producer(transferQueue, "ProducerOne", 2);        Consumer consumer = new Consumer(transferQueue, "ConsumerOne", 2);
        exService.execute(producer);        exService.execute(consumer);
        exService.awaitTermination(50000, TimeUnit.MILLISECONDS);        exService.shutdown();    }

复制代码

输出结果：

[pool-1-thread-2] INFO com.flydean.Consumer - take 第0个[pool-1-thread-1] INFO com.flydean.Producer - transfered 第0个 是否成功: true[pool-1-thread-2] INFO com.flydean.Consumer - take 第1个[pool-1-thread-1] INFO com.flydean.Producer - transfered 第1个 是否成功: true[pool-1-thread-1] INFO com.flydean.Producer - total transfered 2[pool-1-thread-2] INFO com.flydean.Consumer - total consumed 2

复制代码

可以看到 Producer 和 Consumer 是一个一个来生产和消费的。

4.2 PriorityQueue 和 PriorityBlockingQueue

Queue 一般来说都是 FIFO 的，当然之前我们也介绍过 Deque 可以做为栈来使用。今天我们介绍一种 PriorityQueue，可以安装对象的自然顺序或者自定义顺序在 Queue 中进行排序。

4.2.1 PriorityQueue

先看 PriorityQueue，这个 Queue 继承自 AbstractQueue，是非线程安全的。

PriorityQueue 的容量是 unbounded 的，也就是说它没有容量大小的限制，所以你可以无限添加元素，如果添加的太多，最后会报 OutOfMemoryError 异常。

这里教大家一个识别的技能，只要集合类中带有 CAPACITY 的，其底层实现大部分都是数组，因为只有数组才有 capacity，当然也有例外，比如 LinkedBlockingDeque。

只要集合类中带有 comparator 的，那么这个集合一定是个有序集合。

我们看下 PriorityQueue：

private static final int DEFAULT_INITIAL_CAPACITY = 11; private final Comparator<? super E> comparator;

复制代码

定义了初始 Capacity 和 comparator，那么 PriorityQueue 的底层实现就是 Array，并且它是一个有序集合。

有序集合默认情况下是按照 natural ordering 来排序的，如果你传入了 Comparator,则会按照你指定的方式进行排序，我们看两个排序的例子：

@Slf4jpublic class PriorityQueueUsage {
    @Test    public void usePriorityQueue(){        PriorityQueue<Integer> integerQueue = new PriorityQueue<>();
        integerQueue.add(1);        integerQueue.add(3);        integerQueue.add(2);
        int first = integerQueue.poll();        int second = integerQueue.poll();        int third = integerQueue.poll();
        log.info("{},{},{}",first,second,third);    }
    @Test    public void usePriorityQueueWithComparator(){        PriorityQueue<Integer> integerQueue = new PriorityQueue<>((a,b)-> b-a);        integerQueue.add(1);        integerQueue.add(3);        integerQueue.add(2);
        int first = integerQueue.poll();        int second = integerQueue.poll();        int third = integerQueue.poll();
        log.info("{},{},{}",first,second,third);    }}

复制代码

默认情况下会按照升序排列，第二个例子中我们传入了一个逆序的 Comparator，则会按照逆序排列。

4.2.2 PriorityBlockingQueue

PriorityBlockingQueue 是一个 BlockingQueue，所以它是线程安全的。

我们考虑这样一个问题，如果两个对象的 natural ordering 或者 Comparator 的顺序是一样的话，两个对象的顺序还是固定的吗？

出现这种情况，默认顺序是不能确定的，但是我们可以这样封装对象，让对象可以在排序顺序一致的情况下，再按照创建顺序先进先出 FIFO 的二次排序：

public class FIFOEntry<E extends Comparable<? super E>>        implements Comparable<FIFOEntry<E>> {    static final AtomicLong seq = new AtomicLong(0);    final long seqNum;    final E entry;    public FIFOEntry(E entry) {        seqNum = seq.getAndIncrement();        this.entry = entry;    }    public E getEntry() { return entry; }    public int compareTo(FIFOEntry<E> other) {        int res = entry.compareTo(other.entry);        if (res == 0 && other.entry != this.entry)            res = (seqNum < other.seqNum ? -1 : 1);        return res;    }}

复制代码

上面的例子中，先比较两个 Entry 的 natural ordering，如果一致的话，再按照 seqNum 进行排序。

4.3 SynchronousQueue 详解

SynchronousQueue 是 BlockingQueue 的一种，所以 SynchronousQueue 是线程安全的。SynchronousQueue 和其他的 BlockingQueue 不同的是 SynchronousQueue 的 capacity 是 0。即 SynchronousQueue 不存储任何元素。

也就是说 SynchronousQueue 的每一次 insert 操作，必须等待其他线性的 remove 操作。而每一个 remove 操作也必须等待其他线程的 insert 操作。

这种特性可以让我们想起了 Exchanger。和 Exchanger 不同的是，使用 SynchronousQueue 可以在两个线程中传递同一个对象。一个线程放对象，另外一个线程取对象。

4.3.1 举例说明

我们举一个多线程中传递对象的例子。还是举生产者消费者的例子，在生产者中我们创建一个对象，在消费者中我们取出这个对象。先看一下用 CountDownLatch 该怎么做：

    @Test    public void useCountdownLatch() throws InterruptedException {        ExecutorService executor = Executors.newFixedThreadPool(2);        AtomicReference<Object> atomicReference= new AtomicReference<>();        CountDownLatch countDownLatch = new CountDownLatch(1);
        Runnable producer = () -> {            Object object=new Object();            atomicReference.set(object);            log.info("produced {}",object);            countDownLatch.countDown();        };
        Runnable consumer = () -> {            try {                countDownLatch.await();                Object object = atomicReference.get();                log.info("consumed {}",object);            } catch (InterruptedException ex) {                log.error(ex.getMessage(),ex);            }        };
        executor.submit(producer);        executor.submit(consumer);
        executor.awaitTermination(50000, TimeUnit.MILLISECONDS);        executor.shutdown();    }

复制代码

上例中，我们使用 AtomicReference 来存储要传递的对象，并且定义了一个型号量为 1 的 CountDownLatch。

在 producer 中，我们存储对象，并且 countDown。

在 consumer 中，我们 await,然后取出对象。

输出结果：

[pool-1-thread-1] INFO com.flydean.SynchronousQueueUsage - produced java.lang.Object@683d1b4b[pool-1-thread-2] INFO com.flydean.SynchronousQueueUsage - consumed java.lang.Object@683d1b4b

复制代码

可以看到传入和输出了同一个对象。

上面的例子我们也可以用 SynchronousQueue 来改写：

    @Test    public void useSynchronousQueue() throws InterruptedException {        ExecutorService executor = Executors.newFixedThreadPool(2);        SynchronousQueue<Object> synchronousQueue=new SynchronousQueue<>();
        Runnable producer = () -> {            Object object=new Object();            try {                synchronousQueue.put(object);            } catch (InterruptedException ex) {                log.error(ex.getMessage(),ex);            }            log.info("produced {}",object);        };
        Runnable consumer = () -> {            try {                Object object = synchronousQueue.take();                log.info("consumed {}",object);            } catch (InterruptedException ex) {                log.error(ex.getMessage(),ex);            }        };
        executor.submit(producer);        executor.submit(consumer);
        executor.awaitTermination(50000, TimeUnit.MILLISECONDS);        executor.shutdown();    }

复制代码

上面的例子中，如果我们使用 synchronousQueue，则可以不用手动同步，也不需要额外的存储。

如果我们需要在代码中用到这种线程中传递对象的情况，那么使用 synchronousQueue 吧。

4.4 DelayQueue 的使用

今天给大家介绍一下 DelayQueue,DelayQueue 是 BlockingQueue 的一种，所以它是线程安全的，DelayQueue 的特点就是插入 Queue 中的数据可以按照自定义的 delay 时间进行排序。只有 delay 时间小于 0 的元素才能够被取出。

4.4.1 DelayQueue

先看一下 DelayQueue 的定义：

public class DelayQueue<E extends Delayed> extends AbstractQueue<E>    implements BlockingQueue<E>

复制代码

从定义可以看到，DelayQueue 中存入的对象都必须是 Delayed 的子类。

Delayed 继承自 Comparable，并且需要实现一个 getDelay 的方法。

为什么这样设计呢？

因为 DelayQueue 的底层存储是一个 PriorityQueue，在之前的文章中我们讲过了，PriorityQueue 是一个可排序的 Queue，其中的元素必须实现 Comparable 方法。而 getDelay 方法则用来判断排序后的元素是否可以从 Queue 中取出。

4.4.2 DelayQueue 的应用

DelayQueue 一般用于生产者消费者模式，我们下面举一个具体的例子。

首先要使用 DelayQueue，必须自定义一个 Delayed 对象：

@Datapublic class DelayedUser implements Delayed {    private String name;    private long avaibleTime;
    public DelayedUser(String name, long delayTime){        this.name=name;        //avaibleTime = 当前时间+ delayTime        this.avaibleTime=delayTime + System.currentTimeMillis();
    }
    @Override    public long getDelay(TimeUnit unit) {        //判断avaibleTime是否大于当前系统时间，并将结果转换成MILLISECONDS        long diffTime= avaibleTime- System.currentTimeMillis();        return unit.convert(diffTime,TimeUnit.MILLISECONDS);    }
    @Override    public int compareTo(Delayed o) {        //compareTo用在DelayedUser的排序        return (int)(this.avaibleTime - ((DelayedUser) o).getAvaibleTime());    }}

复制代码

上面的对象中，我们需要实现 getDelay 和 compareTo 方法。

接下来我们创建一个生产者：

@Slf4j@Data@AllArgsConstructorclass DelayedQueueProducer implements Runnable {    private DelayQueue<DelayedUser> delayQueue;
    private Integer messageCount;
    private long delayedTime;
    @Override    public void run() {        for (int i = 0; i < messageCount; i++) {            try {                DelayedUser delayedUser = new DelayedUser(                        new Random().nextInt(1000)+"", delayedTime);                log.info("put delayedUser {}",delayedUser);                delayQueue.put(delayedUser);                Thread.sleep(500);            } catch (InterruptedException e) {                log.error(e.getMessage(),e);            }        }    }}

复制代码

在生产者中，我们每隔 0.5 秒创建一个新的 DelayedUser 对象，并入 Queue。

再创建一个消费者：

@Slf4j@Data@AllArgsConstructorpublic class DelayedQueueConsumer implements Runnable {
    private DelayQueue<DelayedUser> delayQueue;
    private int messageCount;
    @Override    public void run() {        for (int i = 0; i < messageCount; i++) {            try {                DelayedUser element = delayQueue.take();                log.info("take {}",element );            } catch (InterruptedException e) {                log.error(e.getMessage(),e);            }        }    }}

复制代码

在消费者中，我们循环从 queue 中获取对象。

最后看一个调用的例子：

    @Test    public void useDelayedQueue() throws InterruptedException {        ExecutorService executor = Executors.newFixedThreadPool(2);
        DelayQueue<DelayedUser> queue = new DelayQueue<>();        int messageCount = 2;        long delayTime = 500;        DelayedQueueConsumer consumer = new DelayedQueueConsumer(                queue, messageCount);        DelayedQueueProducer producer = new DelayedQueueProducer(                queue, messageCount, delayTime);
        // when        executor.submit(producer);        executor.submit(consumer);
        // then        executor.awaitTermination(5, TimeUnit.SECONDS);        executor.shutdown();
    }

复制代码

上面的测试例子中，我们定义了两个线程的线程池，生产者产生两条消息，delayTime 设置为 0.5 秒，也就是说 0.5 秒之后，插入的对象能够被获取到。

线程池在 5 秒之后会被关闭。

运行看下结果：

[pool-1-thread-1] INFO com.flydean.DelayedQueueProducer - put delayedUser DelayedUser(name=917, avaibleTime=1587623188389)[pool-1-thread-2] INFO com.flydean.DelayedQueueConsumer - take DelayedUser(name=917, avaibleTime=1587623188389)[pool-1-thread-1] INFO com.flydean.DelayedQueueProducer - put delayedUser DelayedUser(name=487, avaibleTime=1587623188899)[pool-1-thread-2] INFO com.flydean.DelayedQueueConsumer - take DelayedUser(name=487, avaibleTime=1587623188899)

复制代码

我们看到消息的 put 和 take 是交替进行的，符合我们的预期。

如果我们做下修改，将 delayTime 修改为 50000，那么在线程池关闭之前插入的元素是不会过期的，也就是说消费者是无法获取到结果的。

DelayQueue 是一种有奇怪特性的 BlockingQueue，可以在需要的时候使用。

5. 其他的要点

5.1 Comparable 和 Comparator 的区别

java.lang.Comparable 和 java.util.Comparator 是两个容易混淆的接口,两者都带有比较的意思，那么两个接口到底有什么区别，分别在什么情况下使用呢？

5.1.1 Comparable

Comparable 是 java.lang 包下面的接口，lang 包下面可以看做是 java 的基础语言接口。

实际上 Comparable 接口只定义了一个方法：

 public int compareTo(T o);

复制代码

实现这个接口的类都需要实现 compareTo 方法，表示两个类之间的比较。

这个比较排序之后的 order，按照 java 的说法叫做 natural ordering。这个 order 用在一些可排序的集合比如：SortedSet，SortedMap 等等。

当使用这些可排序的集合添加相应的对象时，就会调用 compareTo 方法来进行 natural ordering 的排序。

几乎所有的数字类型对象：Integer, Long，Double 等都实现了这个 Comparable 接口。

5.1.2 Comparator

Comparator 是一个 FunctionalInterface，需要实现 compare 方法：

int compare(T o1, T o2);

复制代码

Comparator 在 java.util 包中，代表其是一个工具类，用来辅助排序的。

在讲 Comparable 的时候，我们提到 Comparable 指定了对象的 natural ordering，如果我们在添加到可排序集合类的时候想按照我们自定义的方式进行排序，这个时候就需要使用到 Comparator 了。

Collections.sort(List,Comparator),Arrays.sort(Object[],Comparator) 等这些辅助的方法类都可以通过传入一个 Comparator 来自定义排序规则。

在排序过程中，首先会去检查 Comparator 是否存在，如果不存在则会使用默认的 natural ordering。

还有一个区别就是 Comparator 允许对 null 参数的比较，而 Comparable 是不允许的，否则会爬出 NullPointerException。

5.1.3 举个例子

最后，我们举一个 natural ordering 和 Comparator 的例子：

    @Test    public void useCompare(){        List<Integer> list1 = Arrays.asList(5, 3, 2, 4, 1);        Collections.sort(list1);        log.info("{}",list1);
        List<Integer> list2 = Arrays.asList(5, 3, 2, 4, 1);        Collections.sort(list2, (a, b) -> b - a);        log.info("{}",list2);    }

复制代码

输出结果：

[main] INFO com.flydean.CompareUsage - [1, 2, 3, 4, 5][main] INFO com.flydean.CompareUsage - [5, 4, 3, 2, 1]

复制代码

默认情况下 Integer 是按照升序来排的，但是我们可以通过传入一个 Comparator 来改变这个过程。

5.2 Reference 和引用类型

java 中有值类型也有引用类型，引用类型一般是针对于 java 中对象来说的，今天介绍一下 java 中的引用类型。java 为引用类型专门定义了一个类叫做 Reference。Reference 是跟 java 垃圾回收机制息息相关的类，通过探讨 Reference 的实现可以更加深入的理解 java 的垃圾回收是怎么工作的。

本文先从 java 中的四种引用类型开始，一步一步揭开 Reference 的面纱。

java 中的四种引用类型分别是：强引用，软引用，弱引用和虚引用。

5.2.1 强引用 Strong Reference

java 中的引用默认就是强引用，任何一个对象的赋值操作就产生了对这个对象的强引用。

我们看一个例子：

public class StrongReferenceUsage {
    @Test    public void stringReference(){        Object obj = new Object();    }}

复制代码

上面我们 new 了一个 Object 对象，并将其赋值给 obj，这个 obj 就是 new Object()的强引用。

强引用的特性是只要有强引用存在，被引用的对象就不会被垃圾回收。

5.2.2 软引用 Soft Reference

软引用在 java 中有个专门的 SoftReference 类型，软引用的意思是只有在内存不足的情况下，被引用的对象才会被回收。

先看下 SoftReference 的定义：

public class SoftReference<T> extends Reference<T>

复制代码

SoftReference 继承自 Reference。它有两种构造函数：

    public SoftReference(T referent)

复制代码

和：

    public SoftReference(T referent, ReferenceQueue<? super T> q)

复制代码

第一个参数很好理解，就是软引用的对象，第二个参数叫做 ReferenceQueue，是用来存储封装的待回收 Reference 对象的，ReferenceQueue 中的对象是由 Reference 类中的 ReferenceHandler 内部类进行处理的。

我们举个 SoftReference 的例子：

    @Test    public void softReference(){        Object obj = new Object();        SoftReference<Object> soft = new SoftReference<>(obj);        obj = null;        log.info("{}",soft.get());        System.gc();        log.info("{}",soft.get());    }

复制代码

输出结果：

22:50:43.733 [main] INFO com.flydean.SoftReferenceUsage - java.lang.Object@71bc1ae422:50:43.749 [main] INFO com.flydean.SoftReferenceUsage - java.lang.Object@71bc1ae4

复制代码

可以看到在内存充足的情况下，SoftReference 引用的对象是不会被回收的。

5.2.3 弱引用 weak Reference

weakReference 和 softReference 很类似，不同的是 weekReference 引用的对象只要垃圾回收执行，就会被回收，而不管是否内存不足。

同样的 WeakReference 也有两个构造函数：

public WeakReference(T referent)；
 public WeakReference(T referent, ReferenceQueue<? super T> q)；

复制代码

含义和 SoftReference 一致，这里就不再重复表述了。

我们看下弱引用的例子：

    @Test    public void weakReference() throws InterruptedException {        Object obj = new Object();        WeakReference<Object> weak = new WeakReference<>(obj);        obj = null;        log.info("{}",weak.get());        System.gc();        log.info("{}",weak.get());    }

复制代码

输出结果：

22:58:02.019 [main] INFO com.flydean.WeakReferenceUsage - java.lang.Object@71bc1ae422:58:02.047 [main] INFO com.flydean.WeakReferenceUsage - null

复制代码

我们看到 gc 过后，弱引用的对象被回收掉了。

5.2.4 虚引用 PhantomReference

PhantomReference 的作用是跟踪垃圾回收器收集对象的活动，在 GC 的过程中，如果发现有 PhantomReference，GC 则会将引用放到 ReferenceQueue 中，由程序员自己处理，当程序员调用 ReferenceQueue.pull()方法，将引用出 ReferenceQueue 移除之后，Reference 对象会变成 Inactive 状态，意味着被引用的对象可以被回收了。

和 SoftReference 和 WeakReference 不同的是，PhantomReference 只有一个构造函数，必须传入 ReferenceQueue：

public PhantomReference(T referent, ReferenceQueue<? super T> q)

复制代码

看一个 PhantomReference 的例子：

@Slf4jpublic class PhantomReferenceUsage {
    @Test    public void usePhantomReference(){        ReferenceQueue<Object> rq = new ReferenceQueue<>();        Object obj = new Object();        PhantomReference<Object> phantomReference = new PhantomReference<>(obj,rq);        obj = null;        log.info("{}",phantomReference.get());        System.gc();        Reference<Object> r = (Reference<Object>)rq.poll();        log.info("{}",r);    }}

复制代码

运行结果：

07:06:46.336 [main] INFO com.flydean.PhantomReferenceUsage - null07:06:46.353 [main] INFO com.flydean.PhantomReferenceUsage - java.lang.ref.PhantomReference@136432db

复制代码

我们看到 get 的值是 null，而 GC 过后，poll 是有值的。

因为 PhantomReference 引用的是需要被垃圾回收的对象，所以在类的定义中，get 一直都是返回 null：

    public T get() {        return null;    }

复制代码

5.2.5 Reference 和 ReferenceQueue

讲完上面的四种引用,接下来我们谈一下他们的父类 Reference 和 ReferenceQueue 的作用。

Reference 是一个抽象类，每个 Reference 都有一个指向的对象，在 Reference 中有 5 个非常重要的属性：referent，next，discovered，pending，queue。

private T referent;         /* Treated specially by GC */volatile ReferenceQueue<? super T> queue;Reference next;transient private Reference<T> discovered;  /* used by VM */private static Reference<Object> pending = null;

复制代码

每个 Reference 都可以看成是一个节点，多个 Reference 通过 next，discovered 和 pending 这三个属性进行关联。

先用一张图来对 Reference 有个整体的概念：

referent 就是 Reference 实际引用的对象。

通过 next 属性，可以构建 ReferenceQueue。

通过 discovered 属性，可以构建 Discovered List。

通过 pending 属性，可以构建 Pending List。

四大状态

在讲这三个 Queue/List 之前，我们先讲一下 Reference 的四个状态：

从上面的图中，我们可以看到一个 Reference 可以有四个状态。

因为 Reference 有两个构造函数，一个带 ReferenceQueue,一个不带。

    Reference(T referent) {        this(referent, null);    }
    Reference(T referent, ReferenceQueue<? super T> queue) {        this.referent = referent;        this.queue = (queue == null) ? ReferenceQueue.NULL : queue;    }

复制代码

对于带 ReferenceQueue 的 Reference，GC 会把要回收对象的 Reference 放到 ReferenceQueue 中，后续该 Reference 需要程序员自己处理（调用 poll 方法）。

不带 ReferenceQueue 的 Reference，由 GC 自己处理，待回收的对象其 Reference 状态会变成 Inactive。

创建好了 Reference，就进入 active 状态。

active 状态下，如果引用对象的可到达状态发送变化就会转变成 Inactive 或 Pending 状态。

Inactive 状态很好理解，到达 Inactive 状态的 Reference 状态不能被改变，会等待 GC 回收。

Pending 状态代表等待入 Queue，Reference 内部有个 ReferenceHandler，会调用 enqueue 方法，将 Pending 对象入到 Queue 中。

入 Queue 的对象，其状态就变成了 Enqueued。

Enqueued 状态的对象，如果调用 poll 方法从 ReferenceQueue 拿出，则该 Reference 的状态就变成了 Inactive，等待 GC 的回收。

这就是 Reference 的一个完整的生命周期。

三个 Queue/List

有了上面四个状态的概念，我们接下来讲三个 Queue/List：ReferenceQueue，discovered List 和 pending List。

ReferenceQueue 在讲状态的时候已经讲过了，它本质是由 Reference 中的 next 连接而成的。用来存储 GC 待回收的对象。

pending List 就是待入 ReferenceQueue 的 list。

discovered List 这个有点特别，在 Pending 状态时候，discovered List 就等于 pending List。

在 Active 状态的时候，discovered List 实际上维持的是一个引用链。通过这个引用链，我们可以获得引用的链式结构，当某个 Reference 状态不再是 Active 状态时，需要将这个 Reference 从 discovered List 中删除。

5.2.6 WeakHashMap

最后讲一下 WeakHashMap，WeakHashMap 跟 WeakReference 有点类似，在 WeakHashMap 如果 key 不再被使用，被赋值为 null 的时候，该 key 对应的 Entry 会自动从 WeakHashMap 中删除。

我们举个例子：

    @Test    public void useWeakHashMap(){        WeakHashMap<Object, Object> map = new WeakHashMap<>();        Object key1= new Object();        Object value1= new Object();        Object key2= new Object();        Object value2= new Object();
        map.put(key1, value1);        map.put(key2, value2);        log.info("{}",map);
        key1 = null;        System.gc();        log.info("{}",map);
    }

复制代码

输出结果：

[main] INFO com.flydean.WeakHashMapUsage - {java.lang.Object@14899482=java.lang.Object@2437c6dc, java.lang.Object@11028347=java.lang.Object@1f89ab83}[main] INFO com.flydean.WeakHashMapUsage - {java.lang.Object@14899482=java.lang.Object@2437c6dc}

复制代码

可以看到 gc 过后，WeakHashMap 只有一个 Entry 了。

5.3 类型擦除 type erasure

泛型是 java 从 JDK 5 开始引入的新特性，泛型的引入可以让我们在代码编译的时候就强制检查传入的类型，从而提升了程序的健壮度。

泛型可以用在类和接口上，在集合类中非常常见。本文将会讲解泛型导致的类型擦除。

5.3.1 举个例子

我们先举一个最简单的例子：

@Slf4jpublic class TypeErase {
    public static void main(String[] args) {        ArrayList<String> stringArrayList = new ArrayList<String>();        stringArrayList.add("a");        stringArrayList.add("b");        action(stringArrayList);    }
    public static void action(ArrayList<Object> al){        for(Object o: al)            log.info("{}",o);    }}

复制代码

上面的例子中，我们定义了一个 ArrayList，其中指定的类型是 String。

然后调用了 action 方法，action 方法需要传入一个 ArrayList，但是这个 list 的类型是 Object。

乍看之下好像没有问题，因为 String 是 Object 的子类，是可以进行转换的。

但是实际上代码编译出错：

Error:(18, 16) java: 不兼容的类型: java.util.ArrayList<java.lang.String>无法转换为java.util.ArrayList<java.lang.Object>

复制代码

5.3.2 原因

上面例子的原因就是类型擦除（type erasure)。java 中的泛型是在编译时做检测的。而编译后生成的二进制文件中并不保存类型相关的信息。

上面的例子中，编译之后不管是 ArrayList<String> 还是 ArrayList<Object> 都会变成 ArrayList。其中的类型 Object/String 对 JVM 是不可见的。

但是在编译的过程中，编译器发现了两者的类型不同，然后抛出了错误。

5.3.3 解决办法

要解决上面的问题，我们可以使用下面的办法：

    public static void actionTwo(ArrayList<?> al){        for(Object o: al)            log.info("{}",o);    }

复制代码

通过使用通配符？，可以匹配任何类型，从而通过编译。

但是要注意这里 actionTwo 方法中，因为我们不知道传入的类型到底是什么，所以我们不能在 actionTwo 中添加任何元素。

5.3.4 总结

从上面的例子我们可以看出，ArrayList<String>并不是 ArrayList<Object>的子类。如果一定要找出父子关系，那么 ArrayList<String>是 Collection<String>的子类。

但是 Object[] objArray 是 String[] strArr 的父类。因为对 Array 来说，其具体的类型是已知的。

5.4 深入理解 java 的泛型

泛型是 JDK 5 引入的概念，泛型的引入主要是为了保证 java 中类型的安全性，有点像 C++中的模板。

但是 Java 为了保证向下兼容性，它的泛型全部都是在编译期间实现的。编译器执行类型检查和类型推断，然后生成普通的非泛型的字节码。这种就叫做类型擦除。编译器在编译的过程中执行类型检查来保证类型安全，但是在随后的字节码生成之前将其擦除。

这样就会带来让人困惑的结果。本文将会详细讲解泛型在 java 中的使用，以避免进入误区。

5.4.1 泛型和协变

有关协变和逆变的详细说明可以参考:

深入理解协变和逆变

这里我再总结一下，协变和逆变只有在类型声明中的类型参数里才有意义，对参数化的方法没有意义，因为该标记影响的是子类继承行为，而方法没有子类。

当然 java 中没有显示的表示参数类型是协变还是逆变。

协变意思是如果有两个类 A<T> 和 A<C>, 其中 C 是 T 的子类，那么我们可以用 A 来替代 A。

逆变就是相反的关系。

Java 中数组就是协变的，比如 Integer 是 Number 的子类，那么 Integer[]也是 Number[]的子类，我们可以在需要 Number[] 的时候传入 Integer[]。

接下来我们考虑泛型的情况，List<Number> 是不是 List<Integer>的父类呢？很遗憾，并不是。

我们得出这样一个结论：泛型不是协变的。

为什么呢？我们举个例子：

List<Integer> integerList = new ArrayList<>();        List<Number> numberList = integerList; // compile error        numberList.add(new Float(1.111));

复制代码

假如 integerList 可以赋值给 numberList，那么 numberList 可以添加任意 Number 类型，比如 Float，这样就违背了泛型的初衷，向 Integer list 中添加了 Float。所以上面的操作是不被允许的。

刚刚我们讲到 Array 是协变的，如果在 Array 中带入泛型，则会发生编译错误。比如 new List<String>[10]是不合法的，但是 new List[10]是可以的。因为在泛型中?表示的是未知类型。

~~~java

List<?>[] list1 = new List<?>[10];

List<String>[] list2 = new List<String>[10]; //compile error

~~~

### 5.4.2 泛型在使用中会遇到的问题

因为类型擦除的原因，List<String>和 List<Integer>在运行是都会被当做成为 List。所以我们在使用泛型时候的一些操作会遇到问题。

假如我们有一个泛型的类，类中有一个方法，方法的参数是泛型，我们想在这个方法中对泛型参数进行一个拷贝操作。

~~~java

public class CustUser<T> {

public void useT(T param){

T copy = new T(param); // compile error

}

~~~

上面操作会编译失败，因为我们并不知道 T 是什么，也不知道 T 到底有没有相应的构造函数。

直接 clone T 是没有办法了，如果我们想 copy 一个 Set，set 中的类型是未定义的该怎么做呢？

~~~java

public void useTSet(Set<?> set){

Set<?> copy1 = new HashSet<?>(set); // compile error

Set<?> copy2 = new HashSet<>(set);

Set<?> copy3 = new HashSet<Object>(set);<br />

}

<pre><code class="">可以看到?是不能直接用于实例化的。但是我们可以用下面的两种方式代替。

再看看 Array 的使用：

~~~java

public void useArray(){

T[] typeArray1= new T[20]; //compile error

T[] typeArray2=(T[]) new Object[20];

T[] typeArray3 = (T[]) Array.newInstance(String.class, 20);

}

同样的，T 是不能直接用于实例化的，但是我们可以用下面两种方式代替。

5.4.3 类型擦除要注意的事项

因为类型擦除的原因，我们在接口实现中，实现同一个接口的两个不同类型是无意义的：

public class someClass implements Comparable<Number>, Comparable<String> { ... } // no

复制代码

因为在编译过后的字节码看来，两个 Comparable 是一样的。

同样的，我们使用 T 来做类型强制转换也是没有意义的：

public <T> T cast(T t, Object o) { return (T) o; }

复制代码

因为编译器并不知道这个强制转换是对还是错。

总结

集合是 java 中一个非常重要的工具类型，希望大家能够熟练掌握。

本文的代码例子https://github.com/ddean2009/learn-java-collections

本文的 PDFjava-collection-all-in-one.pdf

本文已收录于 http://www.flydean.com/java-collection-all-in-one/
最通俗的解读，最深刻的干货，最简洁的教程，众多你不知道的小技巧等你来发现！
欢迎关注我的公众号:「程序那些事」,懂技术，更懂你！

发布于: 2020 年 10 月 26 日阅读数: 57

原文链接:【http://xie.infoq.cn/article/c736282e1c6fbe3852c4e7927】。文章转载请联系作者。

程序那些事

关注

关注公众号：程序那些事，更多精彩等着你！ 2020.06.07 加入

最通俗的解读，最深刻的干货，最简洁的教程，众多你不知道的小技巧，尽在公众号：程序那些事！

评论 (1 条评论)

发布

程序那些事

加油，老铁！

2020 年 10 月 26 日 09:59

 1 回复

没有更多了

创作场景

万字长文深入理解 java 中的集合 - 附 PDF 下载

1. 前言

2. List

2.1 fail-safe fail-fast 知多少

2.1.1 Fail-fast Iterator

2.1.2 Fail-fast 的原理

2.1.3 Fail-safe Iterator

2.2 Iterator to list 的三种方法

2.2.1 使用 while

2.2.2 使用 ForEachRemaining

2.2.3 使用 stream

2.3 asList 和 ArrayList 不得不说的故事

2.3.1 创建 ArrayList

2.3.2 UnsupportedOperationException

2.3.3 asList

2.3.4 转换

2.4 Copy ArrayList 的四种方式

2.4.1 使用构造函数

2.4.2 使用 addAll 方法

2.4.3 使用 Collections.copy

2.4.4 使用 stream

3. Map

3.1 深入理解 HashMap 和 TreeMap 的区别

3.1.1 HashMap 和 TreeMap 本质区别

3.1.2 排序区别

3.1.3 Null 值的区别

3.1.4 性能区别

3.1.5 共同点

3.2 深入理解 HashMap 和 LinkedHashMap 的区别

3.2.1 LinkedHashMap 详解

3.2.2 插入

3.2.3 访问

3.2.4 removeEldestEntry

3.2.5 总结

3.3 EnumMap 和 EnumSet

3.3.1 EnumMap

3.3.2 什么时候使用 EnumMap

3.3.3 EnumSet

3.3.4 总结

3.4 SkipList 和 ConcurrentSkipListMap 的实现

3.4.1 SkipList

3.4.2 ConcurrentSkipListMap

4. Queue

4.1 java 中的 Queue 家族

4.1.1 Queue 接口

4.1.2 Queue 的分类

4.2 PriorityQueue 和 PriorityBlockingQueue

4.2.1 PriorityQueue

4.2.2 PriorityBlockingQueue

4.3 SynchronousQueue 详解

4.3.1 举例说明

4.4 DelayQueue 的使用

4.4.1 DelayQueue

4.4.2 DelayQueue 的应用

5. 其他的要点

5.1 Comparable 和 Comparator 的区别

5.1.1 Comparable

5.1.2 Comparator

5.1.3 举个例子

5.2 Reference 和引用类型

5.2.1 强引用 Strong Reference

5.2.2 软引用 Soft Reference

5.2.3 弱引用 weak Reference

5.2.4 虚引用 PhantomReference

5.2.5 Reference 和 ReferenceQueue

5.2.6 WeakHashMap

5.3 类型擦除 type erasure

5.3.1 举个例子

5.3.2 原因

5.3.3 解决办法

5.3.4 总结

5.4 深入理解 java 的泛型

5.4.1 泛型和协变

5.4.3 类型擦除要注意的事项

总结

程序那些事

评论 (1 条评论)