刚好看到了记录一下：
“给出一个数据流，这个数据流的长度很大或者未知。并且对该数据流中数据只能访问一次。请写出一个随机选择算法，使得数据流中所有数据被选中的概率相等。”
首先，我们考虑从n个对象中等概率的选取1个对象。如果我们知道n的值，那么只需要从0-n-1中随机一个数选取它就可以了，被选中的概率是1/n。
如果我们不知道n的值的时候，这个问题就转换成了一个蓄水池抽样问题，即我们总是选择第一个对象，以1/2的概率选择第二个，以1/3的概率选择第三个，
以此类推，以1/m的概率选取地m个对象，当该过程结束时，对每个对象具有相同选中的概率，均为1/n。
证明如下：
第m个对象最终被选中的概率P = 选择m的概率*后面所有的对象均不被选中的概率
伪代码如下： i = 0 while more input items with probability 1.0 / ++i choice = this input item print choice
Java代码如下：
将k个中的代码k=1即可。
对于选取K的对象，思路类似。首先把读到的前K个对象放入“水库”，从第k+1个对象开始对于第m个对象，以k/m的概率选取，并以1/k的概率替换水库中的一个对象（貌似替换水库中的一个对象就是1/k，因为只能替换一个嘛），当这个过程结束，每个被选中的概率均为k/n。其实选取一个就是k=1这个特例
证明如下：
第m个对象被选中的概率=选择m的概率*（其后元素不被选中的概率+其后元素被选中*不替换已经在水库中的m的概率）
伪代码如下： array S[n]; //source, 0-based array R[k]; // result, 0-based integer i, j; // fill the reservoir array for each i in 0 to k - 1 do R[i] = S[i] done; // replace elements with gradually decreasing probability for each i in k to n do j = random(0, i); // important: inclusive range if j < k then R[j] = S[i] fi done java代码：
public static int[] doReservoirSampling(int[] source, int k){ int[] result = new int[k]; int index = -1; for (int i : source) { ++index; if (index < k) { //将前k项先保存进结果数组中 result[index] = source[index]; continue; } int j = random.nextInt(index + 1);//生成随机数 下标是从0开始，但是概率是从1开始计算的 if (j < k) { //一共可以产生0-index 这么多数，其中0到k-1都可以满足条件，这样概率就是k/index+1 result[j] = source[index]; } } return result; } 测试结果（10000次）：
K=1的时候：
total used : 0ms 1 : 993 2 : 1000 3 : 968 4 : 988 5 : 990 6 : 990 7 : 1072 8 : 1039 9 : 950 10 : 1010
K=5的时候：
total used : 15ms 1 : 4959 2 : 5007 3 : 4968 4 : 5077 5 : 4964 6 : 4926 7 : 5037 8 : 4974 9 : 5088 10 : 5000
参考链接：
http://blog.jobbole.com/42550/
http://blog.csdn.net/huagong_adu/article/details/7619665
