分块读取 ConcurrentHashMap（或类似的）

Question

我有一个程序，它有一个 ConcurrentHashMap，其中不同的线程可以 add/remove 地图中的项目。

我很想知道以 25 项为单位阅读地图的最佳方法是什么。我想要做的是这样的：用户点击一个按钮并从地图上读取 25 个项目（顺序无关紧要）。之后他可以单击 "Next" 按钮并阅读另外 25 个项目（与前 25 个不同），依此类推。

我不确定我是否可以用 ConcurrentHashMap 做到这一点。我不想使用数据库，我想将其保存在内存中。我不认为将 Map 转换为 ArrayList 会有帮助，因为大部分时间都是从地图中添加/删除项目。

我愿意接受任何解决方案，甚至是第 3 方库。

更新：我也不受 ConcurrentHashMap 的束缚。我只是在寻找最好的解决方案

更新 2：它们的键是 String

谢谢

Answer 1

对于您的情况，由于字符串键是严格排序的，因此 ConcurrentSkipListMap 是一种可行的方法。

它既是concurrent and navigable，又可以经常用来代替ConcurrentHashMap
get / put / remove 与 O(log N).
作为奖励，您将免费获得自然遍历顺序。

要从 ConcurrentSkipListMap 获取下一页，调用 tailMap 以上一页的最后一个键作为锚点，然后从结果子映射构造迭代器或流：

    return map.tailMap(lastKey, false).entrySet()
            .stream()
            .limit(pageSize)
            .collect(Collectors.toList());

注意 tailMap 即使从地图中删除锚键也会成功。迭代将从下一个大于锚点的键开始。

如果键没有严格排序，或者如果需要 O(1) 复杂度，那么您可能更喜欢替代建议 - 一个开放寻址散列 table 按单元格索引的顺序遍历。然而，标准 Java 类中没有这样的实现。这种映射的线程安全通常是通过锁定来实现的。

Answer 2

如果不想使用concurrenthashmap，可以考虑使用linkedhashmap，然后同步。
linkedhashmap 按插入顺序存储，因此您可以对其进行迭代。但是，您需要保留一个 lastViewedElement，当它被删除时，用一个新的有效值更新它，以便您可以从那里进行迭代。

它应该正确同步（可能是手动），因为它不是线程安全的。粗略的实现是：
（我是用头脑做的，而不是 IDE，所以它可能会遗漏一些东西。而且我的泛型不合格，而且你可能根本不需要泛型......）

public class MyMagicMap<X,Y> implements Map
    private LinkedHashMap<X,Y> innerMap = new LinkedHashMap<>();
    X lastKey = null;

    @Override
    public void put(X key,Y value) {
        synchronized(MyMagicMap.class) {
            if(innerMap.contains(key)) {
                innerMap.remove(key);
            }
            innerMap.put(key, value);
        }
    }

    @Override
    public Y remove(X key) {
        synchronized(MyMagicMap.class) {
            if(key.equals(lastKey) {
                lastKey = getKeyBefore(lastKey);
            }
            return innerMap.remove(key);
        }
    }

    private X getKeyBefore(X oldLastKey) {
        Iterator<X> it = innerMap.KeySet.iterator();
        for(X key : it  ) {
            if(key.equals(oldLastKey)) {
                return it.next();
            }
        }
    }

    public Map<X,Y> getNextBatch(int count) {
         synchronized(MyMagicMap.class) {

             Map<X,Y> resultMap = new HashMap();
             Iterator<X> it = innerMap.keySet().iterator();
             X lastKey = scanForLastKey(it);
             if(lastKey == null) {
                 return resultMap;
             }
             resultMap.put(lastKey, innerMap.get(key);
             for(int i; i < count-1; i++) {
                 if(it.hasNext()) {
                     X key = it.next();
                     resultMap.put(X, innerMap.get(key));
                 }
             }
        }
    }

    private X scanForLastKey(Iterator<X> iterator) {
        if(lastKey == null) {
            iterator.next();
        }
        while(iterator.hasNext()) {
            X key = iterator.next();
            if(key.equals(lastKey)) {
                return key;
            }
        }
        return null;
    }




    // other map methods can probably go without synchronization
}

需要注意的是相关块上有线程同步，只有一个线程应该这样做。
另请注意，删除方法性能不佳 (O(N))
如果你想更快地完成它，你必须实现你自己的 LinkedHashMap ，它允许你有效地确定下一个行。听起来很难，直到您意识到您只需要一个 HashMap> 以及具有上一个和下一个键值的三元组。再次同步 put 和 remove 操作，这是为了保持列表的完整性，即

void put(X key, Y value) {
    // synchronize this
    Triplet<X,Y,X> lastValueInMap = innerMap.get(endOfMapKey);
    lastValueInMap.rightElement = key;
    innerMap.put(X, new Triplet(endOfMapKey, value, null);
    endOfMapKey = key;
}
Y remove(X key) {
    // synchronize this.
    Triplet<X,Y,X> valueTriplet = innerMap.remove(key);
    if(valueTriplet.left != null)
        if(valueTriplet.right != null) {
            innerMap.get(valueTriplet.left).right = valueTriplet.right;
            innerMap.get(valueTriplet.right).left=valueTriplet.left;
        } else
        // etc.
     }
}

最后要注意的是 put 方法，如果键已经存在，它会显式删除键，而不是更新值。由于 LinkedHashMap 的更新不会修改插入顺序，这意味着如果未完成删除，任何已在批次中读取并稍后更新的键 K 将永远不会显示在较新的批次中。

分块读取 ConcurrentHashMap（或类似的）

Read ConcurrentHashMap (or similar) in chunks

java

concurrency

hashmap

java.util.concurrent