我设法找到一个解决方案，而不会降低性能。我将其张贴在这里，因为它可能对其他人有帮助-并可能回答有关此主题的几个未解决的问题（我将在以后搜索）。
您需要的是第二个
Set类似于自定义的数据结构来存储密钥-
而不是此处建议的列表。类似于列表的数据结构要从中删除项目成本很高。所需的操作是在固定时间内添加/删除元素（以使其与HashMap保持最新），以及选择随机元素的过程。下面的类
MySet正是这样做的
class MySet<A> { ArrayList<A> contents = new ArrayList(); HashMap<A,Integer> indices = new HashMap<A,Integer>(); Random R = new Random(); //selects random element in constant time A randomKey() { return contents.get(R.nextInt(contents.size())); } //adds new element in constant time void add(A a) { indices.put(a,contents.size()); contents.add(a); } //removes element in constant time void remove(A a) { int index = indices.get(a); contents.set(index,contents.get(contents.size()-1)); contents.remove(contents.size()-1); indices.set(contents.get(contents.size()-1),index); indices.remove(a); }}
