有一个流，源源不断地往外吐出球，我有个袋子，能装10个球，比如流现在吐到100个了，那么想做到之前每个球（1~100）进袋子的概率都是10/100. 比如流现在吐到1732个了，那么想做到之前每个球（1~1732）进袋子的概率都是10/1732. 比如流现在吐到3429个了，那么想做到之前每个球（1~3429）进袋子的概率都是10/3429.

先讲流程

前1~10个不用逻辑，直接进袋子，
假设有个随机函数f( i ), 可以等概率地返回1 ~i 中的某个数字，那我们就可以决定事情了
假设我现在吐出了第k号球，那么我调f（k），若返回的是1~10中的数，那么我就进袋子，这就做到了10/k的概率，那么袋子中10个数扔谁？ 10个数中等概率扔一个。

然后现在看比如吐到17号球了，问袋子中3号球存活的概率
当只有10个球的时候， 3号球存活的概率是百分之100，
当11号球浩劫来了，它有10/11的概率会进袋子，3号球被换出的概率是1/10，
10 / 11 1 / 10 = 1 / 11
那么3号球存活的概率是1 （1 - 1 / 11） = 1 10 / 11
当12号球来了，它有10/ 12的概率会进袋子，3号球被换出的概率是1/ 10,
10 / 12 1 / 10 = 1 / 12
1 - 1 / 12 = 11/ 12
那么3号球存活的概率是 1 10 / 11 11/ 12
接下来我们有理由相信，
3号球存活的概率是 1 10 / 11 11/ 12 12/13 13/ 14 14/ 15 15 / 16 * 16 / 17
约掉，那么3号球存活的概率就是10 / 17

然后现在看比如吐到17号球了，问13号球(i > 10) 进袋子的概率
调f（13）， 10 / 13 概率，它不用管淘汰谁，反正它必进袋子，接下来就是看当14号来的时候，13号存活下来的概率
1 - (10 / 14 1/ 10) = 13 / 14
所以13号球进袋子的概率就是 10 / 13 13/ 14
接下来就有规律了
10 / 13 13/ 14 14 / 15 15 / 16 16 / 17 = 10 / 17
所以13号球最终在袋子中的概率就是 10 / 17,
至此我们可以说每个球在袋子中的概率一定均等

应用场景

比如我有10亿+用户，然后要从中选出100个幸运观众，我有很多服务器，在中国，美国，巴西。。。。，
而且只有在纪念日登录的用户才能参加抽奖，一个用户无论你在那天登录了多少次，都只算一个名额，
如果不用蓄水池算法，我要所有服务器记录在那一天登录的名单，然后再用大机器去重，最终选出100个幸运观众，非常的麻烦。

如果用蓄水池算法呢？
,
如果你不是首次登录，那么你滚吧，
如果是首次登录，则看是第几个登录的用户，比如x，
那么你就以 100 / x 的概率进袋子，
那么就直接在发奖的时候公布这100个人，根本不用许多服务器之间同步这同步那的。
原来我需要收集很多信息，现在变成动态决定的了。

补充题 RandToRand

给你一个f( ) 函数（黑盒），等概率给你返回1~7中的数字，现在要你实现一个函数g（），你可以用f（）函数，要求你返回1~10中等概率的数字。

我们可以把f（）函数加工成等概率返回0 和1 的函数
只要返回的是7就重做，只要返回的是123，就认为返回的是0，只要返回的是456，就认为返回的是1，
```
现在我们的随机源就是0，1了
```
我们要实现1~10等概率返回，就相当于实现0 ~9等概率返回最后再加个1即可。
- 需要几个二进制位才能覆盖0~9 ？ 4个二进制位 - - - -
- 然后用这个-0， 1随机源去扔4次，就可以得到一个0 ~15中的数字，但我们要的是0 ~9 的咋办？
  - 没关系，只要你扔出的是10 ~ 15的就重做。 ```java // 这个结构是唯一的随机机制 // 你只能初始化并使用，不可修改 public static class RandomBox { private final int min; private final int max;
  // 初始化时请一定不要让mi==ma public RandomBox(int mi, int ma) { min = mi; max = ma; }
  
  // 13 ~ 17 // 13 + [0,4] public int random() { return min + (int) (Math.random() * (max - min + 1)); }
  
  public int min() { return min; }
  
  public int max() { return max; } }

// 利用条件RandomBox，如何等概率返回0和1 public static int rand01(RandomBox randomBox) { int min = randomBox.min(); int max = randomBox.max(); // min ~ max int size = max - min + 1; // size是不是奇数，odd 奇数 boolean odd = (size & 1) != 0; int mid = size / 2; int ans = 0; do { ans = randomBox.random() - min; } while (odd && ans == mid); return ans < mid ? 0 : 1; }

// 给你一个RandomBox，这是唯一能借助的随机机制 // 等概率返回from~to范围上任何一个数 // 要求from<=to public static int random(RandomBox randomBox, int from, int to) { if (from == to) { return from; } // 3 ~ 9 // 0 ~ 6 // 0 ~ range int range = to - from; int num = 1; // 求0～range需要几个2进制位 while ((1 << num) - 1 < range) { num++; }

// 我们一共需要num位
// 最终的累加和，首先+0位上是1还是0，1位上是1还是0，2位上是1还是0...
int ans = 0;
do {
    ans = 0;
    for (int i = 0; i < num; i++) {
        ans |= (rand01(randomBox) << i);
    }
} while (ans > range);
return ans + from;

} ```