5

我想到了一个特定的用例，但无法找出要使用的正确数据结构。

我有一个线程可以将对象流式传输到 HashMap 中。类似于市场数据的东西，其中您有很高且未知的分时频率。

另一个线程不断读取此映射以获取更新的 Price 对象并按特定顺序按键查询。在给定的周期中，对于同一个键的查询可能会多次。读取和写入非常频繁，但读取线程只对完全更新的最新可用数据感兴趣，并且在写入完成之前不一定会阻塞。

我希望您对此类用例的理想数据结构有想法。是否有比可用的 ConcurrentHashMap 更好的实现？

谢谢

4

3 回答 3

2

并发哈希映射。来自 Javadoc

支持检索的完全并发和可调整的预期更新并发的哈希表。此类遵循与 Hashtable 相同的功能规范，并包含与 Hashtable 的每个方法对应的方法版本。但是，即使所有操作都是线程安全的，检索操作也不需要锁定，并且不支持以阻止所有访问的方式锁定整个表。在依赖线程安全但不依赖同步细节的程序中，此类与 Hashtable 完全可互操作。

检索操作（包括 get）一般不会阻塞，因此可能与更新操作（包括 put 和 remove）重叠。检索反映了最近完成的更新操作在其开始时保持的结果。对于 putAll 和 clear 等聚合操作，并发检索可能仅反映插入或删除某些条目。类似地，迭代器和枚举返回反映哈希表在创建迭代器/枚举时或之后的某个时间点的状态的元素。

于 2012-11-08T20:38:20.643 回答
1

如果在更新数据时未修改映射（即没有放置或删除），您甚至不需要像 ConcurrentHashMap 这样的同步映射。如果程序执行过程中不断有puts和removes，则需要同步这些调用。然而，当更新频率变高时（在多线程程序中），即使是 ConcurrentHashMap 也会开始抛出 ConcurrentModificationExceptions 。什么频率太高？您可能必须自己衡量，这取决于您平台中的许多因素。

在这些情况下，我会尝试创建一种情况，即在程序执行期间不必从映射中插入或删除，仅在数据流停止时启动和关闭时。如果这不可能，我使用普通的 HashMap 和优秀的数据结构CopyOnWriteArrayList的组合，并在外部进行同步。我还没有测试过 ConcurrentHashMap 的限制，但我不会将它用于我自己的生产系统。

编辑：ConcurrentHashMap 不会导致任何 ConcurrentModificationExceptions，仅当您使用 Collections.synchronizedMap 时，您可能会遇到麻烦。

于 2012-11-08T20:49:39.337 回答
1

一种方法是写时复制方案，如下所示：

public class Prices {
    private volatile Map<String, Integer> prices = Collections.emptyMap();

    public void putPrice(String ticker, int price) {
        HashMap<String, Integer> newPrices = new HashMap<String, Integer>(prices);
        newPrices.put(ticker, price);
        prices = newPrices;
    }

    public Integer getPrice(String ticker) {
        return prices.get(ticker);
    }
}

这对获取具有最小的开销 - 从 volatile 读取，然后是正常的哈希查找。但是，它对 puts 有很大的开销——创建一个全新的映射，以及对 volatile 的写入。如果您的读写比率很高，这可能仍然是一个很好的权衡。

您可以通过仅在实际需要添加新条目而不是更新现有条目时更改地图来改进这一点；您可以通过使用可变值来实现：

public class Prices {
    private volatile Map<String, AtomicInteger> prices = Collections.emptyMap();

    public void putPrice(String ticker, int price) {
        AtomicInteger priceHolder = prices.get(ticker);
        if (priceHolder != null) {
            priceHolder.set(price);
        }
        else {
            HashMap<String, AtomicInteger> newPrices = new HashMap<String, AtomicInteger>(prices);
            newPrices.put(ticker, new AtomicInteger(price));
            prices = newPrices;
        }
    }

    public Integer getPrice(String ticker) {
        AtomicInteger priceHolder = prices.get(ticker);
        if (priceHolder != null) return priceHolder.get();
        else return null;
    }
}

我不确定 an 的性能特征是什么AtomicInteger；这可能比看起来要慢。假设AtomicInteger不是不合理的慢，这应该非常快 - 它涉及从 volatile 读取两次加上每次获取的正常哈希查找，从 volatile 读取，哈希查找，以及对 volatile 的一次写入以更新现有价格。它仍然涉及复制地图以添加新价格。然而，在典型的市场中，这种情况并不经常发生。

于 2012-11-08T22:42:56.570 回答