java - 根据不断变化的 map 对数组进行排序

Question

我有一个 ConcurrentHashMap，它会异步更新以镜像数据库中的数据。我正在尝试根据此数据对数组进行排序，该数据在大多数情况下都工作正常，但如果数据在排序时更新，那么事情可能会变得困惑。

我曾想过复制 map ，然后使用复制的 map 进行排序，但由于我需要排序的频率以及 map 的大小，这是不可能的。

Answer 1

我不确定我是否完全理解您的要求，因此我将处理两个单独的案例。 假设您的异步“更新”操作需要您更新 map 中的 2 个键。 场景 1 是:如果在两个更新中只有 1 个可见时发生“排序”操作，这是可以的。 场景 2 是:您需要 2 个更新同时可见或根本不可见(这称为原子行为)。

情况 1:您不需要原子批量更新

在这种情况下，ConcurrentHashMap 就可以了，因为迭代器保证在修改映射时不会失败。来自 ConcurrentHashMap 文档(重点是我的):

Similarly, Iterators and Enumerations return elements reflecting the state of the hash table at some point at or since the creation of the iterator/enumeration. They do not throw ConcurrentModificationException. However, iterators are designed to be used by only one thread at a time.

因此，您可以保证即使在修改映射时也可以迭代该映射，而不会因并发修改而导致迭代崩溃。但是(请参阅重点)您不能保证同时对 map 进行的所有修改都立即可见，即使只有其中一部分以及按顺序可见。

情况 2:您需要批量更新是原子的

此外，对于 ConcurrentHashMap，您无法保证批量操作 (putAll) 将以原子方式运行:

For aggregate operations such as putAll and clear, concurrent retrievals may reflect insertion or removal of only some entries.

因此，我看到了处理此案例的两种场景，每种场景都需要锁定。

解决方案 1:构建副本

构建“卡住”副本可以帮助您仅在所有其他更新都被锁定的阶段构建此副本，因为复制 map 意味着迭代它，我们的假设是如果我们有并发修改，那么迭代是不安全的。

这可能看起来像:

ConcurrentMap<String, String> map = new ConcurrentHashMap<String, String>(); //
AtomicReference<Map<String, String>> frozenCopy = new AtomicReference<Map<String, String>>(map); 

public void sortOperation() {
    sortUsingFrozenCopy();
}

public void updateOperation() {
    synchronized (map) { // Exclusive access to the map instance
        updateMap();
        Map<String, String> newCopy = new HashMap<String, String>();
        newCopy.putAll(map); // You build the copy. This is safe thanks to the exclusive access.
        frozenCopy.set(newCopy); // And you update the reference to the copy
    }
}

这个解决方案可以改进...... 看到您的 2 个操作(映射读取和映射写入)完全异步，可以假设您的读取操作无法知道(也不应该关心)前一个写入操作是在 0.1 秒之前发生还是在 0.1 秒之后发生。 因此，让您的读取操作依赖于 map 的“卡住副本”，该副本实际上每 1(或 2、5、10)秒(或更新事件)更新一次，而不是每次更新一次，这可能适合您的情况。

解决方案 2:锁定 map 以进行更新

锁定 map 而不复制它是一个解决方案。您需要一个 ReadWriteLock (或 Java 8 中的 StampedLock)，以便可以进行多种排序，并互斥读写操作。

解决方案2实际上很容易实现。你会有类似的东西

ReadWriteLock lock = new ReentrantReadWriteLock();

public void sortOperation() {
    lock.readLock().lock();
            // read lock granted, which prevents writeLock to be granted
    try {
        sort(); // This is safe, nobody can write
    } finally {
        lock.readLock().unlock();
    }
}

public void updateOperation() {
    lock.writeLock().lock();
            // Write lock granted, no other writeLock (except to myself) can be granted
            // nor any readLock
    try {
        updateMap(); // Nobody is reading, that's OK.
    } finally {
        lock.writeLock().unlock();
    }
}

使用ReadWriteLock，可以同时进行多次读取，也可以进行一次写入，但不能进行多次写入或读取和写入。 您必须考虑使用锁的公平变体的可能性，以便您确定每个读写进程最终都有机会被执行，具体取决于您的使用模式。

(注意:如果您使用锁定/同步，您的 Map 可能不需要并发，因为写入和读取操作将是独占的，但这是另一个主题)。