Introduction to Algorithms: 6.006 Massachusetts Institute of Technology Instructors: Erik Demaine, Jason Ku, and Justin Solomon Lecture 4: Hashing Lecture 4: Hashing Review Data Structure Array Sorted Array Container Static build(X) find(k) n n log n n log n Operations O(·) Dynamic Order insert(x) find min() find prev(k) delete(k) find max() find next(k) n n n 1 n log n • Idea! Want faster search and dynamic operations. Can we find(k) faster than Θ(log n)? • Answer is no (lower bound)! (But actually, yes...!?) Comparison Model • In this model, assume algorithm can only differentiate items via comparisons • Comparable items: black boxes only supporting comparisons between pairs • Comparisons are <, ≤, >, ≥, =, = 6 , outputs are binary: True or False • Goal: Store a set of n comparable items, support find(k) operation • Running time is lower bounded by # comparisons performed, so count comparisons! Decision Tree • Any algorithm can be viewed as a decision tree of operations performed • An internal node represents a binary comparison, branching either True or False • For a comparison algorithm, the decision tree is binary (draw example) • A leaf represents algorithm termination, resulting in an algorithm output • A root-to-leaf path represents an execution of the algorithm on some input • Need at least one leaf for each algorithm output, so search requires ≥ n + 1 leaves 2 Lecture 4: Hashing Comparison Search Lower Bound • What is worst-case running time of a comparison search algorithm? • running time ≥ # comparisons ≥ max length of any root-to-leaf path ≥ height of tree • What is minimum height of any binary tree on ≥ n nodes? • Minimum height when binary tree is complete (all rows full except last) • Height ≥ dlg(n + 1)e − 1 = Ω(log n), so running time of any comparison sort is Ω(log n) • Sorted arrays achieve this bound! Yay! • More generally, height of tree with Θ(n) leaves and max branching factor b is Ω(logb n) • To get faster, need an operation that allows super-constant ω(1) branching factor. How?? Direct Access Array • Exploit Word-RAM O(1) time random access indexing! Linear branching factor! • Idea! Give item unique integer key k in {0, . . . , u − 1}, store item in an array at index k • Associate a meaning with each index of array • If keys ﬁt in a machine word, i.e. u ≤ 2w , worst-case O(1) ﬁnd/dynamic operations! Yay! • 6.006: assume input numbers/strings ﬁt in a word, unless length explicitly parameterized • Anything in computer memory is a binary integer, or use (static) 64-bit address in memory • But space O(u), so really bad if n u... :( • Example: if keys are ten-letter names, for one bit per name, requires 2610 ≈ 17.6 TB space • How can we use less space? Hashing • Idea! If n u, map keys to a smaller range m = Θ(n) and use smaller direct access array • Hash function: h(k) : {0, . . . , u − 1} → {0, . . . , m − 1} (also hash map) • Direct access array called hash table, h(k) called the hash of key k • If m u, no hash function is injective by pigeonhole principle Lecture 4: Hashing 3 • Always exists keys a, b such that h(a) = h(b) → Collision! :( • Can’t store both items at same index, so where to store? Either: – store somewhere else in the array (open addressing) ∗ complicated analysis, but common and practical – store in another data structure supporting dynamic set interface (chaining) Chaining • Idea! Store collisions in another data structure (a chain) • If keys roughly evenly distributed over indices, chain size is n/m = n/Ω(n) = O(1)! • If chain has O(1) size, all operations take O(1) time! Yay! • If not, many items may map to same location, e.g. h(k) = constant, chain size is Θ(n) • Need good hash function! So what’s a good hash function? Hash Functions Division (bad): h(k) = (k mod m) • Heuristic, good when keys are uniformly distributed! • m should avoid symmetries of the stored keys • Large primes far from powers of 2 and 10 can be reasonable • Python uses a version of this with some additional mixing • If u n, every hash function will have some input set that will a create O(n) size chain • Idea! Don’t use a ﬁxed hash function! Choose one randomly (but carefully)! :( 4 Lecture 4: Hashing hab (k) = (((ak + b) mod p) mod m) Universal (good, theoretically): • Hash Family H(p, m) = {hab | a, b ∈ {0, . . . , p − 1} and a 6= 0} • Parameterized by a ﬁxed prime p > u, with a and b chosen from range {0, . . . , p − 1} • H is a Universal family: Pr {h(ki ) = h(kj )} ≤ 1/m ∀ki = 6 kj ∈ {0, . . . , u − 1} h∈H • Why is universality useful? Implies short chain lengths! (in expectation) • Xij indicator random variable over h ∈ H: Xij = 1 if h(ki ) = h(kj ), Xij = 0 otherwise P • Size of chain at index h(ki ) is random variable Xi = j Xij • Expected size of chain at index h(ki ) ( ) X X X Xij = E {Xi } = E E {Xij } = 1 + E {Xij } h∈H h∈H j j h∈H j= 6 i h∈H X 6 h(kj )} =1+ (1) Pr {h(ki ) = h(kj )} + (0) Pr {h(ki ) = j6=i ≤1+ X h∈H h∈H 1/m = 1 + (n − 1)/m j6=i • Since m = Ω(n), load factor α = n/m = O(1), so O(1) in expectation! Dynamic • If n/m far from 1, rebuild with new randomly chosen hash function for new size m • Same analysis as dynamic arrays, cost can be amortized over many dynamic operations • So a hash table can implement dynamic set operations in expected amortized O(1) time! Data Structure Array Sorted Array Direct Access Array Hash Table Container Static build(X) find(k) n n log n u n(e) n log n 1 1(e) Operations O(·) Dynamic Order insert(x) find min() find prev(k) delete(k) find max() find next(k) n 1 u n n log n u n n n 1 1(a)(e) :)