Hash Table Improvement
Posted on 2009-02-21
There are two parts to my question:
A) I have implemented a hash table that has 26 keys (one for each letter of the alphabet) that will store words in the table/array. A collision list (i.e. overflow list) has been implemented as a single linked list such that if an incoming word into the hash table shares the same key as another word already in the table, then the words will be added to the collision list.
The hash function implemented is too simplistic to be used in practice since it distributes words nonuniformly across the table. I want to design a better hash function, one that will provide a more uniform distribution of the words over the total components of the array (the array size may change if needed) and which will give similar sized overflow lists.
B) I then wish to design and implement an experiment which shows that my hash function performs appropriately. The results of the experiment should:
- demonstrate the uniformity of the word distribution.
- provide information re the length (ie maximum, mimimum, average ) of the overflow lists and
the length (ie maximum, mimimum, average) of search paths to find a word or to identify its
- give the frequency distribution of the size of the possible overflow lists.
Any help on these two parts would be greatly appreciated. No code needed, just a **detailed ** algorithm.