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

random hashmap java

2022-09-01 11:38:52

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

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

从技术上讲，我觉得这应该是可能的，因为HashMap将其密钥存储在内部，并且从数组中随机选择很容易，但是我不知道如何访问它。因此，任何访问内部的想法都是非常受欢迎的。当然，其他解决方案（只要它们不消耗哈希图大小的线性时间）也很受欢迎。Entry[]Entry[]Entry[]

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

答案 1

从我的头顶

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

然后只是

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

答案 2

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

您需要的是第二个自定义数据结构来存储密钥，而不是像这里建议的一些人那样的列表。类似列表的数据结构从中删除项的成本很高。所需的操作是在恒定时间内添加/删除元素（以使其与HashMap保持最新）以及选择随机元素的过程。以下类正是这样做的SetMySet

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));
        indices.put(contents.get(index),index);
        contents.remove((int)(contents.size()-1));
        indices.remove(a);
     }
}