ConcurrencyWithJava

并发数据结构

Java 集合框架

Java 集合框架：Java collections framework，JCF。

JCF 提供了一个包含多种可用于串行编程的数据结构集合。
Java 并发 API 对这些数据结构进行了扩展，提供了另外一些可用于并发应用程序的数据结构，包括如下两项。

• 接口：
  扩展了 JCF 提供的接口，添加了一些可用于并发应用程序的方法。

• 类：
  实现了前面的接口，提供了可以用于应用程序的具体实现。

JCF接口

BlockingQueue

队列是一种线性数据结构，允许在队列的末尾插入元素且从队列的起始位置获取元素。

它是一个先入先出（FIFO）型数据结构，第一个进入队列的元素将是第一个被处理的元素。

JCF 定义了 Queue 接口，该接口定义了在队列中执行的基本操作。该接口提供了实现如下操作的方法。

• add()、 offer()、 put() 在队列的末尾插入一个元素。

• remove()、 poll()、 take() 从队列的首部开始检索并删除一个元素。
• element()、 peek() 从队列的首部开始检索一个元素但不删除。

BlockingDeque

与队列一样，双端队列也是一种线性数据结构，但是允许从该数据结构的两端插入和删除元素。

JCF 定义了 Deque 接口，该接口扩展了 Queue 接口。
除了 Queue 接口提供的方法之外，它还提供了从两端执行插入、检索且删除、检索但不删除等操作的方法。

• 插入
  addFirst() 、 addLast() 、 offerFirst() 、 offerLast() 、 putFirst() 、 putLast()

• 检索并删除
  removeFirst() 、 removeLast() pollFirst() 、 pollLast() 、 takeFirst() 、 takeLast()
• 检索但不删除
  getFirst() 、 getLast() peekFirst() 、 peekLast()

ConcurrentMap

map （有时也叫关联数组）是一种允许存储(键，值)对的数据结构。
JCF 提供了 Map 接口，它定义了使用 map 的基本操作。

这些方法包括如下几个。

• put() ：
  向 map 插入一个(键，值)对。

• get() ：
  返回与某个键相关联的值。 remove() ：
  删除与特定键相关联的(键，值)对。
• containsKey() 和 containsValue() ：
  如果 map 中包含值的特定键，则返回 true 。
• forEach() ：
  该方法针对 map 的所有元素执行给定函数。
• compute() 、 computeIfAbsent() 和 computeIfPresent() ：
  这些方法允许指定一个函数，该函数用于计算与某个键相关的新值。
• merge() ：
  该方法允许你指定将某个(键，值)对合并到某个已有的 map 中。如果 map 中没有该键，则直接插入，否则，执行指定的函数。

TransferQueue

该接口扩展了 BlockingQueue 接口，并且增加了将元素从生产者传输到消费者的方法。
在这些方法中，生产者可以一直等到消费者取走其元素为止。

该接口添加的新方法有如下几项。

• transfer() ：
  将一个元素传输给一个消费者，并且等待（阻塞调用线程）该元素被使用。

• tryTransfer() ：
  如果有消费者等待，则传输一个元素。否则，该方法返回 false 值，并且不将该元素插入队列。

JCF类

Java 并发 API 为之前描述的接口提供了多种实现，其中一些实现并没有增加任何新特征，而另一些实现则增加了新颖有用的功能。

• LinkedBlockingQueue
  该类实现了 BlockingQueue 接口，提供了一个带有阻塞型方法的队列，该方法可以有任意有限数量的元素。
  该类还实现了 Queue 、 Collection 和 Iterable 接口。

• ConcurrentLinkedQueue
  该类实现了 Queue 接口，提供了一个线程安全的无限队列。
  从内部来看，该类使用一种非阻塞型算法保证应用程序中不会出现数据竞争。
• LinkedBlockingDeque
  该类实现了 BlockingDeque 接口，提供了一个带有阻塞型方法的双端队列，它可以有任意有限数量的元素。
  LinkedBlockingDeque 具有比 LinkedBlockingQueue 更多的功能，但是其开销更大。
  因此，应在双端队列特性不必要的场合使用 LinkedBlockingQueue 类。
• ConcurrentLinkedDeque
  该类实现了 Deque 接口，提供了一个线程安全的无限双端队列，它允许在双端队列的两端添加和删除元素。
  它具有比 ConcurrentLinkedQueue 更多的功能，但与 LinkedBlockingDeque 相同，该类开销更大。
• ArrayBlockingQueue
  该类实现了 BlockingQueue 接口，基于一个数组提供了阻塞型队列的一个实现，可以有有限个元素。
  它还实现了 Queue 、 Collection 和 Iterable 接口。与基于数组的非并发数据结构（ ArrayList和 ArrayDeque ）不同， ArrayBlockingQueue 按照构造函数中所指定的固定大小为数组分配空间，而且不可再调整其大小。
• DelayQueue
  该类实现了 BlockingDeque 接口，提供了一个带有阻塞型方法和无限数目元素的队列实现。
  该队列的元素必须实现 Delayed 接口，因此它们必须实现 getDelay() 方法。
  如果该方法返回一个负值或 0，那么延时已过期，可以取出队列的元素。
  位于队列首部的是延时负数值最小的元素。
• LinkedTransferQueue
  该类提供了一个 TransferQueue 接口的实现。它提供了一个元素数量无限的阻塞型队列。
  这些元素有可能被用作生产者和消费者之间的通信信道。在那里，生产者可以等待消费者处理它们的元素。
• PriorityBlockingQueue
  该类提供了 BlockingQueue 接口的一个实现，在该类中可以按照元素的自然顺序选择元素，也可以通过该类构造函数中指定的比较器选择元素。该队列的首部由元素的排列顺序决定。
• ConcurrentHashMap
  该类提供了 ConcurrentMap 接口的一个实现。它提供了一个线程安全的哈希表。
  除了 Java 8 中Map 接口新增加的方法之外，该类还增加了其他一些方法。
  • search() 、 searchEntries() 、 searchKeys() 和 searchValues() ：
    这些方法允许对(键，值)对、键或者值应用搜索函数。
    这些搜索功能可以是一个 lambda 表达式。
    搜索函数返回一个非空值时，该方法结束。这也是该方法的执行结果。
  • reduce() 、 reduceEntries() 、 reduceKeys() 和 reduceValues() ：
    这些方法允许应用一个 reduce() 操作转换(键，值)对、键，或者将其整个哈希表作为流处理。