# Count-Min Sketch（A）

![left](./student-guide/diagram/18-Count-Min-Sketch-01-01.png)

-------------------------------------------------------------
1. 数据结构目的：统计一个实时的数据流中元素出现的频率，并且可以实时回答出某个元素出现的频率，不需要的精确的结果。

2. 基本思路：
创建一个长度为 x 的数组，用来计数，初始化每个元素的计数值为 0；
对于一个新来的元素，哈希到 0 到 x 之间的一个数，比如哈希值为 i，作为数组的位置索引；
这是，数组对应的位置索引 i 的计数值加 1；

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

4. 优化：
考虑到使用哈希，会有冲突（哈希碰撞），即不同的元素哈希到同一个数组的位置索引，这样，频率的统计都会偏大。所以还需要做如下优化：
使用多个数组，和多个哈希函数，来计算一个元素对应的数组的位置索引；
那么，要查询某个元素的频率时，返回这个元素在不同数组中的计数值中的最小值即可。