A hash function maps input data to a value in a hash space, commonly turning a key into a position in a data structure. Hashmaps use that position to store and retrieve key-value pairs efficiently. section 6.13.1
When different keys produce the same position, a hash collision occurs. One hashmap implementation handles collisions by storing the affected pairs in a linked list at that array index. A hashset uses the same idea when only key membership matters. section 6.13.1
Hashing keys in a bloom filter
A five-bit bloom filter hashes “foo” to index 2 and sets that bit to 1. Hashing “baz” to index 4 finds a 0, proving it is absent. If “qux” also hashes to index 2, the filter reports that it may be present because the collision hides which element set the bit. section 6.13.2
Hash functions support several practical tradeoffs:
- A bloom filter stores only hash-derived bits rather than the original elements, using less memory than a hashmap. section 6.13.1 section 6.13.2
- Bloom-filter collisions create false positives: a set bit shows that an element may be present, but a zero bit shows it is absent. section 6.13.2
- Multiple hash functions set and check multiple bit positions, reducing false positives while increasing insertion and lookup time. section 6.13.3
- Bloom filters cannot delete elements safely because resetting a shared bit could remove evidence for another element. section 6.13.2
Inspect the hashmap layout to see how a hashed key selects an array index and how collisions share a linked list. section 6.13.1


















