Java数据结构：高效添加、删除和随机访问

Question

Java数据结构：高效添加、删除和随机访问

javasearchdata-structuresrandom

6

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

以下是不起作用的方法：

ArrayList有高效的添加（常数时间）和随机访问（只需使用随机整数的“get”），但删除可能需要线性时间，因为它必须潜在地搜索整个列表。

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

有什么想法吗？

理论上，如果我能自己遍历树并随机选择左右节点，那么B树将起作用，但我不认为标准的Java类库能够给我这种能力。

如果标准Java类中没有适合的，我愿意使用第三方库。

我不需要支持重复项或null，并且它不需要是线程安全的。

谢谢。

- Magmatic

ArrayList.remove(int index) 运行时间为摊销常数时间。据我所知，这意味着单个调用是线性时间，但在一系列调用中的平均时间趋近于常数时间。 - Aarowaim

@Magmatic 你需要允许重复元素吗？ - Boann

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

1

你说的元素有多少个？是几百个？几千个？还是几百万个？它们是简单的数字、字符串，还是更复杂的对象？ - Hot Licks

关于ArrayList：你可以看一下GapList：https://dev59.com/questions/b4Dba4cB1Zd3GeqPDmR0#24140749 - rpax

显示剩余2条评论

3个回答

1

我建议您使用一个带有整数键的Map。这样，您可以为删除生成一个随机数。

留给读者的问题：在后续的删除（或任何操作）中，将会出现间隙。

- user949300

但是如果你不知道它的键，你怎么能删除一个值呢？你仍然需要进行低效的线性搜索来找到它。 - Magmatic

1

请注意，如果您预先分配到所需的最大大小，则可以使用简单的数组完成工作。保留“顶部”索引值，并通过递增“top”并存储到该数组元素中进行插入。删除时，将“top”值复制到已删除的元素中，并递减“top”。

如果您不知道最大大小，则仍可以分配一个数组的数组并使用相同的基本算法，只是在访问元素之前需要首先计算主要和次要数组索引值。

- Hot Licks

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Boann · Accepted Answer

如果你让列表的移除操作变得无序，就可以使用ArrayList/HashMap配对（其中Map将存储列表中对象的索引）。在移除时，不要将列表中后续的所有元素都向下移动一个位置，而是将最后一个元素移动到填补移除项的空间中。然后，在移除期间最多只需要触及两个不同的元素。这里有一个快速示例（我没有测试过并希望我没有搞砸）：

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以获得更好的速度。