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

问题描述

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

速度很重要（因为我需要这样做10000次，hashmaps所以只需在[0999]中选择一个随机数k，然后在迭代器k次上执行 .next（），这真的不是一个选项。 类似地，在每个随机选择中将HashMap转换为数组或ArrayList实际上不是一种选择。请在回复前阅读此内容。

技术上我觉得这应该是可能的，因为HashMap在内部将其键存储在 Entry [] 中，并且从数组中随机选择很容易，但是我无法确定了解如何访问条目[] 。因此，任何访问内部 Entry [] 的想法都值得欢迎。其他解决方案（只要它们不占用散列表大小的线性时间）也是受欢迎的。

注意：启发式是好，所以如果有一种排除1％元素的方法（例如因为多填充桶），那根本就没有问题。 解析方案

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

你需要什么是第二个自定义的 Set -like数据结构来存储密钥 - 不像这里提供的一些列表。像列表一样的数据结构要从中移除项目会很昂贵。所需的操作是在常量时间内添加/删除元素（以使其与HashMap保持同步）以及选择随机元素的过程。下面的类 MySet 完全是这样的

  class MySet< A> {
 ArrayList< A> contents = new ArrayList（）; 
 HashMap< A，Integer> indices = new HashMap< A，Integer>（）; 
 Random R = new Random（）; 
 
 //在常量时间内选择随机元素
 randomKey（）{
 return contents.get（R.nextInt（contents.size（）））; 
} 
 
 //在常量时间内添加新元素
 void add（A a）{
 indices.put（a，contents.size（））; 
 contents.add（a）; 
} 
 
 //在常量时间内移除元素
 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）; 
} 
} 
  

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?

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.

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.

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

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

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