布隆过滤器之C++实现

C++实现的布隆过滤器，其中使用到的bitset也是自己简单实现的一个BitContainer。可以处理千万条到亿条记录的存在性判断。做成dll可以在很多场合使用，如自己写爬虫，要判断一个url是否已经访问过，判断一个单词是否在某个字典内，当集合很大的时候，用布隆过滤器很有优势，不过使用前，请了解它的优缺点（缺点是有一定的误判率）

#include “bloomfilter.h“

typedef unsigned long ULONG;

ULONG BloomFilter::hashCode（const char* strint n）
{
	ULONG seeds[] = {1323314151617173798387}; //
	ULONG seed = seeds[n];
	ULONG hash = 0;

	while （*str）
	{
		hash = hash * seed + （*str++）;
	}

	return （hash & 0x7FFFFFFF）% _mem; //确保得到的值不会数组越界
}

bool BloomFilter::add（const char* str）
{
	if（NULL == str）
		return false;
	if（exists（str））
		return false;
	for（int i=0;i<_k;++i）
	{
		ULONG hcode = hashCode（stri）;
		_bitset.set（hcode）;
	}
	return true;
}

bool BloomFilter::exists（const char* str）
{
	bool result=false;
	if（NULL == str）
		return result;
	for（int i=0;i<_k;++i）
	{
		ULONG hc = hashCode（stri）;
		if（! _bitset.test（hc））
		{
			return result;
		}
	}
	return true;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        456  2011-11-20 11:00  test.cpp

     文件       1616  2011-11-20 09:51  bitcontainer.h

     文件        687  2011-11-20 10:38  bloomfilter.h

     文件        807  2011-11-20 10:37  bloomfilter.cpp

----------- ---------  ---------- -----  ----

                 3566                    4