Java中使用TreeMap权重随机算法，以及验证与分析

权重下随机，就是给定各个值不同的权重，再根据权重的比例随机选出一个值

 1 /**
 2  * Created by Jungle on 2020/2/23.
 3  *
 4  * @author JungleZhang
 5  * @version 1.0.0
 6  * @Description 权重下随机的算法
 7  */
 8 public class WeightRandom<K, V extends Number> {
 9     private TreeMap<Double, K> weightMap = new TreeMap<>();
10 
11     public WeightRandom(@NotNull List<Pair<K, V>> list) {
12         // 先排除权重为0的项
13         Iterator<Pair<K, V>> it = list.iterator();
14         while (it.hasNext()) {
15             if (it.next().second.doubleValue() == 0) {
16                 it.remove();
17             }
18         }
19 
20         for (Pair<K, V> pair : list) {
21             double lastWeight = this.weightMap.size() == 0 ? 0 : this.weightMap.lastKey();// 统一转为double
22             this.weightMap.put(pair.second.doubleValue() + lastWeight, pair.first);// 权重累加
23         }
24     }
25 
26     public K random() {
27         double randomWeight = this.weightMap.lastKey() * Math.random();
28         SortedMap<Double, K> tailMap = this.weightMap.tailMap(randomWeight, false);
29         return this.weightMap.get(tailMap.firstKey());
30     }
31 
32 }

算法验证：

 1 /**
 2  * Created by Jungle on 2020/3/31.
 3  *
 4  * @author JungleZhang
 5  * @version 1.0.0
 6  * @Description
 7  */
 8 public class WeightRandomTest {
 9 
10     @Test
11     public void test() {
12         Pair<String, Integer> pair1 = new Pair<>("1", 1);
13         Pair<String, Integer> pair2 = new Pair<>("2", 2);
14         Pair<String, Integer> pair3 = new Pair<>("3", 3);
15         Pair<String, Integer> pair4 = new Pair<>("4", 4);
16         List<Pair<String, Integer>> list = new ArrayList<>();
17         list.add(pair1);
18         list.add(pair2);
19         list.add(pair3);
20         list.add(pair4);
21         WeightRandom<String, Integer> random = new WeightRandom<>(list);
22 
23         String num;
24         HashMap<String, Integer> totalCount = new HashMap<>();
25         for (int i = 0; i < 10000000; i++) {
26             num = random.random();
27             if (totalCount.containsKey(num)) {
28                 totalCount.put(num, totalCount.get(num) + 1);
29             } else {
30                 totalCount.put(num, 1);
31             }
32         }
33         System.out.println(totalCount.toString());
34 
35     }
36 }

运行1000w次，结果

{1=1000402, 2=1998608, 3=3000011, 4=4000979}

{1=1001041, 2=1999736, 3=3000950, 4=3998273}

{1=1000074, 2=1999378, 3=3000471, 4=4000077}

{1=1001806, 2=2001035, 3=3000200, 4=3996959}

{1=1000215, 2=2001900, 3=2995226, 4=4002659}

从结果上看，基本上满足了根据权重随机出的数据正确

这里使用TreeMap的tailMap()方法的特性，可以选出比该key值大的所有键值对

通过

1         for (Pair<K, V> pair : list) {
2             double lastWeight = this.weightMap.size() == 0 ? 0 : this.weightMap.lastKey();// 统一转为double
3             this.weightMap.put(pair.getValue().doubleValue() + lastWeight, pair.getKey());// 权重累加
4         }

这个方法，把值分段，比如例子中会分成（1:1）（3:2）（6:3）（10:4）这四个键值对

使用

1 weightMap.lastKey() * Math.random()

可以得到一个权重累加值得随机数，最后根据tailMap() 得到第一个比权重随机数大的key值，这个key值就是我们随机到的值

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Create by JungleZhang on 2020年3月31日17:29:28