From b1f99bed6f0fbbe94e6a3161b49b3f225dec8374 Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Fri, 2 Nov 2012 18:33:50 -0400 Subject: Add a nTweak to bloom filters to tweak the seed. --- src/bloom.cpp | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) (limited to 'src/bloom.cpp') diff --git a/src/bloom.cpp b/src/bloom.cpp index e773bbbbd..65f9b021b 100644 --- a/src/bloom.cpp +++ b/src/bloom.cpp @@ -15,7 +15,7 @@ using namespace std; static const unsigned char bit_mask[8] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80}; -CBloomFilter::CBloomFilter(unsigned int nElements, double nFPRate) : +CBloomFilter::CBloomFilter(unsigned int nElements, double nFPRate, unsigned int nTweakIn) : // The ideal size for a bloom filter with a given number of elements and false positive rate is: // - nElements * log(fp rate) / ln(2)^2 // We ignore filter parameters which will create a bloom filter larger than the protocol limits @@ -23,14 +23,15 @@ vData(min((unsigned int)(-1 / LN2SQUARED * nElements * log(nFPRate)), MAX_BLOOM // The ideal number of hash functions is filter size * ln(2) / number of elements // Again, we ignore filter parameters which will create a bloom filter with more hash functions than the protocol limits // See http://en.wikipedia.org/wiki/Bloom_filter for an explanation of these formulas -nHashFuncs(min((unsigned int)(vData.size() * 8 / nElements * LN2), MAX_HASH_FUNCS)) +nHashFuncs(min((unsigned int)(vData.size() * 8 / nElements * LN2), MAX_HASH_FUNCS)), +nTweak(nTweakIn) { } inline unsigned int CBloomFilter::Hash(unsigned int nHashNum, const std::vector& vDataToHash) const { // 0xFBA4C795 chosen as it guarantees a reasonable bit difference between nHashNum values. - return MurmurHash3(nHashNum * 0xFBA4C795, vDataToHash) % (vData.size() * 8); + return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash) % (vData.size() * 8); } void CBloomFilter::insert(const vector& vKey) -- cgit v1.2.3