java-collections-example

example for java collections

http://www.cs.rochester.edu/u/scott/papers/2009_Scherer_CACM_SSQ.pdf

---

Set

EnumSet<E extends Enum>

• RegularEnumSet

  • 内部存储结构为一个 long Bit 形式记载枚举的站位.long 的大小为 -2^63 ~ 2^63-1

• JumboEnumSet

  • 内部存储结构为一个 long 的数组,先查找出是哪一个数组然后再进行位运算

• complementOf 取反 EnumSet 没有被包含的枚举集合

HashSet

• HashSet 实际上就是 HashMap 的键集合

LinkedHashSet

• LinkedHashSet 实际上就是 LinkedHashMap 的键集合

CopyOnWriteArraySet

• CopyOnWriteArrayList 的子实现

SortedSet

• Set 约束添加一个保证，它的迭代器将以升序元素顺序遍历集合。
• E first() // 返回 set 里第一个元素
• E last() // 返回 set 里最后一个元素

NavigableSet

• E ceiling(E e) // 返回此集合中的最小元素大于或等于 e;如果不存在这样的元素，则返回 null
• E floor(E e) // 返回此集合中最大的元素小于或等于 e;如果没有这样的元素，则返回 null
• E higher(E e) // 返回此集合中的最小元素严格大于 e，如果不存在这样的元素，则返回 null
• E lower(E e) // 返回此集合中最大的元素严格小于 e，如果没有这样的元素，则返回 null

TreeSet

• TreeMap 的键集合

ConcurrentSkipListSet

• ConcurrentSkipListMap 的子实现

---

Queue

• add 新增,失败会异常

• offer 新增,失败会返回 false

• remove 删除某个节点,没有这个节点会抛出异常

• poll 检索头部和删除节点

• element 检索头部节点,没有会抛出异常

• peek 检索头部节点

AbstractQueue

• 实现接口关联 add 与 off 关联,remove 与 poll 关联, element 与 peek 关联, clear 与 poll 关联, addAll 与 add 关联

PriorityQueue

• 非线程安全

• 底层是一个数组结构

• 插入时自动排序大小

• 不能有相同的节点,否则排序会失效

• 类比 PriorityBlockingQueue

Deque

• 双端队列

LinkedList

• 底层是链表集合,能通过下标获取值

• 不是线程安全的

ArrayDeque

• Deque 接口的可调整大小的数组实现。

• 阵列deques没有容量限制;他们根据需要增长以支持使用。

• 不是线程安全的

• 禁止使用空元素。

• 当用作堆栈时，此类可能比 Stack 快，并且在用作队列时比 LinkedList 更快。

BlockingQueue

• 添加了一些超时接口

ArrayBlockingQueue

• 底层数组实现

• 支持用于排序等待生产者和消费者线程的可选公平策略。

• 阻塞队列

DelayQueue

• 延迟队列

• 阻塞队列

• 基于 PriorityQueue 实现

BlockingDeque

• 同 BlockingQueue

LinkedBlockingDeque

• 见 ArrayBlockingQueue

• 底层链表结构

LinkedBlockingQueue

• 底层链表结构

• 相对于 LinkedBlockingDeque 拥有 2 把锁,可以在新增的时候同时消费

TransferQueue

• BlockingQueue 的子集

• 生产者可以等待消费者接收元素

• TransferQueue 可能在例如消息传递应用程序中很有用，其中生产者有时（使用方法转移（E））等待消费者调用 take 或 poll 接收元素，而在其他时候将元素排队（通过方法 put ）而不等待接收。 还可以使用 tryTransfer 的非阻塞和超时版本。 也可以通过 hasWaitingConsumer() 查询 TransferQueue，是否有任何线程等待项目，这与窥视操作相反。

LinkedTransferQueue

• 基于链接节点的无界 TransferQueue。该队列针对任何给定的生产者对元素 FIFO（先入先出）进行排序。队列的头部是队列中某个生产者最长时间的元素。队列的尾部是队列中的元素，对于某些生产者来说是最短的时间。 请注意，与大多数集合不同，size 方法不是恒定时间操作。由于这些队列的异步性质，确定元素的当前数量需要遍历元素，因此如果在遍历期间修改此集合，则可能会报告不准确的结果。 此外，批量操作 addAll，removeAll，retainAll，containsAll，equals 和 toArray 不保证以原子方式执行。例如，与 addAll 操作同时运行的迭代器可能只查看一些添加的元素。

• 该类及其迭代器实现了 Collection 和 Iterator 接口的所有可选方法。

• 内存一致性效果：与其他并发集合一样，在将对象放入 LinkedTransferQueue 之前，线程中的操作发生在从另一个线程中的 LinkedTransferQueue 访问或删除该元素之后的操作之前。

• 由 Scherer 和 Scott 2004-DISC-DDS.pdf 引入的双队列是（链接）队列，其中节点可以表示数据或请求。 当一个线程试图将数据节点入队但遇到一个请求节点时，它会“匹配”并将其删除; 反之亦然，用于排队请求。 阻止双队列安排排队不匹配请求的线程阻塞，直到其他线程提供匹配。 双同步队列（参见 Scherer，Lea 和 Scott 2009_Scherer_CACM_SSQ.pdf）还安排排队不匹配数据的线程也会阻塞。 双重传输队列支持所有这些模式，如呼叫者所指示的。

• 可以使用 Michael 和 Scott 无锁队列算法 的变体来实现 FIFO 双队列。 它维护两个指针字段“head”，指向（匹配的）节点，该节点又指向第一个实际（不匹配的）队列节点（如果为空，则为null）; 和“tail”指向队列中的最后一个节点（如果为空则再次为null）。 例如，这是一个包含四个数据元素的队列：

  head                tail
  |                   |
  v                   v
  M -> U -> U -> U -> U
  

• 已知 M&S 队列算法在维护（通过 CAS）这些头尾指针时容易出现可扩展性和开销限制。这导致了减少争用变量的发展，例如消除数组和乐观的反向指针。 但是，双队列的性质使得在需要双重性时可以采用更简单的策略来改进 M&S 风格的实现。

• 在双队列中，每个节点必须以原子方式保持其匹配状态。虽然还有其他可能的变体，但我们在此实现这一点：对于数据模式节点，匹配需要在匹配时将非空数据值中的“item”字段 CASing 为 null， 反之请求节点，CASing来自 null 到数据值。 （请注意，此类队列的线性化属性易于验证 - 元素通过链接可用，并且通过匹配不可用。）与普通 M&S 队列相比， 双队列的此属性需要每个 enq /另外一个成功的原子操作 deq 对。 但它也可以实现队列维护机制的低成本变体。 （这种想法的变体甚至适用于支持删除内部元素的非双重队列， 例如 j.u.c.ConcurrentLinkedQueue。）

• 匹配节点后，其匹配状态永远不会再次更改。因此，我们可以安排它们的链表包含零个或多个匹配节点的前缀，后跟零个或多个不匹配节点的后缀。（注意，我们允许前缀和后缀都为零长度， 这反过来意味着我们不使用虚拟头。）如果我们不关心时间或空间效率，我们可以正确执行入队和出队操作 遍历从指针到初始节点; 在匹配时对第一个不匹配节点的项进行 CASing， 并对追加到尾随节点的下一个字段进行 CASing。 （最初空的时候还加上一些特殊的外壳）。 虽然这本身就是一个糟糕的想法，但它确实具有不需要在头/尾场上进行任何原子更新的好处。

• 我们在这里介绍一种方法，它位于从不与总是更新队列（头部和尾部）指针的极端之间。 这提供了在有时需要额外遍历步骤来定位第一个和/或最后一个不匹配节点之间的权衡，而不是减少的开销和对队列指针的更少更新的争用。 例如，队列的可能快照是：

  head           tail
    |              |
    v              v
    M -> M -> U -> U -> U -> U
  

• 这种“松弛”的最佳值（“头部”和第一个不匹配节点的值之间的目标最大距离，以及“尾部”的类似）是一个经验问题。 我们发现使用 1-3 范围内的非常小的常数可以在一系列平台上运行得最好。 较大的值会导致缓存未命中的成本增加以及长遍历链的风险，而较小的值会增加 CAS 争用和开销。

• 具有松弛的双队列与普通的 M&S 双队列不同，因为在匹配，附加或甚至遍历节点时，有时仅更新头部或尾部指针; 为了保持目标松弛。 “有时”的想法可以通过几种方式实现。 最简单的方法是在每个遍历步骤中使用递增计数器， 并在计数超过阈值时尝试（通过 CAS）更新关联的队列指针。 另一个需要更多开销的是使用随机数生成器以每个遍历步骤的给定概率进行更新。

• 在这些行的任何策略中，因为 CAS 更新字段可能失败，实际的松弛可能超过目标松弛。但是，可以随时重试它们以维持目标。即使使用非常小的松弛值，这种方法也适用于双队列，因为它允许所有操作直到匹配或附加项目 （因此可能允许另一个线程进展）为只读，因此不会进一步引入争。如下所述，我们通过仅在这些点之后执行松弛维护重试来实现此目的。

• 作为这种技术的伴随，可以进一步减少遍历开销而不增加头指针更新的争用：线程有时可以将当前“头”节点的“下一个”链路路径缩短为更接近当前已知的第一个不匹配节点，并且 同样的尾巴。同样，这可以通过使用阈值或随机化来触发。

• 必须进一步扩展这些想法，以避免由旧的遗忘的头节点开始的节点的顺序“下一个”链接引起的无限量的昂贵回收垃圾：首先由 Boehm 详细描述 如果 GC 延迟注意到任何任意旧节点已变为垃圾，则所有较新的死节点也将被取消。 （类似的问题出现在非 GC 环境中。）为了在我们的实现中处理这个问题，在 CASing 推进头指针时，我们将前一个头的“next”链接设置为仅指向它自己; 从而限制了连接死亡列表的长度。（我们也会采取类似的措施来消除其他节点字段中可能存在的垃圾保留值。）但是，这样做会增加遍历的一些复杂性：如果任何“下一个”指针链接到自身，则表明当前线程落后了头部更新，因此遍历必须从“头部”继续。 尝试从“尾部”开始寻找当前尾部的遍历也可能遇到自我链接，在这种情况下，它们也继续在“头部”。

• 在基于松弛的方案中，甚至不使用 CAS 进行更新（类似于 M&S）是诱人的。但是，在上述链接遗忘机制下，对于头更新无法做到这一点，因为更新可能会留在分离的节点上。虽然直接写入可能用于尾部更新，但是它们增加了长时间撤回的风险， 因此增加了长垃圾链，考虑到执行 CAS 与写入的成本差异较小时，这可能比成本高得多。 在每次操作时触发（特别是考虑到写入和CAS同样需要额外的 GC 簿记（“写入障碍”），有时因为争用而比写入本身更昂贵）。

• 我们使用基于阈值的方法进行更新，松弛阈值为 2 - 也就是说，当当前指针看起来距离第一个/最后一个节点两步或更远时，我们更新头/尾。 松弛值是硬连线的：通过检查遍历指针的相等性自然地实现大于 1 的路径， 除非列表只有一个元素，在这种情况下我们将松弛阈值保持为 1。避免在方法调用中跟踪显式计数会略微简化已经混乱的实现。如果有一个质量低劣的每线程可用的随机化可能会更好， 但即使 ThreadLocalRandom 对于这些目的来说也太重了。

• 利用这样小的松弛阈值，除了取消/移除（见下文）之外，不值得用路径短路（即，未拼接的内部节点）来增加这一点。

• 在任何节点入队之前，我们允许 head 和 tail 字段为 null;在第一次追加时初始化。这简化了一些其他逻辑，并提供了更有效的显式控制路径，而不是让 JVM 在它们为空时插入隐式 NullPointerExceptions。 虽然目前还没有完全实现，但我们也可以在空的时候将这些字段重新置零（这很复杂，但收效甚微）。

• 所有入队/出队操作都由单个方法“xfer”处理，其中参数指示是否充当某种形式的 offer，put，poll，take 或 transfer（每个可能都有超时）。 使用单一方法的相对复杂性超过了为每种情况使用单独方法的代码批量和维护问题。

• 操作最多包括三个阶段。 第一个是在方法 xfer 中实现的，第二个是在 tryAppend 中实现的，第三个是在方法 awaitMatch 中实现的。

  • 尝试匹配现有节点

    从头开始，跳过已经匹配的节点，直到找到相反模式的不匹配节点（如果存在），在这种情况下匹配它并返回，如果需要，也可以在匹配节点之后更新头部（或者如果列表具有节点本身） 没有其他不匹配的节点）。 如果 CAS 未命中， 则循环重试前进两步，直到成功或松弛最多为两步。通过要求每次尝试逐头前进（如果适用），我们确保松弛不会无限制地增长。遍历还检查初始头是否现在是偏离列表，在这种情况下，它们从新头开始。 如果找不到候选人并且呼叫是不定时的民意调查/提议，（参数“如何”现在）返回。

  • 尝试附加一个新节点（方法 tryAppend）

    从当前尾指针开始，找到实际的最后一个节点并尝试附加一个新节点（或者如果 head 为 null，则建立第一个节点）。 仅当节点的前任已经匹配或具有相同模式时，才能追加节点。 如果我们另外检测到， 则在遍历期间必须附加具有相反模式的新节点，因此我们必须在阶段 1 重新开始。遍历和更新步骤与第 1 阶段类似：重试 CAS 未命中并检查陈旧性。 特别是，如果遇到自链接， 那么我们可以通过在当前头部继续遍历来安全地跳转到列表上的节点。 成功追加时，如果呼叫是 ASYNC，则返回。

  • 等待匹配或取消（方法 awaitMatch）

    等待另一个线程匹配节点;而是取消当前线程是否被中断或等待超时。在多处理器上，我们使用队列前旋转：如果一个节点看起来是队列中第一个不匹配的节点，它会在阻塞之前旋转一点。在任何一种情况下， 在阻塞之前它会尝试取消当前“head”和第一个不匹配节点之间的任何节点。队列前旋转大大提高了大量争用队列的性能。只要它相对简短且“安静”，旋转对于较少争用的队列的性能影响不大。 在旋转线程期间检查它们的中断状态并生成线程局部随机数，以决定偶尔执行 Thread.yield。虽然产量规格不足，但我们认为限制纺纱对繁忙系统的影响可能会有所帮助，也不会受到影响。 我们还使用较小的（1/2）旋转用于未知前端但其前辈未被阻塞的节点 - 这些“链式”旋转避免了前端队列规则的伪像，否则会导致交替节点旋转与阻塞。此外，与其前任相比， 表示相位变化（从数据到请求节点或反之亦然）的前线程接收额外的链式自旋，反映了在相位变化期间解锁线程通常所需的较长路径。

• 取消链接删除的内部节点

  • 除了通过上述自我链接最小化垃圾保留之外，我们还取消了删除的内部节点的链接。这些可能是由于超时或中断等待或调用 remove(x) 或 Iterator.remove 而引起的。通常情况下，如果一个节点一度被称为要删除的某个节点的前身， 我们可以通过 CASing 它的前任的下一个字段（如果它仍然指向s）来解除s（否则s必须已经存在）删除或现在是 offlist）。但是有两种情况我们不能保证以这种方式使节点不可达： （1）如果 s 是列表的尾随节点（即，下一个是 null），那么它被固定为追加的目标节点，所以只能在追加其他节点后删除。 （2）在给定匹配的前趋节点（包括被取消的情况）的情况下，我们不一定能够取消链接：前一个可能已经是未拼接的，在这种情况下，一些先前可达节点仍然可以指向s。 （有关进一步说明，请参阅Herlihy＆Shavit“多处理器编程的艺术”第9章）。 虽然，在这两种情况下，如果 s 或其前任（或可以使其成为）或从列表负责人中脱离，我们可以排除采取进一步行动的必要性。

  • 如果不考虑这些因素，有可能无限数量的所谓删除节点仍然可以访问。 导致这种积累的情况并不常见，但在实践中可能会发生; 例如，当一系列短暂的定时调用重复超时但由于在队列前面进行不定时的调用而从未从列表中掉落。

  • 当这些情况出现时，而不是总是回溯整个列表以找到一个实际的前连接器来取消链接（这对案例（1）无论如何都没有帮助），我们记录了对可能的非连接故障的保守估计（在“sweepVotes”中）。 当估计超过阈值（“SWEEP_THRESHOLD”）时，我们触发完全扫描，指示在扫描之前容许的估计移除失败的最大数量，取消链接在初始移除时未解除链接的取消节点。 我们通过线程命中阈值 （而不是后台线程或通过将工作扩展到其他线程）执行扫描，因为在发生删除的主要上下文中，调用者已经超时，取消或执行可能的O（n）操作 （例如 remove(x)），其中没有一个对时间要求足以保证替代方案对其他线程施加的开销。

  • 因为 sweepVotes 估计是保守的，并且因为节点在从队列的头部落下时“自然地”被取消链接，并且因为即使在扫描正在进行中我们允许投票累积，所以通常比估计的节点少得多。 阈值的选择平衡了浪费努力和争用的可能性， 而不是提供静态队列中内部节点保留的最坏情况限制。 根据经验选择下面定义的值以在各种超时情况下平衡这些值。

  • 请注意，我们无法在扫描期间自行链接未链接的内部节点。 但是，当一些后继者最终脱离列表的头部并且是自我链接时，相关的垃圾链终止。

• https://www.cnblogs.com/lighten/p/7505355.html

PriorityBlockingQueue

• 相对于 PriorityQueue 线程安全

SynchronousQueue

• 阻塞队列

• 每个插入操作必须等待另一个线程执行相应的删除操作，反之亦然。同步队列没有任何内部容量，甚至没有容量。您无法查看同步队列，因为只有在您尝试删除元素时才会出现该元素;你不能插入一个元素（使用任何方法），除非另一个线程试图删除它; 你不能迭代，因为没有什么可以迭代。队列的头部是第一个排队插入线程试图添加到队列的元素;如果没有这样的排队线程，那么没有元素可用于删除，poll() 将返回 null。出于其他 Collection方法 （例如 contains ）的目的，SynchronousQueue 充当空集合。此队列不允许 null 元素。

• 同步队列类似于 CSP 和 Ada 中使用的集合点通道。它们非常适用于切换设计，其中在一个线程中运行的对象必须与在另一个线程中运行的对象同步，以便将其传递给某些信息，事件或任务。

• 此类支持用于排序等待生产者和消费者线程的可选公平策略。默认情况下，不保证此顺序。但是，将 fairness 设置为 true 构造的队列以 FIFO 顺序授予线程访问权限。

ConcurrentLinkedQueue

• 基于链接节点的无界线程安全队列。此队列命令元素 FIFO（先进先出）。队列的头部是队列中最长时间的元素。队列的尾部是队列中最短时间的元素。在队列的尾部插入新元素，队列检索操作获取队列头部的元素。 当许多线程共享对公共集合的访问权限时，ConcurrentLinkedQueue是一个合适的选择。与大多数其他并发集合实现一样，此类不允许使用 null 元素。 该实现采用有效的“无等待”算法，该算法基于 Maged M.Michael 和 Michael L.Scott 的简单，快速，实用的非阻塞和阻塞并发队列算法中描述的算法。

• 迭代器是弱一致的，在迭代器创建时或之后的某个时刻返回反映队列状态的元素。它们不会抛出 ConcurrentModificationException，并且可能与其他操作同时进行。自创建迭代器以来队列中包含的元素将只返回一次。

• 请注意，与大多数集合不同，size 方法不是恒定时间操作。由于这些队列的异步性质，确定当前元素数量需要遍历元素，因此如果此集合可能会报告不准确的结果此外，批量操作 addAll，removeAll，retainAll， containsAll，equals 和 toArray 不是保证以原子方式执行。例如，与 addAll 操作同时运行的迭代器可能只查看一些添加的元素。

• 该类及其迭代器实现了 Queue 和 Iterator 接口的所有可选方法。

• 内存一致性影响：与其他并发集合一样，在将对象放入 ConcurrentLinkedQueue 之前，线程中的操作发生在从另一个线程中的 ConcurrentLinkedQueue 访问或删除该元素之后的操作之前。

List

ArrayList

• 非线程安全

• 底层结构数组

• 可初始化指定大小, 添加第一个元素之前初始化大小为 10

• int newCapacity = oldCapacity + (oldCapacity >> 1); 扩容没特殊情况时扩展 1.5 倍

LinkedList

• 非线程安全

• 底层链表结构

Vector

• synchronized 实现线程安全

• 底层结构数组

• 可初始化指定大小, 默认 10,可指定扩容量默认 0, 即翻倍扩容 int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);

CopyOnWriteArrayList

• 底层结构数组

• setArray(new Object[0]) 初始化默认为 0 大小的数组

• 添加删除都是整体替换整个数组,没有所谓的扩容.

• ReentrantLock 实现线程安全

Map

HashMap

• 非线程安全

• 初始化可指定大小(工具指定的大小会计算出一个默认的桶的个数,如果没有指定则默认 16 个桶)和加载因子.

• 加载因子就是值的总数到达了一定的比例就扩容

• 当链表的长度达到 8 的时候转换成红黑树，红黑树的个数少于 6 的时候退化成链表

LinkedHashMap

• 在添加元素后,添加到链表结构,来保证数据顺序

• 其他见 HashMap

Hashtable

• synchronized 线程安全

• 键值对都不允许为 null

IdentityHashMap

• 键值对都保存在一个数组里面,0 和 1, 2 和 3 ... 这样的位置保存

• 通过 hash 运算如果冲突且相等则替换原来的值,或者扩容.

WeakHashMap

• 键值对实现了 WeakReference ,弱引用,当键 gc 的时候会被删除

AbstractMap

EnumMap

• 键使用的是枚举

• 内置的数组会根据初始化的枚举内部的值数量来初始化数组大小

• 枚举的键值对在数组的下标是枚举的顺序变量

TreeMap

• 有序

• 节点红黑树结构

ConcurrentMap

ConcurrentHashMap

• CAS 线程安全,1.8 放弃了 1.7 的分段加锁设计

ConcurrentSkipListMap

• 跳表以空间换时间,平衡了链表和红黑树的特点和缺陷

• CAS 保证线程安全,Comparator 排序

• ConcurrentSkipListMap