本文介绍了如何从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中选择一个随机密钥?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-23 14:37