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

Question

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

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

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

注意:启发式方法很好,所以如果有一种方法可以排除1%的元素(例如,由于多个填充的桶),那就没有问题了.

Answer 1

从我的头顶

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

然后就是

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

Answer 2

您需要访问基础条目表。

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

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

Answer 3

我设法找到一个解决方案，而没有性能损失。我将其张贴在这里，因为它可能会对其他人有所帮助-并可能回答有关此主题的几个未解决的问题（我将在以后搜索）。

您需要的是第二个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);
     }
}