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