java - Java ConcurrentMap - 键在地图中的位置

Question

我有一个有趣的问题需要帮助。我已经为两个单独的条件实现了几个队列，一个基于 FIFO，另一个基于键的自然顺序（ConcurrentMap）。也就是说，您可以想象两个队列具有相同的数据，只是排序不同。如果我根据某些标准在 ConcurrentMap 中找到键，我有一个问题（我正在寻找一种有效的方法），那么在 FIFO 映射中找到键的“位置”的最佳方法是什么。本质上我想知道它是第一个键（这很容易），还是说它是第 10 个键。

任何帮助将不胜感激。

Answer 1

没有用于访问 FIFO 映射中的订单的 API。你可以做到的唯一方法是迭代keySet()，values()或entrySet()计数。

Answer 2

如果您可以使用 a ConcurrentNavigableMap，则 的大小headMap正是您想要的。

Answer 3

我相信下面的代码可以完成这项工作。我将 element --> key 的实现保留为抽象方法。请注意用于为元素分配递增数字的计数器。另请注意，如果add(...)被多个线程调用，则 FIFO 中的元素只是松散排序的。这迫使幻想max(...)和min(...)逻辑。这也是为什么位置是近似的。第一个和最后一个是特殊情况。首先可以明确指出。最后一个很棘手，因为当前的实现返回一个真实的索引。

由于这是一个大概位置，我建议您考虑让 API 返回一个floatbetween0.0和1.0来指示队列中的相对位置。

如果您的代码需要使用除 之外的其他方式支持删除pop(...)，您将需要使用近似大小，并将返回更改为((id - min) / (max - min)) * size，并使用所有适当的int/float强制转换和舍入。

public abstract class ApproximateLocation<K extends Comparable<K>, T> {

    protected abstract K orderingKey(T element);

    private final ConcurrentMap<K, Wrapper<T>> _map = new ConcurrentSkipListMap<K, Wrapper<T>>();
    private final Deque<Wrapper<T>> _fifo = new LinkedBlockingDeque<Wrapper<T>>();
    private final AtomicInteger _counter = new AtomicInteger();

    public void add(T element) {
        K key = orderingKey(element);
        Wrapper<T> wrapper = new Wrapper<T>(_counter.getAndIncrement(), element);
        _fifo.add(wrapper);
        _map.put(key, wrapper);
    }

    public T pop() {
        Wrapper<T> wrapper = _fifo.pop();
        _map.remove(orderingKey(wrapper.value));
        return wrapper.value;
    }

    public int approximateLocation(T element) {
        Wrapper<T> wrapper = _map.get(orderingKey(element));
        Wrapper<T> first = _fifo.peekFirst();
        Wrapper<T> last = _fifo.peekLast();
        if (wrapper == null || first == null || last == null) {
            // element is not in composite structure; fifo has not been written to yet because of concurrency
            return -1;
        }
        int min = Math.min(wrapper.id, Math.min(first.id, last.id));
        int max = Math.max(wrapper.id, Math.max(first.id, last.id));
        if (wrapper == first || max == min) {
            return 0;
        }
        if (wrapper == last) {
            return max - min;
        }
        return wrapper.id - min;
    }

    private static class Wrapper<T> {
        final int id;
        final T value;

        Wrapper(int id, T value) {
            this.id = id;
            this.value = value;
        }
    }
}