从哈希映射中随机获取值

Question

我有一个类型为<T,Integer>的哈希表。T是一个通用类型。

T可以是任何对象，整数是我们当前在映射中拥有该对象的数量。

例如，一个字符串"shirt"，它对应的值是3。

我想建立一个名为random的方法，根据当前对象的分布情况从映射中返回一个随机对象。

也就是说，如果我的映射中有2个键..."Shirt"和"Pants"。我的映射中有3个"Shirts"和7个"Pants"。分布应该是30%的时间返回一个shirt，70%的时间返回"Pants"。

如何使用随机生成器实现这样的功能呢？

- Coder_Moler10345

---

你能否提供你当前的源代码？你尝试了什么？ - Charles

Answer 1

那种映射数据类型使得实现您的要求变得非常困难。更好的数据结构将使它变得更容易。有各种可能的数据结构可以优化不同的事情。

少量不同值/值计数的解决方案

如果您经常需要选择随机值，并且没有太多不同的值/值计数，那么以下解决方案非常有效：

如何使用简单的 List<T> ？

// Calculate this in advance
List<T> values = 
map.entrySet()
   .stream()
   .flatMap(entry -> Stream.generate(() -> entry.getKey())
                           .limit(entry.getValue()))
   .collect(Collectors.toList());

根据您的例子，这个数组现在将包含3个 "Shirts" 的副本和7个 "Pants" 的副本。

现在很容易根据您想要的概率分布随机选择一个值：

SecureRandom random = new SecureRandom();
T randomValue = values.get(random.nextInt(values.length));

证明：

Map<String, Integer> result = new HashMap<>();
for (int i = 0; i < 100000; i++)
    result.compute(values.get(random.nextInt(values.length)), 
                  (s, j) -> j == null ? 1 : j + 1);

System.out.println(result);

…产生：

{Shirts=29955, Pants=70045}

- Lukas Eder

---

是的，这是正确的，但我的哈希映射使用泛型。因此，它不一定总是字符串。此外，HashMap 可能有多达 100,000 个或更多对象的大小。因此，制作一个数组（我之前考虑过）似乎非常低效。 - Coder_Moler10345

@Coder_Moler10345：好的，我修复了泛型部分。如果有人认为这种方法可行，我会在这里留下答案。我建议您更新您的问题并提供更多具体信息，否则您将无法得到您要寻找的答案。 - Lukas Eder

Answer 2

如果地图中包含（虚拟）3件衬衫和7条裤子，则表示该地图总共有10个元素。

遇到衬衫的概率为3 /（7 + 3）= 0.3

遇到裤子的概率为7 /（7 + 3）= 0.7

现在，想象一下您可以从0.0到1.0掷骰子。 如果骰子显示0.0到0.3之间的数字 ->选择一件衬衫。 如果骰子显示0.3到1.0之间的数字 ->选择一条裤子。

以下代码实现了这个想法：

private static <T> T randomBasedOnOcurrenceDistribution(Map<T, Integer> map) {
    SecureRandom random = new SecureRandom();
    double total = map.values().stream().mapToInt(Integer::intValue).sum();
    double dice = random.nextDouble();
    double floor = 0.0;

    for (Entry<T, Integer> entry : map.entrySet()) {
        double currentProbability = entry.getValue() / total;
        if(dice < floor + currentProbability) {
            return entry.getKey();
        }
        floor += currentProbability;
    }
    throw new RuntimeException("Unreachable");
}

使用方法（摘自@Lukas的回答）：

Map<String, Integer> map = new HashMap<>();
map.put("Shirt", 3);
map.put("Pant", 7); 

Map<String, Integer> result = new HashMap<>();
for (int i = 0; i < 100000; i++)
       result.compute(randomBasedOnOcurrenceDistribution(map), 
                     (s, j) -> j == null ? 1 : j + 1);

System.out.println(result); //prints {Pant=69679, Shirt=30321}

- Spotted

---

如果两个项目具有相同的概率，会发生什么情况呢...例如，我现在有5个项目：衬衫 = 3，裤子 = 4，内衣 = 3，背心 = 1和袜子 = 6。 - Coder_Moler10345

在这种情况下，有两个具有相同概率的项。那么我如何确保这些项目具有相同的权重或被选中的机会相同呢？ - Coder_Moler10345

@Coder_Moler10345 如果两个项目的概率相同，则它们被选中的机会是相等的。你尝试过用更多的项目运行我的代码吗？ - Spotted