当前位置: 首页 > 面试题库 >

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

郎成弘
2023-03-14
问题内容

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

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

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

注意: 试探法很好,因此,如果有一种方法排除了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);
     }
}


 类似资料:
  • 微调器板条箱有一个枚举,其中包含大量可能的微调器。 这是枚举(跳过除顶部和底部4之外的所有值): 新微调器易于创建: 但是,我希望随机选择一个微调器,这是行不通的: 因为: 如何随机选择枚举值,并使用该值显示随机微调器?

  • 问题内容: 我可以使用列出所有组合, 但这通常会很大。 给定和,我如何在不首先构建大量列表的情况下随机地均匀选择组合? 问题答案: 来自http://docs.python.org/2/library/itertools.html#recipes

  • 我对任何逻辑都不熟悉,正在尝试构建一个基于代理的模型,该模型随机地将代理(车辆)从起点(地理信息系统地图上的家庭位置点)引导到选定的位置。我有6组不同的集合,其中存储了不同的位置(学校集合、超市集合、购物中心集合、医院集合、旅游集合和工作办公室集合)。 在我的车辆状态图中,我指示它访问4个位置。到目前为止,我只能在每次转换中使用:moveTo(随机来自(主。医院集合))使代理移动到其中一个集合中的

  • 问题内容: 我想从集合中选择一个随机项目,但是选择任何项目的机会应与相关的权重成比例 输入示例: 因此,如果我有4种可能的物品,那么没有重量的任何一件物品的机会将是四分之一。 在这种情况下,用户遭受痛苦之剑的可能性应该是三刃剑的十倍。 如何在Java中进行加权随机选择? 问题答案: Apache Commons中现在有一个用于此的类: 这里是,像(假设Item接口阿恩的答案): 或在Java 8中

  • 问题内容: 我正在寻找从整数数组中随机选择数字的解决方案。 例如我有一个数组,如何随机选择一个数字? 问题答案:

  • 如何从列表中随机选择Kotlin科特林的颜色?我找不到任何与这个话题相关的东西...< br >谢谢。