Hashing, Collision Resolution, Bloom Filters, and String Algorithms

Hashing maps data of arbitrary size to fixed-size values. It provides expected $O(1)$ dictionary lookups, cryptographic message integrity verification, caching layers, and high-performance string matching algorithms (KMP, Rabin-Karp).

⚡ Quick Dive

Hashing & String Matching Complexity Reference

Structure / Algorithm Operation / Problem Average Time Worst Time Space Primary Strength
Hash Table (Chaining) Lookup / Insert / Delete $O(1)$ $O(n)$ $O(n)$ Simple deletion, robust to high load factors
Hash Table (Open Addressing) Lookup / Insert / Delete $O(1)$ $O(n)$ $O(n)$ Superior CPU cache locality, zero pointer overhead
Bloom Filter Probabilistic Set Membership $O(k)$ ($k$ hashes) $O(k)$ $O(m)$ (Bits) Zero false negatives; tiny memory footprint
Knuth-Morris-Pratt (KMP) Substring Pattern Search $O(n + m)$ $O(n + m)$ $O(m)$ Guaranteed linear time; never backtracks text pointer
Rabin-Karp Algorithm Multi-Pattern / Substring Search $O(n + m)$ $O(n \cdot m)$ $O(1)$ Rolling hash allows checking multiple patterns

📖 Extended Guide

1. Hash Table Architecture & Collision Resolution

A hash table maps a key $k$ to a bucket index $i = h(k) \pmod m$ where $m$ is the table capacity.

Key: "user:101" ──► [ Hash Function h(k) ] ──► Hash Code: 894371 ──► % 8 ──► Index: 3

1. Separate Chaining (Linked Lists or Mini-Red-Black Trees per Bucket):
   Index 3: [ "user:101", Data ] ──► [ "user:893", Data ] ──► nil

2. Open Addressing (Linear Probing / Robin Hood):
   Index 3: [ "user:101", Data ]
   Index 4: [ "user:893", Data ]  ◄── Stored in next available contiguous slot
  • Load Factor ($\alpha = n / m$): Ratio of stored elements $n$ to table capacity $m$. When $\alpha \ge 0.75$, the table reallocates to double capacity to preserve $O(1)$ performance.
  • Robin Hood Hashing: During open addressing collisions, elements further from their ideal hash location ("poor") take precedence over elements closer to their ideal spot ("rich"), drastically narrowing worst-case search variance.

2. Probabilistic Data Structures: Bloom Filters

A Bloom Filter is a space-efficient probabilistic data structure used to test whether an element is a member of a set:

  • Returns "Definitely Not in Set" (100% guarantee, Zero False Negatives).
  • Returns "Possibly in Set" (Controlled False Positive Probability $p$).
Bit Array of Size m = 10: [ 0, 1, 0, 0, 1, 0, 1, 0, 0, 0 ]
                           ▲        ▲     ▲
                        hash1(x)  hash2(x) hash3(x)
  • Use Cases: Preventing expensive disk reads in databases (Cassandra / RocksDB SSTables), caching layers (preventing cache stampedes), and malicious URL filtering in web browsers.

3. Knuth-Morris-Pratt (KMP) Substring Search

The naive substring search takes $O(n \cdot m)$ time because it backtracks the text index upon a mismatch. KMP eliminates backtracking by precomputing a Longest Proper Prefix which is also Suffix (LPS / $\pi$) table for the pattern in $O(m)$ time:

package main

import "fmt"

func computeLPSArray(pattern string) []int {
	m := len(pattern)
	lps := make([]int, m)
	length := 0
	i := 1

	for i < m {
		if pattern[i] == pattern[length] {
			length++
			lps[i] = length
			i++
		} else {
			if length != 0 {
				length = lps[length-1]
			} else {
				lps[i] = 0
				i++
			}
		}
	}
	return lps
}

func KMPSearch(text, pattern string) []int {
	matches := []int{}
	n, m := len(text), len(pattern)
	if m == 0 || n < m {
		return matches
	}

	lps := computeLPSArray(pattern)
	i, j := 0, 0 // i for text, j for pattern

	for i < n {
		if pattern[j] == text[i] {
			i++
			j++
		}

		if j == m {
			matches = append(matches, i-j)
			j = lps[j-1]
		} else if i < n && pattern[j] != text[i] {
			if j != 0 {
				j = lps[j-1] // Shift pattern without moving text pointer i
			} else {
				i++
			}
		}
	}

	return matches
}

func main() {
	text := "ABABDABACDABABCABAB"
	pattern := "ABABCABAB"
	fmt.Println("Pattern found at indices:", KMPSearch(text, pattern)) // [10]
}

4. Rabin-Karp Algorithm (Rolling Hash)

Rabin-Karp computes a polynomial rolling hash of the pattern and a sliding window over the text: $$H(S) = (s_0 \cdot b^{k-1} + s_1 \cdot b^{k-2} + \dots + s_{k-1}) \pmod q$$

Advancing the window by one character requires only $O(1)$ arithmetic (subtract outgoing character, multiply by base $b$, add incoming character). This enables searching for hundreds of patterns simultaneously (plagiarism detection) in $O(n)$ average time.

⌂ All Guides