实现并发LinkedHashMap

Question

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

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

如果我使用ConcurrentSkipListMap有任何方法可以实现Comparator按顺序存储，如存储在Linked List或队列中。

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

编辑：

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

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

我理解通过使用Collections#synchronizedMap()，必须实现迭代的同步块，但是在迭代时地图是可修改的（可以添加/删除条目）。

Answer 1

如果使用synchronizedMap，则除了迭代之外，不必在外部进行同步。如果需要保留地图的顺序，则应使用SortedMap。您可以使用ConcurrentSkipListMap（它是线程安全的）或另一个SortedMap与synchronizedSortedMap结合使用。

Answer 2

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

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

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

Answer 3

使用Collections#synchronizedMap()。

根据我的观点，如果我使用Collections.synchronizedMap（），我将不得不使用synchronized块作为getter / setter。

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

Answer 4

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

我已经从MapMaker切换到Google Guava。你也可以看看CacheBuilder。

Answer 5

嗯，简单的答案是使用你的Comparator操作的单调增加的密钥提供者。想想AtomicInteger，每次插入时，都会创建一个用于比较的新密钥。如果您汇集真实密钥，则可以制作OrderedKey<MyRealKeyType>的内部地图。

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）方法来计算大小（除非你允许删除，在这种情况下，也要计算它们，所以你可以从“减去”所有成功删除“所有成功的添加“，成功意味着实际创建或删除了一个条目”。