如何从 Java 中的 HashMap 中选择一个随机键? [英] How to select a random key from a HashMap in Java?

问题描述

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

I'm working with a large ArrayList<HashMap<A,B>>, and I would repeatedly need to select a random key from a random HashMap (and do some stuff with it). Selecting the random HashMap is trivial, but how should I select a random key from within this HashMap?

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

Speed is important (as I need to do this 10000 times and the hashmaps are large), so just selecting a random number k in [0,9999] and then doing .next() on the iterator k times, is really not an option. Similarly, converting the HashMap to an array or ArrayList on every random pick is really not an option. Please, read this before replying.

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

Technically I feel that this should be possible, since the HashMap stores its keys in an Entry[] internally, and selecting at random from an array is easy, but I can't figure out how to access this Entry[]. So any ideas to access the internal Entry[] are more than welcome. Other solutions (as long as they don't consume linear time in the hashmap size) are also welcome of course.

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

Note: heuristics are fine, so if there's a method that excludes 1% of the elements (e.g. because of multi-filled buckets) that's no problem at all.

推荐答案

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

I managed to find a solution without performance loss. I will post it here since it may help other people -- and potentially answer several open questions on this topic (I'll search for these later).

您需要的是第二个自定义 Set 类数据结构来存储键——而不是这里建议的列表.类似列表的数据结构要从中删除项目的成本很高.所需的操作是在恒定时间内添加/删除元素(以使其与 HashMap 保持同步)以及选择随机元素的过程.下面的类 MySet 正是这样做的

What you need is a second custom Set-like data structure to store the keys -- not a list as some suggested here. Lists-like data structures are to expensive to remove items from. The operations needed are adding/removing elements in constant time (to keep it up-to-date with the HashMap) and a procedure to select the random element. The following class MySet does exactly this

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

这篇关于如何从 Java 中的 HashMap 中选择一个随机键?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！