CountMin Sketch

目的：在流计算的场景中，我们经常需要做Freq Counting，而普通的HashTable、Counted BF都有Linear的空间复杂度，CountMin Sketch能让你把性能降到Sub Linear，当然可能会有误差。
过程：
- 构建一个m * d的二维数组，每一行都有一个hash函数控制。
- 遍历（添加）每个元素时，算出d个0 - (m - 1)的hash value，对应d个槽自增下
- 如果要计算某个值的Freq，依然hash出那d个value，去对应槽中值最小的。
性质
- 很明显这个一个只会高估不会低估的过程，对于在长尾上的元素，很可能因为其他元素也映射到了一样的槽中，产生大量冲突，造成误差，所以也有Count-Min-Mean Sketch，这里就不介绍了，有兴趣的可以自己查阅相关资料。