麻省理工学院：《算法导论》（英文版） Lecture 7 Prof charles e. leiserson

Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 7 Prof charles e. leiserson

Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 7 Prof. Charles E. Leiserson

Symbol-table problem Symbol table T holding n records recor X keys Operations on T INSERT(T, x) DELETE x) Other fields containing SEARCH(T, K) satellite data How should the data structure T be organized? o 2001 by Charles E Leiserson Introduction to Algorithms Day 11 L7.2

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 11 L7.2 Symbol-table problem Symbol table T holding n records: key key[x] [x] record x Other fields containing satellite data Operations on T: • INSERT(T, x) • DELETE(T, x) • SEARCH(T, k) How should the data structure T be organized?

Direct-access table IDEA: Suppose that the set of keys is K C 10 m-1), and keys are distinct. Set up an array 110.. m-1 7k]= xifk∈ K and keylx]=k, nil otherwise Then, operations take o()time Problem: The range of keys can be large 64-bit numbers(which represent 182446,74073,709,551616 different keys), character strings(even larger o 2001 by Charles E Leiserson Introduction to Algorithms Day 11 L7.3

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 11 L7.3 Direct-access table IDEA: Suppose that the set of keys is K ⊆ {0, 1, …, m–1}, and keys are distinct. Set up an array T[0 . . m–1]: T[k] = x if k ∈ K and key[x] = k, NIL otherwise. Then, operations take Θ(1) time. Problem: The range of keys can be large: • 64-bit numbers (which represent 18,446,744,073,709,551,616 different keys), • character strings (even larger!)

Hash functions Solution: Use a hash function h to map the universe U of all keys into {0,1,…,m-1} 0 k h(k h(k K k h(k2)=h(k5 k3 When a record to be inserted maps to an already occupied slot in T' a collision occurs o 2001 by Charles E Leiserson Introduction to Algorithms Day 11 L7.4

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 11 L7.4 As each key is inserted, h maps it to a slot of T. Hash functions Solution: Use a hash function h to map the universe U of all keys into {0, 1, …, m–1}: U K k1 k2 k3 k4 k5 0 m–1 h(k1) h(k4) h(k2) h(k3) When a record to be inserted maps to an already occupied slot in T, a collision occurs. T = h(k5)

Resolving collisions by chaining Records in the same slot are linked into a list 4 86 52 h(49)=h(86)=h(52)= o 2001 by Charles E Leiserson Introduction to Algorithms Day 11 L7.5

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 11 L7.5 Resolving collisions by chaining • Records in the same slot are linked into a list. h(49) = h(86) = h(52) = i T 4949 8686 5252 i

Analysis of chaining We make the assumption of simple uniform hashing Each key k e K of keys is equally likely to be hashed to any slot of table independent of where other keys are hashed Let n be the number of keys in the table, and let m be the number of slots Define the load factor of T to be a=n/m average number of keys per slot o 2001 by Charles E Leiserson Introduction to Algorithms Day 11 L7.6

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 11 L7.6 Analysis of chaining We make the assumption of simple uniform hashing: • Each key k ∈ K of keys is equally likely to be hashed to any slot of table T, independent of where other keys are hashed. Let n be the number of keys in the table, and let m be the number of slots. Define the load factor of T to be α = n/m = average number of keys per slot

Search cost Expected time to search for a record with a given key=(1+∞) apply hash h searc function and the list access slot Expected search time =o(1)ifa=O(1) or equivalently, ifn=O(m) o 2001 by Charles E Leiserson Introduction to Algorithms Day 11 L7.7

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 11 L7.7 Search cost Expected time to search for a record with a given key = Θ(1 + α). apply hash function and access slot search the list Expected search time = Θ(1) if α = O(1), or equivalently, if n = O(m)

Choosing a hash function The assumption of simple uniform hashing is hard to guarantee but several common techniques tend to work well in practice as long as their deficiencies can be avoided Desirata: a good hash function should distribute the keys uniformly into the slots of the table Regularity in the key distribution should not affect this uniformity o 2001 by Charles E Leiserson Introduction to Algorithms Day 11 L7. 8

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 11 L7.8 Choosing a hash function The assumption of simple uniform hashing is hard to guarantee, but several common techniques tend to work well in practice as long as their deficiencies can be avoided. Desirata: • A good hash function should distribute the keys uniformly into the slots of the table. • Regularity in the key distribution should not affect this uniformity

Division method assume all keys are integers, and define h(k)=k mod m Deficiency: Dont pick an m that has a small divisor d. a preponderance of keys that are congruent modulo d can adversely affect uniformity Extreme deficiency: Ifm=2 then the hash doesn t even depend on all the bits of k Ifk=1011000111011010,andr=6,then h()=0110102 h(k) o 2001 by Charles E Leiserson Introduction to Algorithms Day 11 L7.9

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 11 L7.9 h(k) Division method Assume all keys are integers, and define h(k) = k mod m. Extreme deficiency: If m = 2r, then the hash doesn’t even depend on all the bits of k: • If k = 10110001110110102 and r = 6, then h(k) = 0110102 . Deficiency: Don’t pick an m that has a small divisor d. A preponderance of keys that are congruent modulo d can adversely affect uniformity

Division method(continued) h(k)=k mod m Pick m to be a prime not too close to a power of 2 or 10 and not otherwise used prominently in the computing environment Annoyance. Sometimes. making the table size a prime is convenient But, this method is popular although the next method we ll see is usually superior o 2001 by Charles E Leiserson Introduction to Algorithms Day 11 L7.10

© 2001 by Charles E. Leiserson Introduction to Algorithms Day 11 L7.10 Division method (continued) h(k) = k mod m. Pick m to be a prime not too close to a power of 2 or 10 and not otherwise used prominently in the computing environment. Annoyance: • Sometimes, making the table size a prime is inconvenient. But, this method is popular, although the next method we’ll see is usually superior