如何实现具有类似LinkedHashMap功能的ConcurrentHashMap？

Question

我曾使用 accessOrder 设置为 true 的 LinkedHashMap，同时允许最多存储 500 条数据作为 LRU 缓存。但由于可扩展性问题，我想转向一些线程安全的替代方案。在这方面，ConcurrentHashMap 看起来不错，但缺少 LinkedHashMap 中的 accessOrder 和 removeEldestEntry(Map.Entry e) 功能。请问有人能提供一些链接或帮助我简化实现吗？

- DKSRathore

---

这是一个真正困难的问题。我们一直在尝试在Google Collections中解决它，但还没有完全解决。但我们会做到的... - Kevin Bourrillion

类似问题：https://dev59.com/-XM_5IYBdhLWcg3wZSTX - Vadzim

Answer 1

最近我使用了ConcurrentHashMap<String,CacheEntry>来实现类似的功能，其中CacheEntry包装了实际的项目并添加了缓存逐出统计信息：过期时间、插入时间（用于FIFO/LIFO逐出）、上次使用时间（用于LRU/MRU逐出）、命中次数（用于LFU/MFU逐出）等。实际的逐出是同步的，并创建了一个ArrayList<CacheEntry>，然后对其使用适当的比较器进行Collections.sort()。由于这很耗时，每个逐出操作都会删除CacheEntries底部的5%。我相信性能调整会有所帮助。

在您的情况下，由于您正在执行FIFO，您可以保留一个单独的ConcurrentLinkedQueue。当您向ConcurrentHashMap添加对象时，请执行ConcurrentLinkedQueue.add()以添加该对象。当您想要逐出一个条目时，请执行ConcurrentLinkedQueue.poll()以删除最旧的对象，然后从ConcurrentHashMap中删除它。

更新: 在这个领域的其他可能性包括Java集合同步包装器和Java 1.6 ConcurrentSkipListMap。

- Jim Ferrans

---

你的建议似乎非常符合我的需求。这意味着我需要保留其他元素的开销，这些元素将占用与地图集相同的空间。无论如何，这对我来说都没问题。 - DKSRathore

我知道已经有一段时间了，但我找到了你的答案，你能告诉我当你得到被驱逐的条目的ArrayList<CacheEntry>时，如何从ConcurrentHashMap中删除它们？你是通过迭代Map.Entry来检查值是否相同，然后使用其键从Map中删除它吗？还是我错过了什么，你用另一种方式做？ - wawek

Answer 2

你是否尝试过使用像ehcache这样的缓存解决方案？ 你可以尝试使用带有ReadWriteLock的LinkedHashMap。这将为您提供并发读访问。

- Peter Lawrey

---

还没有。但EHcache将是我的另一个选择。 - DKSRathore

我们尝试过使用带有LinkedHashMap(maxSize, true)的ReentrantReadWrite Locks，但是会出现ConcurrentModificationExceptions（get操作将修改map结构），而且性能比使用ConcurrentHashMap要差得多。 - dag

Answer 3

这可能看起来有点老了，但至少为了我的历史记录，我要在这里添加我的解决方案：我将 ConcurrentHashMap（将 K 映射到 WeakReference 的子类）、ConcurrentLinkedQueue 和一个基于 K 的值对象反序列化定义接口组合在一起，以正确运行 LRU 缓存。队列保存强引用，GC 会在适当时候从内存中清除值。跟踪队列大小涉及 AtomicInteger，因为您无法真正检查队列以确定何时进行清除。缓存将处理从/添加到队列的驱逐，以及映射管理。如果 GC 从内存中清除了值，则反序列化接口的实现将处理检索值的操作。我还有另一种实现方法，涉及将数据写入磁盘并重新读取，但与我在此发布的解决方案相比，它要慢得多，因为我必须同步写入/读取。

- Gene

---

谢谢，很高兴能在帖子中加入你的解决方案，即使时间已经有些久远。 - Guillaume

Answer 4

当您在concurrenthashmap中使用其他数据结构时，操作的原子性（例如在concurrenthashmap中添加新项和在其他数据结构中添加新项）不能保证不进行附加同步，例如使用ReadWriteLock，这将影响性能。

- kishore

Answer 5

您提到希望使用“线程安全”的替代方案来解决可扩展性问题。这里的“线程安全”意味着该结构对并发访问的尝试是容忍的，它不会在没有外部同步的情况下因并发使用而遭受破坏。然而，这种容忍并不一定有助于改善“可扩展性”。在最简单的（虽然通常是误导的）方法中，您将尝试在内部同步您的结构，并仍然保留非原子的“检查-然后-操作”操作不安全。

LRU缓存至少需要对总体结构有一定的了解。它们需要类似成员计数或成员大小的东西来决定何时驱逐元素，然后需要能够协调驱逐和并发尝试读取、添加或删除元素。试图减少对“主”结构的并发访问所需的同步会影响您的驱逐机制，并迫使您的驱逐策略在其保证方面变得不那么精确。

当前接受的答案提到“当您想要驱逐一个条目时”。这就是难点所在。您如何知道何时要驱逐一个条目？您需要暂停哪些其他操作才能做出这个决定？

- seh

Answer 6

将地图包装在Collections.synchronizedMap()中。如果您需要调用其他方法，则在从此调用返回的地图上进行同步，并在原始地图上调用原始方法（请参见Javadocs示例）。当您遍历键等时，也是如此。

- Aaron Digulla

---

"Aaron，这会加剧我的可扩展性问题。因为地图的更新将变得串行化。ConcurrentHashMap具有多个人同时更新地图的功能。" - DKSRathore

ConcHM具有一些特定的属性，这些属性不易映射到LinkedHM（即它允许并发插入，只要哈希没有映射到同一段键）。当您需要保持插入顺序时，这种优化是不可能的。您必须决定哪一个对您更重要。 - Aaron Digulla