具有高效添加，删除和随机的Java数据结构
我需要一个Java数据结构，我可以有效地添加，删除和访问随机对象。
这是不起作用的：
ArrayList具有高效的添加（常量时间）和随机访问（只是“获取”随机整数），但删除可能需要线性时间，因为它必须可能搜索整个列表。
TreeSet或HashSet具有高效的添加和删除function，但我无法弄清楚如何获取随机对象。
有任何想法吗？
从理论上讲，如果我可以使用随机Lefts或Rights自己遍历树，那么B树就可以工作了，但我不认为标准的Java类能给我这种能力。
如果标准Java类中没有任何内容可以使用，我愿意使用第三方库。
我不需要支持重复或空值，也不需要线程安全。
谢谢。
如果将列表删除无序，则可以使用ArrayList / HashMap对（其中地图将存储列表中的对象索引）来获取此对象。 在删除时，您只需移动最后一个元素以填充已删除项目的空间，而不是将列表中的所有后续元素向下移动一个位置。 然后在移除期间最多需要触摸两个不同的元素。 一个简单的例子（我没有测试过，希望我没有笨拙）：
class SpecialSet extends AbstractSet implements Set { private final List list = new ArrayList<>(); private final Map 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 iterator() { return list.iterator(); } @Override public int size() { return list.size(); } }
根据您想要的对象相等性测试行为，您可以将IdentityHashMap的HashMap替换为更快的速度。
请注意，如果预先分配到您需要的最大大小，则可以使用简单的数组。 保持“顶部”索引值并通过递增“top”并存储到该数组元素中进行插入。 删除时，将“top”值向下复制到已删除的元素中并递减“top”。
如果您不知道最大大小，仍然可以分配数组数组并使用相同的基本算法，则只需在访问元素之前首先计算主要和次要数组索引值。
我建议您使用带有整数键的Map。 这样你就可以为删除生成一个随机数。
给读者留下的问题：在随后的移除（或任何操作）上会有间隙。