还有一种经常使用的策略是bitmap. Bitmap本身也是一种hash-table, 只不过hash的结果恰好落在[0, sizeof_bitmap_in_bits]内. 因为hash到的每个slot只有一个bit,所以通常用作判断是否存在等bool型的问题.
例子, 已知40亿个不重复的unsigned int, 如何判断一个整数在不在这40亿个整数里面?
给定说unsigned int,其实是指定了元素的可能范围, [0, 2^32 – 1]中, 注意2^32=42,9496,7296, 大约是42亿.
判断存在与否, 一个bit就够了,而记录所有的uint32_t, 4GB/8=512MB的bitmap也就够了, 这年头,512内存的需求是很正常的.
和这个问题类似的一个问题:
已知一个web server的客户ip地址日志, 大约有40亿条记录, 如何判断某个ip地址是否在这个日志中?
这个问题由于有了上下文, 就要具体分析. 具体来说, 一个web server的访问记录不大可能是不重复的, 我们有理由假定许多记录都是重复的, 所以一个较小的hash-table就可以了. 当然,hash-table小了, 会导致准确度的下降, 因为这时候的hash函数不是单射了. 为了保证成功, 512MB的bitmap还是可以考虑的.
这个问题的一个变种:
2.5亿个uint32_t整数中, 寻找不重复的整数的个数.
1bit信息只能判断存在与否, 那么是否可以附加1bit的信息, 每个元素映射到2bit, 00表示不存在, 01表示出现1次, 10表示出现2次, 11表示更多, 则很容易就实现了.
这种做法可以换个思路来理解, 用两个bitmap来判断, 当bm1里面没有置位的时候,将bm1中对应的位置位; 当bm1中对应位置已经置位的时候, 就将bm2里面的对应位置置位. 最后, 只要找到在bm1而不在bm2的那些bit位就可以了.
这种问题也可以产生一些变种, 譬如在64bit已经普及的今天:
已知40亿个不重复的uint64_t, 如何判断一个uint64_t在不在这个集合里面?
在看这个问题之前, 先看一个更一般性的问题:
有一个proxy server的url访问记录, 大约有40亿条记录, 如何快速确定某个url是否在这个日志中?
url不好处理,可以先用cryptographic hash function做一个hash(注意这种hash与通常所说的hash-table的hash的区别, 由于cryptographic hash function的性质, 我们认为这种hash是抗碰撞的). MD5已经不行了, 目前我们可以假设160bit的SHA-1是抗碰撞的.
这就转化成了: 已知40亿个不重复的uint160_t, 如何判断一个uint160_t在不在这个集合里面?
对于以上问题, 由于可能的取值空间太大(2^64或者2^160),
直接bitmap内存肯定放不下了. 但是可以利用前面hash的思想, 将40亿个元素通过hash拆分到多个小文件(子集)中, 也即桶划分(区段划分). 具体拆分规则是这样的, 假设我们的hash规则是选取前k位, 那么将最多拆分成2^k个文件, 而每个文件至多有2^(64-k)个元素. ---- 事实上, 这种拆分还可以继续细化为多级的拆分, 譬如前3bit用作第一级目录名, 4-6bit用作第二级目录名, 7-10bit用作文件名…
当我们走了一遍拆分成2^k个小文件以后, 每个小文件都可以放到内存了, 剩下的就好办了. 每个小文件可以自身就是一个bitmap, 这样对于给定的元素, 找到它应该在哪个子集(小文件)里面, 然后把那个文件的内容拉到内存, whatever后续处理.
类似的思想也可以用于解决下面的这些相关问题.
已知有40亿个不重复的uint32_t整数, 如何快速找到一个整数, 不在这40亿个整数内?
已知有40亿个不重复的uint32_t整数, 如何找到它们的中位数?
第一个问题, 拆分以后, 必定有若干个子集中元素个数小于2^(64-k), 表明这个子集的区段里面, 是有不存在的元素的, 读入这个文件, 随便搞就行了.
第二个问题, 拆分以后, 可以统计各个区段的元素个数, 立刻可以知道中位数位于哪个子集, 搞到内存里, 很快就能找到了. 注: 读入该子集以后, 由于子集中元素个数已知, 转化为求一个n元素序列中第k大元素的问题, 这个问题可以用类似于qsort中partition的办法, 在线性时间内解决, 参见http://www.cnblogs.com/qsort/archive/2011/05/09/2041653.html
这里桶划分(区段划分)的思想并不新鲜, 譬如上面"判断一个uint64_t是否在某集合里面", 其实就是一个操作系统中线性地址是否已经映射的判断, 而操作系统中关于地址空间页表的分段管理(两级或三级页表), 就是上面的按区段划分的典型例子.