Skip to content

Instantly share code, notes, and snippets.

@darkf
Created October 11, 2015 11:51
Show Gist options
  • Save darkf/e91d1e746ee39b184bbb to your computer and use it in GitHub Desktop.
Save darkf/e91d1e746ee39b184bbb to your computer and use it in GitHub Desktop.
Simple Python hash table and Bloom filter
def sillyhash(x):
return x % 16
class BloomFilter:
SIZE = 32
HASH_FNS = [hash, sillyhash]
def __init__(self):
self.n = BloomFilter.SIZE
self.bitset = [0]*self.n
def hashes(self, x):
return map(lambda f: f(x), BloomFilter.HASH_FNS)
def add(self, x):
for hash in self.hashes(x):
self.bitset[hash % self.n] = 1
def __contains__(self, x):
return all(self.bitset[hash % self.n] for hash in self.hashes(x))
bf = BloomFilter()
bf.add(1)
bf.add(8)
bf.add(42)
bf.add(64)
bf.add(10225)
bf.add(123)
print(1 in bf)
print(8 in bf)
print(42 in bf)
print(64 in bf)
print(10225 in bf)
print(123 in bf)
# not
print("")
print(256 in bf)
print(1253 in bf)
print(1253 in bf)
print(156 in bf)
print(41 in bf)
print(bf.bitset)
class HashTable:
NUM_BUCKETS = 8
def __init__(self):
self.n = HashTable.NUM_BUCKETS
self.buckets = [[] for _ in range(self.n)]
def __getitem__(self, key):
for k, v in self.buckets[hash(key) % self.n]:
if k == key:
return v
raise KeyError(key)
def __setitem__(self, key, value):
bucket = self.buckets[hash(key) % self.n]
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
ht = HashTable()
ht[3] = 10
ht["lol"] = "bazar"
ht["lol"] = "bizarre"
ht["fuu"] = "quuz"
ht[123] = 20
print(ht.buckets)
print(ht["lol"])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment