java：并发集合

Question

我正在尝试找到一个或多个并发集合来使用，我可以实现以下行为（这些名称是出于类比目的而设计的）：

/**
 * Acts as a broker for a concurrent hash map that stores its keys in order 
 * of submission. At shipping time, the concurrent map is "sealed" 
 * (picture a truck with its cargo door being closed)
 * and its contents presented as an immutable map, and is replaced 
 * by a new concurrent map ready to accept values.
 *
 * Consumers of this class that submit information to it, are expected to 
 * know that this contains a concurrent collection, and should use the 
 * compareAndSet paradigm, e.g. the following:
 *
 * LoadingDock loadingDock = ...
 * boolean done = false;
 * while (!done)
 * {
 *    V oldValue = loadingDock.get();
 *    V newValue = computeNewValue(oldValue, otherInformation);
 *    if (oldValue == null)
 *       done = loadingDock.putIfAbsent(newValue) == null;
 *    else
 *       done = loadingDock.replace(oldValue, newValue) == oldValue;
 * }
 *    
 *
 * Keys and values must be non-null. Keys are not ordered.
 */
class LoadingDock<K,V>
{
    /**
     * analogous to ConcurrentMap's replace, putIfAbsent, and get methods
     */
    public boolean replace(K key, V oldValue, V newValue);
    public V putIfAbsent(K key, V value);
    public V get(K key)

    /* see above */
    public Map<K,V> ship();
}

我遇到了两个问题。

一是Java和Guava都不包含ConcurrentLinkedHashMap。这让我想知道为什么不——也许我错过了这样一个野兽的微妙之处。看起来我可以通过用一个类装饰 ConcurrentHashMap 来自己制作一个，如果 putIfAbsent() 被调用并返回 null，该类将一个键添加到列表中 - 我不需要任何ConcurrentHashMap 中除上述方法外还有其他方法，因此除了调用 putIfAbsent() 之外，无法向映射添加新键。

另一个更隐蔽的问题是，我似乎无法想到如何在不阻塞同步的情况下实现 Ship() ——当调用 Ship() 时，LoadingDock 需要引导所有新调用到新映射，并且在确定所有并发写入完成之前无法返回旧映射。 （否则我只会使用 AtomicReference 来保存并发映射。）

有没有办法做到这一点而无需同步？

Answer 1

您可以使用 ConcurrentSkipListMap 并提供您自己的比较器根据时间戳对条目进行排序。人们想象没有 ConcurrentLinkedMap，因为没有任何特别好的方法来实现它，这比同步常规方法要好得多。

对于 Ship() 方法，只需使用 ReadWriteLock 已开启公平模式。想要添加到映射的线程，获取读取锁（我知道这很奇怪的语义，但这就是它的工作原理，将其视为对映射的实际引用的读取模式，然后正常使用），以便多达想要的可以同时添加。在 Ship 方法中，您获取写入锁，它将阻止其他人在您导出和创建新地图时更改地图。公平模式使得您在调用 Ship() 时尽可能“切断”加法器，并让现有的加法器完成。