在网上看到的:
1分钟内用户上线的数目是60万，如果用户在5分钟内重复上线，就给他发警告，问如何设计？
嗯，让我这个自以为是的不知天高地厚的家伙来看看该怎么设计。
嗯，首先确认的是,出题者应该是想考实际算法的，和应试者解决难题的方法，全方位思考问题的意识。所以”花600百万美刀花一套oracle的顶级牛B数据库然后把五分钟内的用户记录入库，连数据库查询“这样回答可能确实解决问题 不过不是出题想要的。
好吧，哪，准确地说，啥数据结构，啥算法?
让我们先想象数据容量和运算量。嗯,五分钟内可能有300万用户名要存储。这个嘛，不大，完全在单机范围之内，内存稍大的机呖器，就能全装下这个量级的用户名或id数据。再看时间要求:一分钟内要上线60万用户，每个用户上线时都要查询是否重复了，呀，这是一秒钟1万次查询。如果说是网络服务器的话，比如web这种效率低一点的服务，一万次每秒还是相当复杂的。不过如果是机器内运算1万次，嗯，还是可行的。
接下来，咱们要看是最麻烦的部分，也是要点一:如何应对一秒内完成一万次对该用户是否在五分钟后上线过的查询。这实际是一个要查询一个数据是否在一个列表中存在的问题。嗯，当然我们可以挨个去比对,这个列表比对完了我们就知道这个数据是不是存在了。不过，做为搞软件开发的，大家都知道，如果这个列表能够事先排好序，那是最好不过了。好吧，让我们确定一点:我们最好应该将某一时间的用户名排个序。
接下来我们假定我们把每秒钟内上线的1万个用户放在一个桶里，然后对该秒中的所有用户按名字排序，从小到大或都是从大到小，都行。现在我们时间每推进一秒，我们就噌地新建建一桶，这一秒时间内的新增的一万用户呀，就存这个桶里了。嗯，做为开发者，实际情况是，我们一始就建了300秒这么多桶，申请了大小为300的内存块。然后每块内存里要能有足够容纳一万个用户的内存大小。
嗯，每当时间的车轮进入新的一秒，我们就去这300个中间去找到已经过期的那一“秒“，给它打上当前时间标记，嗯，把它个1万个用户数据清空。每进来一个用户，我们就丢进去，让它们按用户名大小排队。
每一个新用户上线时，我们都需要向这个300个桶发出查询请求。嗯，学过二分法的话，就应该知道，一万个排好序的数据，要查询是否包含某一数据只需要log10000就行了，啊，大概是14次查找。嗯，比你一万个挨个查好了吧，那可是1万次查找啊。
再接下来，我们再思考一下，检查一下:如果是实际场景的话，我们用户们可能不那么听话，每分钟内的60万用户未必刚好平均分配到一秒一万。嗯，而且就跟电灯炮一般能承受的电压都不是220v,而会高出不少，比如250v也能工作，180v也能点亮。比如，明天突然出了个重大新闻，一秒钟内涌进了13000名用户，那我们这么桶的大小就不能承受了。这个，我们做一点点改进，因为二分法最多反正也得比较14次，我们就以2的14次方做为桶大小。如果再还不能承受，那就在用户超出时2的14次方时单独再申请内存。
嗯，这样看上去好多了，不过，排序也是一个比较繁琐的过程，嗯。假设这样一个场景….算了，直接说吧。对于这种从一堆数据中查询是否存在某一个数据的做法，有一个算法叫布隆算法，可以google 一下bloom algorithm或是bloom filter,就专门干这些事。布隆算法做这个查询会有误差，比如，有的用户明明是没有登陆，可是却被提示重复登陆了。这个误差机率我们是可以计算的。
接下来我们可以试际测试一下，看看单机测试的结果。如果实在还不行，那就需要把这300个秒上的数据分布到几台机器上去计算。比如每分钟内的时间分在一台机器上…
有的哥们是这样考虑的:
做一个长度为300的循环链表，每个链接项的数据是一个hashtable,这样来判断。也是删掉过期数据。我觉得这样难度挺大的，因为这样每秒种进1万个用户，对300个链表项中每一个项的1万个数据都要做比较，大致相当于一秒内做了10k*300*10k次比较。我的印象中，就是一亿次for循环,每个循环基本上啥也不干，这个时间，也应该在一秒左右。我偷了下懒， 用c写了个简单的测试:
| 以下是代码片段： #include “stdlib.h” #include “stdio.h” int main(int argc,void ** argv){ int i=0; int j=10000*10000*3; for(;i } printf("done"); } |
编译后:
| 以下是引用片段： $time ./a.out done real 0m1.363s user 0m1.268s sys 0m0.008s |
如果再100倍，时间就远超出1秒了。还没有做其他事情呢。我用的是10000*10000*3是因为，如果是10000*10000*300，就溢出了。
不过至于究竟分桶排序后效率如何，也还不好说。没有实战。只是我凭经验觉得一秒钟几百亿次比较是不靠谱的。嗯，不知道有没有时间写个程序验证一下。