问Java ConcurrentMap -键在地图中的位置
EN

Stack Overflow用户

提问于 2012-04-26 06:31:04

回答 3查看 536关注 0票数 1

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

任何帮助都将不胜感激。

java

treemap

fifo

云联络中心6.1折起

灵活稳定的一体化云联络中心，助力快速搭建集电话、在线交流、音视频通话为一体的客户联络平台

回答 3

Stack Overflow用户

回答已采纳

发布于 2012-04-26 17:34:44

我相信像下面这样的代码就可以完成这项工作。我把element --> key的实现作为一个抽象方法。请注意，计数器用于将递增的数字分配给元素。还要注意，如果add(...)被多个线程调用，那么FIFO中的元素只是松散排序的。这迫使花哨的max(...)和min(...)逻辑。这也是为什么这个位置是近似的。第一个和最后一个都是特例。第一个可以清楚地标明。Last比较棘手，因为当前的实现返回一个真实的索引。

由于这是一个大概的位置，我建议您考虑让API返回一个介于0.0和1.0之间的float，以指示队列中的相对位置。

如果您的代码需要支持使用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;
        }
    }
}