【学习】Count-Min Sketch 算法，解决大数据统计难题

如果老板让你统计一个实时的数据流中元素出现的频率，并且准备随时回答某个元素出现的频率，不需要的精确的计数，那该怎么办？

直觉告诉我们可能需要一个巨大的 HashMap 来统计各个元素的出现频率，但由于不同的元素的个数可能非常大，以至于是个天文数字，要求的内存可能会非常大，从而不切实际。同时，又要求我们实时计算，实时回答，当HashMap的冲突很高时，最坏的情况的时间复杂度可能无法满足实时的要求。

加上前面要求不需要精确的计数，这么说来，必须寻找新的算法。

那么，Count-Min Sketch 就是用来解决此类问题的算法。

这个算法的技巧是：

不存储所有的不同的元素，只存储它们Sketch的计数。

基本的思路是这样的：

创建一个长度为 x 的数组，用来计数，初始化每个元素的计数值为 0；

对于一个新来的元素，哈希到 0 到 x 之间的一个数，比如哈希值为 i，作为数组的位置索引；

这是，数组对应的位置索引 i 的计数值加 1；

那么，这时要查询某个元素出现的频率，只要简单的返回这个元素哈希望后对应的数组的位置索引的计数值即可。

原文链接：

https://mp.weixin.qq.com/s/YfQDlhK8xN05ko0NqOvXlw