Find It Fast: Hash Tables and Collision Resolution

The Objective : Hash tables are an efficient method for data storage and access. They allow accessing data without extensive search. When two keys hash to the same location, a collision resolution algorithm is used to determine where the keys should be placed. I studied three collision resolution algorithms (CRAs): linear probing, linked list, and cellar. My hypothesis was that all three hash table CRAs would perform about equally well, and all much better than a simpler linear search method.

Methods/Materials

I measured time, memory usage, and number of string comparisons (as a more precise proxy for time) on 50 different inputs for these three hash methods and for linear search.

Results

As expected, hashing was a hundred times faster than linear search, taking 0.35-0.5 seconds to look up the approximately one million words of the Bible, instead of 45 seconds for linear search.

Conclusions/Discussion

The cellar and linked list CRAs always performed well. Contrary to my hypothesis, linear probing sometimes performed poorly when it didn't rehash until the table was full. Rehashing when the table was only 70% full allowed linear probing to perform on par with linked list and cellar.

This project programmed and measured the performance of three collision resolution algorithms for hash tables.

Science Fair Project done By Abraham P. Karplus

 

 

<<Back To Topics Page...................................................................................>>Next Topic

Related Projects : Effects of Inverse Fourier Transform ,Efficient True Random Number Generation, Fibonacci Sequence in Plants ,Number Theory Meets Algebra ,Optimizing the Chicken Soup Can ,Tricky Triangles ,What's the Deal or No Deal ,Mathematical Approaches to a Neat Problem ,Computer Generated Simulation ,Effect of RGB and CMYK Color