Back to Study Material Data Structures and Algorithms

Hashing

Hashing is a technique that maps arbitrary-sized data to fixed-size values called hash codes or digests. A hash function takes an input, such as a string, ...

Hashing

The Concept of Hash Functions

Hashing is a technique that maps arbitrary-sized data to fixed-size values called hash codes or digests. A hash function takes an input, such as a string, number, or object, and deterministically produces an integer within a fixed range. The power of hashing lies in its ability to reduce potentially complex keys to simple array indices, enabling constant-time lookup operations.

A good hash function must satisfy several properties. First, it must be deterministic: the same input always produces the same output. Second, it must be fast to compute, ideally O(1) or O(key length). Third, it must distribute outputs uniformly across the output range to minimize collisions, where two different inputs produce the same output. Fourth, for cryptographic applications it must also be one-way and collision-resistant, though these extra requirements do not apply to hash tables in general programming.

A simple hash function for strings adds the ASCII values of all characters and takes the result modulo the table size. For example, the string cat has ASCII values 99, 97, and 116 summing to 312. With a table size of 10, the hash is 312 mod 10 equals 2. However, this simple function is poor because it ignores character order: act and cat produce the same hash. Better string hash functions multiply a running value by a prime base like 31 before adding each character, giving different positions higher different weights.

The polynomial rolling hash computes: hash equals (c0 times p to the n-1 plus c1 times p to the n-2 plus ... plus cn-1) mod M, where p is a prime base and M is the table size or a large prime. This function distributes strings well and is used in Rabin-Karp string search and Bloom filters.

Time complexity for computing a hash: O(k) where k is the key length. For integer keys, O(1).

Interview tip: when asked about hash functions, mention that a good hash function for strings should account for character position, not just character content. The polynomial rolling hash with a prime base is the standard production approach.

Hash Function Design Principles

Designing an effective hash function requires balancing several competing concerns: speed, uniform distribution, low collision rate, and for some applications, adversarial resistance. Understanding these design principles helps you both write custom hash functions and evaluate existing ones.

The avalanche effect is a desirable property: a small change in the input should produce a dramatically different hash output. If flipping one bit in the input flips roughly half the bits in the output, the function has good avalanche behavior. This reduces the chance that similar inputs collide, which matters in practice because real-world data is rarely uniformly distributed.

Multiplication-based hash functions exploit the fact that multiplying by certain large primes and shifting creates good bit mixing. The Knuth multiplicative hash multiplies the key by the golden ratio multiplied by 2 to the 32nd power (approximately 2,654,435,761) and keeps the top bits. This works well for integer keys.

FNV (Fowler-Noll-Vo) hash is a widely used non-cryptographic hash that initializes an offset basis and for each byte, XORs the byte into the hash and multiplies by a large prime. It is fast, has good distribution, and is easy to implement.

MurmurHash is a high-performance non-cryptographic hash designed for hash tables. It processes input in 32- or 64-bit chunks, applying multiply-xor-shift operations to achieve strong avalanche behavior. Many production systems including Redis and Hadoop use MurmurHash or its successor xxHash.

Cryptographic hash functions like SHA-256 and MD5 provide collision resistance and one-way properties at the cost of being much slower, typically 50 to 100 times slower than MurmurHash. They should only be used in hash tables if adversarial collision attacks are a concern, such as in web services that accept user-controlled keys.

Time complexity: O(k) for key of length k. Cryptographic hashes have larger constants.

Interview tip: distinguish non-cryptographic hash functions for data structures (fast, good distribution) from cryptographic hash functions for security (collision-resistant, one-way). Using a cryptographic hash in a hash table is overengineering; using a non-cryptographic hash for password storage is a security vulnerability.

Hashing for String Problems

Polynomial rolling hash is one of the most powerful techniques in competitive programming because it enables fast string matching, pattern detection, and duplicate finding that would otherwise require quadratic time.

The basic idea is to precompute a prefix hash array for a string. The hash of any substring from index l to index r can then be computed in O(1) using the formula: hash(l, r) equals (prefix[r+1] minus prefix[l] times power[r-l+1]) modulo M, where power[i] is the i-th power of the base modulo M. This allows comparing any two substrings in O(1) after O(n) preprocessing.

Rabin-Karp string search uses this technique to find all occurrences of a pattern in a text in expected O(n plus m) time, where n is the text length and m is the pattern length. Compute the hash of the pattern, then compute the hash of each window of length m in the text using a rolling update (add the new character, remove the old character). When hashes match, confirm with a direct character comparison to rule out false positives.

A worked example: find all occurrences of the pattern ab in the text xaababc using Rabin-Karp. With base 31 and modulus 1000003, the hash of ab is 31 times 1 plus 2 equals 33. Slide a window of length 2 over the text and compute the rolling hash. When the rolling hash matches 33, check the characters directly. This finds matches at positions 1 and 3 in O(n) time versus O(n times m) for naive search.

Hashing also solves the longest repeating substring problem in O(n log n) by binary searching on the substring length and using a hash set to detect repeated hashes among all substrings of that length.

Time complexity: O(n) preprocessing, O(1) per substring hash query. Space complexity: O(n).

Interview tip: for any string problem involving comparing substrings or finding repeated patterns, consider polynomial hashing as an O(n log n) or O(n) solution before reaching for suffix arrays, which have better asymptotic guarantees but are significantly harder to implement correctly under interview time pressure.