大致伪代码如下： int count = 1; string query[m+1]; //为了方便理解，从1开始存 while(scanf("%s",&cur_query)!=EOF) { count++; if(count <= m) { // 如果输入小于m，直接存。 query[count] = cur_query; } else { // 剩余的，就随机一个数，并交换。具体为何，在下述证明可见 int M = random(1, count); if( M < m) { query[M] = cur_query; } } 证明每个query被抽中的概率相等：（假设总请求量为N） 1. 如果N<=m，每个query都被存下来，那么query被抽中保存下来的概率均为1.所以相等 2. N > m. 将query分成前m个和后m个来看（其实也就对应伪码中if/else 两种处理方式） 对于第i个数(i < m)，在前m步被选中的概率仍是1.但是从第m+1步，i就有可能被替换掉，被替换掉的概率是 1/count。第m+1步，count = m+1,所以不被替换的概率为m/m+1。接下来的也就是m+1/m+2、m+2/m+3 。 那么读到第N个数时， 显然第i个数被选中的概率 = 每一步都不替换的概率,即  m/m+1 * m+1/m+2  … n-1/n = m/n 对于第i个数(i >= m)时。要想被选中的概率为，首先，在它出现的那一次，M取值要