Skip to content

Instantly share code, notes, and snippets.

@p7g
Created September 16, 2019 22:06
Show Gist options
  • Save p7g/5439d67369245a00a6d964df0dbb7670 to your computer and use it in GitHub Desktop.
Save p7g/5439d67369245a00a6d964df0dbb7670 to your computer and use it in GitHub Desktop.
A hashmap implemented in python
FNV_PRIME_64 = 1099511628211
FNV_OFFSET_BASIS_64 = 14695981039346656037
def hash(s: str) -> int:
val = FNV_OFFSET_BASIS_64
for c in s:
val ^= ord(c)
val *= FNV_PRIME_64
return val
class HashMap:
LOAD_FACTOR = 0.7
@staticmethod
def _entries(buckets):
for bucket in buckets:
if not bucket:
continue
for e in bucket:
yield e
def __init__(self):
cap = 8
self._cap = cap
self._load = 0
self._buckets = [None] * cap
def _hash(self, k):
return hash(k) & self._cap - 1
def _grow(self):
self._cap <<= 1
oldbuckets = self._buckets
self._buckets = [None] * self._cap
self._load = 0
for k, v in HashMap._entries(oldbuckets):
self.set(k, v)
def get(self, key):
hashed = self._hash(key)
bucket = self._buckets[hashed] or []
for k, v in bucket:
if k == key:
return v
return None
def set(self, key, value):
hashed = self._hash(key)
bucket = self._buckets[hashed]
if not bucket:
bucket = []
self._load += 1
self._buckets[hashed] = bucket
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (k, value)
return
bucket.append((key, value))
if self._load / self._cap > self.LOAD_FACTOR:
self._grow()
def delete(self, key):
hashed = self._hash(key)
bucket = self._buckets[hashed]
if not bucket:
return False
for i, (k, _) in enumerate(bucket):
if k == key:
bucket.pop(i)
if len(bucket) == 0:
self._buckets[hashed] = None
self._load -= 1
return True
return False
def entries(self):
return HashMap._entries(self._buckets)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment