Perfect hashing and related problems
MetadataShow full item record
This thesis addresses the following issues: â ¢ Mapping, ordering and searching (MOS) is a successful algorithmic approach to finding perfect hash functions for static dictionaries. Previously, no analysis has been given for the running time of the MOS algorithm. In this thesis, a lower bound is proved on the tradeoff between the time required to find a perfect hash function and the space required to represent the perfect hash function . â ¢ A new algorithm for static dictionaries called the musical chairs(MC) algorithm is developed that is based on ordering the hyperedges of a graph. It is found experimentally that the MC algorithm runs faster than the MOS algorithm in all cases for which the MC algorithm is capable of finding a perfect hash function. â ¢ A new perfect hashing algorithm is developed for dynamic dictionaries. In this algorithm, an insert or a delete operation takes 0(1) time in the average case, and a find operation takes 0(1) time in the worst case. The algorithm is modeled using results from queueing theory . â ¢ An ordering problem from graph theory, motivated by the hypergraph ordering problem in the Me algorithm, is proved to be NP-complete.
- Doctoral Dissertations