Bitcoinで使用されるハッシュ関数はmurmur3と呼ばれ、暗号学的に安全ではないが高速
以下のように定義される
i * 0xfba4c795 + tweak
murmur3
def murmur3(data, seed=0):
c1 = 0xcc9e2d51
c2 = 0x1b873593
length = len(data)
h1 = seed
roundedEnd = (length & 0xfffffffc)
for i in range(0, roundedEnd, 4):
k1 = (data[i] & 0xff) | ((data[i + 1] & 0xff) << 8) | \
((data[i + 2] & 0xff) << 16) | (data[i + 3] << 24)
k1 *= c1
k1 = (k1 << 15) | ((k1 & 0xffffffff) >> 17)
k1 *= c2
h1 ^= k1
h1 = (h1 << 13) | ((h1 & 0xffffffff) >> 19)
h1 = h1 * 5 + 0xe6546b64
k1 = 0
val = length & 0x03
if val == 3:
k1 = (data[roundedEnd + 2] & 0xff) << 16
if val in [2, 3]:
k1 |= (data[roundedEnd + 1] & 0xff) << 8
if val in [1, 2, 3]:
k1 |= data[roundedEnd] & 0xff
k1 *= c1
k1 = (k1 << 15) | ((k1 & 0xffffffff) >> 17)
k1 *= c2
h1 ^= k1
h1 ^= length
h1 ^= ((h1 & 0xffffffff) >> 16)
h1 *= 0x85ebca6b
h1 ^= ((h1 & 0xffffffff) >> 13)
h1 *= 0xc2b2ae35
h1 ^= ((h1 & 0xffffffff) >> 16)
return h1 & 0xffffffff
BIP37_CONSTANT = 0xfba4c795
from bloomfileter import BloomFilter, BIP37_CONSTANT
from helper import bit_field_to_bytes, murmur3
field_size = 10
function_count = 5
tweak = 99
items = (b'Hello World', b'Goodbye!')
bit_field_size = field_size * 8
bit_field = [0] * bit_field_size
for item in items:
for i in range(function_count):
seed = i * BIP37_CONSTANT + tweak
h = murmur3(item, seed=seed)
bit = h % bit_field_size
bit_field[bit] = 1
print(bit_field_to_bytes(bit_field).hex())
def add(self, item):
for i in range(self.function_count):
seed = i * BIP37_CONSTANT + self.tweak
h = murmur3(item, seed=seed)
bit = h % (self.size * 8)
self.bit_field[bit] = 1
