• 实时输出从当前时间向前数的1个小时的top k （问题原链接）

• QPS可能会达到10W/s

• 稍微解释一下问题：QPS=10W/S的意思是每秒可能会有10W次的IP访问数据，因此每小时最多的log数量是：360,000,000

  如果要做到实时的话，还有一个窍诀，在当前时刻重放之前一个小时这个时刻发生的log，但是要-1，于是就能知道实时的一个小时的数据了。

我专门针对这个问题做过论文的研究。有很多的方法可以解决这个问题。得看是否允许损失精度。

一般来说，实际的运用，都是允许损失精度的，也就是有一定概率找得不准，但是这个概率很低。

有这么几个算法可以解决这个问题，有兴趣的同学搜一下论文，基本都是O(k)空间和realtime的。k是你要找top-k的。

• Lossy Counting
• Space Saving
• Sticky Sampling
• Efficient Counting
• Hash Count

还有很多这方面的算法，我没举完。我比较喜欢的是Space-Saving和Hash Count（还有一个算法是Hash Count 2），以Hash Count算法为例子。这个做法特别简单就是用一个Hash表，但是不存Key，只存value（一个数组就搞定了），然后每个key过来，我就算出对应的hashcode是什么（一个index呗），去hash表里找对应的位置，count++。这个方法听起来就是，如果两个key有同样的hashcode，然后count就会被叠加到一起，但是实际上你要找的top-k的k是很小的，比如10，所以基本上对最后结果有影响的概率也是很小的。所以这种方法是我认为最实用的方法。

有兴趣的同学可以搜索“Top-k Frequently Elements”或者类似的关键词来查找相关的论文。