如何从Java中的HashMap中选择随机密钥？

一尘不染

如何从Java中的HashMap中选择随机密钥？

java

我正在使用large
ArrayList<HashMap<A,B>>，并且我将反复需要从随机HashMap中选择一个随机密钥（并对其进行处理）。选择随机的HashMap很简单，但是我应该如何从此HashMap中选择一个随机密钥呢？

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

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

注意： 试探法很好，因此，如果有一种方法排除了1％的元素（例如，由于多个填充的桶），那根本没有问题。

阅读 302

2020-12-03

共1个答案

一尘不染

我设法找到一个解决方案，而不会降低性能。我将其张贴在这里，因为它可能对其他人有帮助-并可能回答有关此主题的几个未解决的问题（我将在以后搜索）。

您需要的是第二个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));
         contents.remove(contents.size()-1);
         indices.set(contents.get(contents.size()-1),index);
         indices.remove(a);
     }
}

2020-12-03