CSC 3102 Chapter : Csc3102HashTables
Document Summary
Hasning & common hashing functions: the dictionary problem, hash functions, collision resolution. Let d be a totally ordered set of elements called keys. The dictionary problem is one of maintaining a collection of items drawn from d. The basic operations are inserting a key, deleting a key, and searching for a key. Other operations include searching for the maximum or minimum keys, ac- cessing the keys in sorted order, etc. Hashing may be used to solved the dictionary problem. One approach is to use the direct-addressing scheme in which each element in d is mapped to a unique position in the array. The goal of hashing is to de ne an appropriate mapping h from the set d to a smaller set d consisting of consecutive integers. Although this approach saves memory, its drawback is that h may map multiple keys to the same integer in d .