Data Structures and Algorithm Xiaoqing Zheng Zhengxq@fudan.edu.cn
Data Structures and Algorithm Xiaoqing Zheng zhengxq@fudan.edu.cn
Dictionary problem Dictionary T holding n records records Operations on T. x- key[x] ● INSERT(T,x) ● DELETE(T2x) Other fields. SEARCH(T, k) containing satellite data How should the data structure T'be organized?
Dictionary problem Dictionary T holding n records: key [ x ] Other fields containing satellite data records x How should the data structure T be organized? Operations on T: y INSERT ( T, x ) y DELETE ( T, x ) y SEARCH ( T, k)
Assumptions assumptions The set of keys is K CU=(1,2, ...,u-13 Keys are distinct What can we do
Assumptions Assumptions: y The set of keys is y Keys are distinct KU u ⊆= − {1, 2, , 1} " What can we do ?
Direct access table Create a table T10..u-1 fk∈ K and key{x]=k 7[k] NIL otherwise Benefit Each operation takes constant time rawbacks The range of keys can be large 64-bit numbers(which represent 18446,744,073,709,551,616 different keys) character strings(even larger!)
Direct access table Create a table T[0 … u −1]: x if k ∈ K and key [ x] = k, NIL otherwise. T[ k] = Benefit: – Each operation takes constant time Drawbacks: – The range of keys can be large: y 64-bit numbers (which represent 18,446,744,073,709,551,616 different keys), y character strings (even larger!)
Hash functions Solution: Use a hash function h to map the universe U of all keys into 0,1 h(k1) h(k4) k k h(k2)=h(k5) K ko h(k3) When a record to be inserted maps to an already occupied slot in t a collision occurs
Hash functions Solution: Use a hash function h to map the universe U of all keys into {0, 1, …, m–1}: h ( k1) h ( k4 ) h ( k2) = h ( k5) h ( k3 ) 0 m − 1 When a record to be inserted maps to an already occupied slot in T, a collision occurs. U K k1 k2 k3 k5 k4 T