实现并发 LinkedHashMap

Question

我正在尝试为多线程架构创建并发 LinkedHashMap。

如果我使用Collections#synchronizedMap()，我将不得不使用同步块进行迭代。此实现将导致元素的顺序添加。

如果我使用 ConcurrentSkipListMap 是否有任何方法可以实现比较器来按顺序存储，如存储在链接列表或队列中。

我想使用内置的java而不是第三方包。

编辑：

在这个并发的 LinkedHashMap 中，如果键是名称，我希望按键到达的顺序放置键。即新值将附加到开始或结束处，但顺序。

迭代时，LinkedHashMap 可以添加新条目，也可以删除。但迭代应该是添加条目的顺序。

据我所知，通过使用Collections#synchronizedMap()，必须实现迭代的同步块，但是映射在迭代时是否可以修改（可以添加/删除条目）。

Answer 1

如果使用synchronizedMap，除了迭代之外，不需要进行外部同步。如果需要保留映射的顺序，则应使用 SortedMap。您可以使用线程安全的 ConcurrentSkipListMap，或另一个与 SynchronizedSortedMap 结合的 SortedMap。

Answer 2

LinkedHashMap 有一个通过哈希表运行的双向链表。 FIFO 仅在写入（插入或删除）时改变链接。这使得版本的实现变得相当简单。

1. 编写仅允许插入顺序的 LHM。
2. 切换到 ConcurrentHashMap 作为哈希表。
3. 使用锁保护#put() / #putIfAbsent() / #remove()。
4. 使“下一个”字段变得不稳定。

在迭代时，不需要锁定，因为您可以安全地遵循“下一个”字段。只需在 #get() 上委托给 CHM 即可实现无锁读取。

Answer 3

使用 <代码>Collections#synchronizedMap()。

根据我的信念，如果我使用 Collections.synchronizedMap()，我将必须对 getter/setter 使用同步块。

这不是真的。您只需要同步任何视图（键集、值、条目集）上的迭代。另请参阅上面链接的 API 文档。

Answer 4

到目前为止，我的项目使用 Apache Collections 中的 LRUMap，但它基于 SequencedHashMap。 Collections 提出 ListOrderedMap 但没有一个是线程-安全的。

我已切换到 MapMaker来自 Google Guava。您可以查看 CacheBuilder也。

Answer 5

嗯，简单的答案是使用您的 Comparator 运行的单调递增密钥提供程序。想想AtomicInteger，每次插入时，都会创建一个用于比较的新键。如果您汇集真实密钥，则可以创建 OrderedKey 的内部映射。

class OrderedKey<T> implements Comparable<OrderedKey<T>> {
  T realKey;
  int index;
  OrderedKey(AtomicInteger source, T key) {
    index = source.getAndIncrement();
    realKey = key;
  }
  public int compareTo(OrderedKey<T> other) {
    if (Objects.equals(realKey, other.realKey)) {
      return 0;
    }
    return index - other.index;
  }


}

这将消除对自定义比较器的需要，并为您提供一个很好的 O(1) 方法来计算大小（除非您允许删除，在这种情况下，也对这些进行计数，因此您只需从“中减去”所有成功删除”即可所有成功添加”，其中成功意味着实际创建或删除了条目）。