Hash Tables and Bloom Filters
Complexity
| Operation | Average | Worst | |-----------|---------|-------| | Insert / Search / Delete | O(1) | O(n) | | Space | O(n) | O(n) |
Worst case occurs when all keys collide (pathological hash function or adversarial input).
Hash Functions
def mod_hash(key: int, size: int) -> int:
return key % size # size should be prime
def poly_hash(key: str, size: int) -> int:
h = 0
for ch in key:
h = h * 31
[Description truncada. Veja o README completo no GitHub.]