28

我正在使用一个大ArrayList<HashMap<A,B>>的 ，我会反复需要从随机 HashMap 中选择一个随机键（并用它做一些事情）。选择随机 HashMap 很简单，但是我应该如何从这个 HashMap 中选择一个随机键呢？

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

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

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

4

10 回答 10

28

从我的头顶

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

那么就

map.get(keysAsArray.get(r.nextInt(keysAsArray.size()))
于 2012-09-12T09:44:39.217 回答
14

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

您需要的是第二个类似自定义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));
        indices.put(contents.get(index),index);
        contents.remove((int)(contents.size()-1));
        indices.remove(a);
     }
}
于 2012-09-12T10:58:26.107 回答
7

您需要访问基础条目表。

// 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)。

于 2012-09-12T10:36:25.343 回答
4

听起来您应该考虑将辅助键列表或真实对象（而不是地图）存储在您的列表中。

于 2012-09-12T09:42:02.927 回答
2

正如@Alberto Di Gioacchino 指出的那样，在接受的解决方案中存在一个带有删除操作的错误。这就是我修复它的方法。

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 item) {
         indices.put(item,contents.size());
         contents.add(item);
     }

     //removes element in constant time
     void remove(A item) {
        int index = indices.get(item);
        contents.set(index,contents.get(contents.size()-1));
        indices.put(contents.get(index),index);
        contents.remove(contents.size()-1);
        indices.remove(item);
     }
}
于 2021-04-29T03:25:59.883 回答
1

我假设您正在使用HashMap，因为您需要在以后查找一些东西？

如果不是这种情况，那么只需将您的更改HashMap为Array/ ArrayList。

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

或者，您可以使用 aTreeMap而不是HashMap吗？我不知道您的密钥是什么类型，但您TreeMap.floorKey()与一些密钥随机器一起使用。

于 2012-09-12T09:58:42.610 回答
1

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

顺便说一句，你的问题引导我，

这个示例IndexedSet可以让您了解操作方法。

[编辑]

如果您决定创建自己的模型，此类 SetUniqueList可能会对您有所帮助。它明确声明它包装了list，而不是副本。所以，我认为，我们可以做类似的事情，

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

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

于 2012-09-12T10:21:40.797 回答
1

从 Java 8 开始，有一种 O(log(N)) 方法和 O(log(N)) 额外内存：创建一个Spliteratorvia map.entrySet().spliterator()，进行 log(map.size())trySplit()调用并随机选择前半部分或后半部分. 当 a 中剩下的元素少于 10 个时Spliterator，将它们转储到列表中并随机选择。

于 2019-02-26T20:15:21.167 回答
0

在 Map 的另一个实现中包装 HashMap 怎么样？另一张地图维护一个列表，在 put() 上它会：

if (inner.put(key, value) == null) listOfKeys.add(key);

（我假设值的空值是不允许的，如果它们使用 containsKey，但这会更慢）

于 2012-09-12T19:54:50.163 回答
0

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

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

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

于 2012-09-12T10:40:01.773 回答