如何从Java中的HashMap中选择一个随机密钥？

Question

我正在使用大型ArrayList<HashMap<A,B>>，我会反复需要从随机HashMap中选择一个随机密钥（并用它做一些事情）。选择随机HashMap是微不足道的，但我该如何从这个HashMap中选择一个随机密钥？

速度很重要（因为我需要这样做10000次，并且哈希图很大），所以只需在[0,9999]中选择一个随机数k，然后在迭代器上执行k次xzxswpoi，这实际上不是一个选项。类似地，在每个随机选择上将HashMap转换为数组或ArrayList实际上不是一个选项。请在回复之前阅读此内容。

从技术上讲，我认为这应该是可能的，因为HashMap在内部将其键存储在.next()中，并且从数组中随机选择很容易，但我无法弄清楚如何访问这个Entry[]。因此，任何访问内部Entry[]的想法都非常受欢迎。其他解决方案（只要它们不占用散列图大小的线性时间）也是受欢迎的。

注意：启发式方法很好，所以如果有一种方法可以排除1％的元素（例如由于多个填充的桶），那就完全没问题了。

Answer 1

从我的头顶

Entry[]

然后就是

List<A> keysAsArray = new ArrayList<A>(map.keySet())
Random r = new Random()

Answer 2

您需要访问基础条目表。

map.get(keysAsArray.get(r.nextInt(keysAsArray.size()))

这仍然必须遍历条目以找到那里的条目，因此最坏的情况是O（n）但典型的行为是O（1）。

Answer 3

我设法找到了没有性能损失的解决方案。我会在这里发布它，因为它可以帮助其他人 - 并且可能回答关于这个主题的几个开放性问题（我稍后会搜索这些）。

你需要的是第二个自定义的

// defined staticly
Field table = HashMap.class.getDeclaredField("table");
table.setAccessible(true);
Random rand = new Random();

public Entry randomEntry(HashMap map) {
    Entry[] entries = (Entry[]) table.get(map);
    int start = rand.nextInt(entries.length);
    for(int i=0;i<entries.length;i++) {
       int idx = (start + i) % entries.length;
       Entry entry = entries[idx];
       if (entry != null) return entry;
    }
    return null;
}

数据结构来存储密钥 - 而不是像这里建议的列表。类似列表的数据结构从中删除项目的成本很高。所需的操作是在恒定时间内添加/删除元素（以使其与HashMap保持同步）以及选择随机元素的过程。以下课程Set就是这样做的

MySet

Answer 4

听起来你应该考虑一个辅助的键列表或一个真实的对象，而不是一个地图，存储在你的列表中。

Answer 5

我假设您正在使用

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

，因为您需要在以后查看某些内容？

如果不是这样，那么只需将你的HashMap改为HashMap / Array。

如果是这种情况，为什么不将对象存储在ArrayList和Map中，以便随机或按键查找。

或者，你可以使用ArrayList而不是TreeMap？我不知道你的密钥是什么类型，但你使用HashMap和一些关键的随机函数。

Answer 6

花了一些时间后，我得出结论，你需要创建一个可以由TreeMap.floorKey()和List<Map<A, B>>支持的模型来维护你的密钥。您需要保持List<A>和List<Map<A, B>>的访问权限，只需向调用者提供操作/方法即可。通过这种方式，您可以完全控制实现，实际对象将更安全地从外部更改。

顺便问一下，你的问题引导我，

• List<A>，和
• Why does the java.util.Set<V> interface not provide a get(Object o) method?：我试图变得聪明但当然，它的Bimap方法也会返回values()。

这个例子，Set，可以给你一个关于how-to的想法。

[编辑]

如果你决定创建自己的模型，这个类IndexedSet可能会帮助你。它明确指出它包装SetUniqueList，而不是副本。所以，我想，我们可以做点什么，

list

注意：我自己没试过。稍后会这样做（赶回家）。

Answer 7

从Java 8开始，有一个带O（log（N））附加内存的O（log（N））方法：通过

List<A> list = new ArrayList(map.keySet());
SetUniqueList unikList = new SetUniqueList(list, map.keySet);
// Now unikList should reflect all the changes to the map keys
...
// Then you can do
unikList.get(i);

创建一个Spliterator，make log（map.size（））map.entrySet().spliterator()调用并选择第一个或者下半场随机。如果说trySplit()中剩下少于10个元素，请将它们转储到列表中并随机选择。

Answer 8

如果您绝对需要在HashMap中访问Entry数组，则可以使用反射。但是那时你的程序将依赖于HashMap的具体实现。

如建议的那样，您可以为每个地图保留一个单独的键列表。你不会保留密钥的深层副本，因此实际的内存非规范化不会那么大。

第三种方法是实现自己的Map实现，即将密钥保存在列表而不是集合中的实现。

Answer 9

如何在另一个Map实现中包装HashMap？另一个映射维护一个List，而在put（）上它做：

Spliterator

（我假设不允许使用值的空值，如果它们使用containsKey，但速度较慢）