liveBook · Manning

Hash function

As explained in Algorithms Every Programmer Should Know

A hash function deterministically maps input data, such as a key, to an index or hash value.

A hash function deterministically turns an input key or string into a value, often an index or a number that can be compared quickly. In a hash map, the value helps locate a key; in Rabin–Karp, it represents a pattern or text window. section 1.4.1 section 4.0

The result depends on the function: different inputs can produce the same hash, a collision. In string searching, a hash match is only a candidate match, so compare the actual characters to rule out false matches. section 4.1 section 4.4

A collision in string matching

A simple addition-based hash can give ACT and CAT the same value. Giving characters different positional weights, such as powers of 10, reduces this collision; a rolling hash then updates the window’s value as characters enter and leave. section 4.4 section 4.1

Figure 4.4 Two substrings previously with a simple hash function yield the same hash value. When the hash function is changed using powers of 10, the same two substrings yield different hash values. This reduces the problem of collision.

Compare how a simple hash collides and how positional weights distinguish the substrings. section 4.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Explains numeric character mapping, collisions, verification, and rolling updates through worked string-search examples.
Examples
Uses alphabet-number mappings, the JOE pattern, ACT/CAT collisions, and character frequencies in hash maps.
What you can do after
Apply a rolling hash to compare pattern and text-window values, verify hash matches, and return match positions.
How it connects
Connects hash functions to hash maps, Rabin–Karp, rolling hashes, sliding windows, and hash collisions.

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 Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.