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.想要添加到地图的线程,获取Read锁(我知道的奇怪语义,但它是如何工作的,将其视为对地图的实际引用的读取模式,然后正常使用),以便尽可能多地使用想要可以同时添加.在ship方法中,您获取了Write锁定,它将阻止其他任何人在您导出并创建新地图时更改地图.公平模式使得你"切断"加法器尽可能接近于调用ship()并让现有的加法器完成.