背景：

   我现在在一个网站工作，每天都有很多网络爬虫和恶意攻击。我想根据http访问日志统计一下每个IP每天的访问次数，然后大于1万的都认为是机器人。现在寻求一个高效且实时的算法解决这个问题。

   最简单的做法，就是用一个map来记录所有IP的访问次数。那么这可能会需要几百兆的内存。有一个更好的办法，可以在O(1)的空间复杂度中解决这个问题。

   算法：

   我们用一个m 乘 k 的 二维数组来存放所有的计数值。此外，我们还需要m个两两独立的散列函数，每个散列函数将输入(即IP地址)散列到[0,k)范围内的整数。

   伪代码如下：

   int count[m][k];

   int c=INT_MAX;

   Object input ; // the ip;

   for(int i=0;i!=m;++i){

     int index=hash(i,input); //用第i个hash函数对input做hash。

     c= std::min(c,++count[i][index]);

   }

   if(c>10000) printf("catch one robot");

   由代码可以看出，每来一个input的时候，会同时增加m个计数器的值。一个更好的改进是，只增加这m个当中值最小的那个。例如7、5、4 变成 7、5、5。但是7、3、3必须变成7、4、4而不是7、4、3。

   分析：

   这是Bloom Filter的一个变种。原始的Bloom Filter算法中，hash对应的是0/1这样的一个bit。而此处把bit改成了一个整数。和Bloom Filter一样，它也存在假阳性的问题，就是，有些IP明明没有访问那么多次，但是我以为它有。降低假阳性率的方式就是提高m和k的数值。同时，和Bloom Filter一样，hash函数的选择也很关键。如果你把hash函数看成是带参数的随机变量，那么它应该尽可能的在值域中均匀、且相互独立。

   相关问题：

   问题一：

   来自《编程之美》这本书，号称是微软面试题。

   假设我给你的是员工的签到签退记录，里面每一行是时间戳和员工号。每个人应该每天有2次记录。已知今天有人只签了一次(只有一人！)，我想让你查一下这个人是谁。要求，空间复杂度是O(1)，时间复杂度是O(n)。

   问题二：

   原题中，假如我要统计的不是访问次数，而是in/out流量。找出流量最大的IP，该怎么办？