One of the most common tasks in many computer applications is the maintenance of a dictionary of words. The three most basic operations on the dictionary are find, insert, and delete. An important data structure that supports these operations is a hash table. On a hash table, a basic operation takes 𝑂(1) time in the average case and 𝑂(𝑛) time in the worst case, where n is the number of words in the dictionary. While an ordinary hash function maps the words in a dictionary to a hash table with collisions, a perfect hash function maps the words in a dictionary to a hash table with no collisions. Thus, perfect hashing is a special case of hashing, in which a find operation takes 𝑂(1) time in the worst case, and an insert or a delete operation takes 𝑂(1) time in the average case and 𝑂(𝑛) time in the worst case.
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 𝑂(1) time in the average case, and a find operation takes 𝑂(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. / Ph. D.
Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/37704 |
Date | 04 May 2006 |
Creators | Juvvadi, Ramana Rao |
Contributors | Computer Science, Heath, Lenwood S., Allison, Donald C. S., Shaffer, Clifford A., Fox, Edward A., Sherali, Hanif D. |
Publisher | Virginia Tech |
Source Sets | Virginia Tech Theses and Dissertation |
Language | English |
Detected Language | English |
Type | Dissertation, Text |
Format | viii, 136 leaves, BTD, application/pdf, application/pdf |
Rights | In Copyright, http://rightsstatements.org/vocab/InC/1.0/ |
Relation | OCLC# 29179312, LD5655.V856_1993.J888.pdf |
Page generated in 0.0026 seconds