具有高效添加,删除和随机的Java数据结构

Question

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

这是行不通的:

ArrayList具有有效的添加(常量时间)和随机访问(只是"获取"随机整数),但删除可能需要线性时间,因为它必须可能搜索整个列表.

TreeSet或HashSet具有高效的添加和删除功能,但我无法弄清楚如何获取随机对象.

有任何想法吗？

从理论上讲,如果我可以使用随机Lefts或Rights自己遍历树,那么B树就可以工作了,但我不认为标准的Java类能给我这种能力.

如果标准Java类中没有任何内容可以使用,我愿意使用第三方库.

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

谢谢.

Answer 1

如果您使列表删除unordered ，您可以使用 ArrayList/HashMap 对（地图将在列表中存储对象的索引）获得它。移除时，不是将列表中的所有后续元素向下移动一个位置，而是移动最后一个元素以填充已移除项的空间。那么在移除过程中最多需要接触两个不同的元素。一个简单的例子（我没有测试过，希望我没有搞砸）：

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();
    }
}

根据您想要的对象相等性测试行为，您可以将 HashMap 换成 IdentityHashMap 以获得更好的速度。