Title page for ETD etd-05042006-164527


Type of Document Dissertation
Author Juvvadi, Ramana Rao
URN etd-05042006-164527
Title Perfect hashing and related problems
Degree PhD
Department Computer Science
Advisory Committee
Advisor Name Title
Heath, Lenwood S. Committee Chair
Allison, Donald C. S. Committee Member
Fox, Edward Alan Committee Member
Shaffer, Clifford A. Committee Member
Sherali, Hanif D. Committee Member
Keywords
  • Hashing (Computer science)
Date of Defense 1993-06-05
Availability restricted
Abstract
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 0 (1) time in the average case and O( n) 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 0(1) time in the worst case, and an insert or a delete operation takes 0(1) time in the average case and O(n) 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 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.

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
[VT] LD5655.V856_1993.J888.pdf 3.75 Mb 00:17:22 00:08:56 00:07:49 00:03:54 00:00:20
[BTD] next to an author's name indicates that all files or directories associated with their ETD are accessible from the Virginia Tech campus network only.

Browse All Available ETDs by ( Author | Department )

dla home
etds imagebase journals news ereserve special collections
virgnia tech home contact dla university libraries

If you have questions or technical problems, please Contact DLA.