![selecting]( "selecting")
本文介绍了如何从Java中的HashMap中选择一个随机密钥？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我正在处理一个大的 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中选择一个随机密钥？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！