liveBook · Manning

Hash function

As explained in The Coder Cafe

A hash function is a function that maps input data to a value in a hash space, commonly used to determine positions in a data structure.

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

How The Coder Cafe covers it

How deep it goes
Explains mapping, collisions, bloom-filter operations, deletion limits, and multiple-hash tradeoffs, including O(k·n) operation cost.
Examples
Demonstrates keys D, A, and C in a hashmap and elements “foo,” “bar,” “qux,” and “baz” in bloom filters.
What you can do after
Evaluate hash-based structures by comparing memory use, collision behavior, false positives, deletion support, and lookup cost.
How it connects
Connects hash functions to hashmaps, hashsets, linked lists, bitvectors, bloom filters, collisions, and false positives.

Also explained in

Compare how 19 books explain hash function →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of The Coder Cafe. The section links point to the parts of the book it draws on.