最近在菜鸟教程上自学redis。看到Redis HyperLogLog的时候，对“基数”以及其它一些没接触过（或者是忘了）的东西产生了好奇。
于是就去搜了“HyperLogLog”，从而引出了Cardinality Estimation算法，以及学习它时参考的一些文章：
http://blog.codinglabs.org/articles/algorithms-for-cardinality-estimation-part-i.html
从文章上看来，基数是指一个集合（这里的集合允许存在重复元素，与集合论对集合严格的定义略有不同，如不做特殊说明，本文中提到的集合均允许存在重复元素）中不同元素的个数。
这就类似“求一个数组中不重复元素的个数”的算法。如数组a[10] = {1，2，3，4，1，2，3，4，5，6，7}，那么不重复元素就是{1，2，3，4，5，6，7}，一共7个。对于它的应用场景，比如一个网站要统计“一个人”的访问次数的时候，比如小明，那么就给对“小明”打上标记，当它下次来访问的时候，总访问次数不能加一。只有当不是“小明”的人，比如“小丽”来访问，对将总访问次数加一。
这又好像之前做过的一题算法题：统计字符串“abcdaaabceeda”中不重复的字母的个数了。当然，最简单粗爆的方法就是去一次又一次地遍历，如：判断第n个字符是否有出现过，先对前n-1个字符进行遍历比较。这样的话也太浪费时间了。于是，当时我想了一个办法：字符串中只有字母，只要建一个长度为26的哈希表，然后遍历一次字符串，把读到的字符填进哈希表中，最后遍历哈希表就可以了：
hash.c
#include <stdio.h>
#include <string.h> int main()
{
char str[] = "abcdaaabceeda";
int hash[] = {};
int size = strlen(str);
int i;
for(i = ; i < size; ++i)
{
int temp = str[i] - 'a';
++hash[temp];
}
int num = ;
for(i = ; i < ; ++i)
{
num += hash[i] > ? : ;
}
printf("num = %d\n", num);
}
如果只统计26个小写字母，只需要26个int型空间。想到bitmap可以节约空间，于是也用它写了一个：
bitmap.c
#include <stdio.h>
#include <string.h> int hamming_weight(unsigned int bitmap)
{
unsigned int temp = bitmap;
temp = (temp & 0x55555555) + ((temp & 0xaaaaaaaa) >> );
temp = (temp & 0x33333333) + ((temp & 0xcccccccc) >> );
temp = (temp & 0x0f0f0f0f) + ((temp & 0xf0f0f0f0) >> );
temp = (temp & 0x00ff00ff) + ((temp & 0xff00ff00) >> );
temp = (temp & 0x0000ffff) + ((temp & 0xffff0000) >> );
return temp;
} int main()
{
char str[] = "abcdaaabceeda";
unsigned int bitmap = ;
int size = strlen(str);
int i;
for(i = ; i < size; ++i)
{
int loc = str[i] - 'a';
int temp = << loc;
bitmap |= temp;
}
printf("num = %d\n", hamming_weight(bitmap));
}
区别就是用hash还可以统计单个字符出现的次数，而bitmap可以用到hamming weight来统计总次数，且节省了大量空间。
对于网站统计“小明”等人的访问次数的问题，其实相当于要把“小明”传入哈希函数，然后找到相应地址，标记为“已访问”。要统计的时候，根据哈希表的数据结构进行遍历，或是计算bitmap中1的个数等方法来统计。以上是我的个人见解，不涉及概率等实现问题。