Java数据结构具有高效的添加，删除和随机 [英] Java data structure that has efficient add, delete, and random

问题描述

我需要一个Java数据结构，我可以有效地添加，删除和访问一个随机对象。

I need a Java data structure that I can efficiently add, delete, and access a random object.

这是不行的：

ArrayList具有高效的add（常数时间）和随机访问（只是get为随机整数），但删除可以采取线性时间，因为它必须可能搜索整个列表

ArrayList has efficient add (constant time), and random access (just "get" with a random integer), but deletes can take linear time because it has to potentially search the whole list for it.

TreeSet或HashSet有效的添加和删除，但我无法弄清楚如何获取随机对象。

TreeSet or HashSet has efficient add and delete, but I can't figure out how to get a random object.

任何想法？

理论上来说，B树可以工作，如果我可以随机使用Lefts或Rights来自行遍历树，但是我不认为一个标准的Java类给了我这种能力。

In theory, a B Tree would work, if I could traverse the tree myself with random Lefts or Rights, but I don't think a standard Java class gives me this ability.

如果标准Java类中没有任何内容，我愿意使用第三方库。

I'm willing to use a third party library if nothing in the standard Java classes will work.

我不需要支持重复或空值，也不需要线程安全。

I do not need to support duplicates or nulls, nor does it need to be thread safe.

谢谢。

推荐答案

你可以用Arr ayList / HashMap对（如果列表删除无序，地图将存储列表中对象的索引）。在删除时，不要将列表中的所有后续元素向下移动一个位置，您只需移动最后一个元素即可填充已删除项目的空间。那么在拆卸过程中最多需要触及两个不同的元素。一个快速的例子（我没有测试，希望我没有闯入）：

You can get this with an ArrayList/HashMap pair (where the map will store the index of objects in the list) if you make list removal unordered. On removal, instead of shifting all subsequent elements in the list down one position, you just move the last element to fill the space of the removed item. Then there are at most two different elements that need to be touched during removal. A quick example (which I haven't tested and hope I didn't bungle):

class SpecialSet<E> extends AbstractSet<E> implements Set<E> {
    private final List<E> list = new ArrayList<>();
    private final Map<E,Integer> indexMap = new HashMap<>();

    @Override
    public boolean add(E e) {
        if (contains(e)) return false;
        indexMap.put(e, list.size());
        list.add(e);
        return true;
    }

    @Override
    public boolean remove(Object o) {
        Integer indexBoxed = indexMap.remove(o);
        if (indexBoxed == null) return false;
        int index = indexBoxed;
        int last = list.size() - 1;
        E element = list.remove(last);
        if (index != last) {
            indexMap.put(element, index);
            list.set(index, element);
        }
        return true;
    }

    public E removeRandom() {
        E element = list.get((int)(Math.random() * size()));
        remove(element);
        return element;
    }

    @Override
    public boolean contains(Object o) {
        return indexMap.containsKey(o);
    }

    @Override
    public Iterator<E> iterator() {
        return list.iterator();
    }

    @Override
    public int size() {
        return list.size();
    }
}

根据您想要的对象等同性测试行为，您也许可以把一个IdentityHashMap的HashMap换成一个更好的速度。

Depending on what object equality testing behavior you want, you maybe could swap out the HashMap for an IdentityHashMap for a little better speed.

这篇关于Java数据结构具有高效的添加，删除和随机的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！