Arrays, linked lists and other simple data structures do not allow us to search for an object in constant time. One way to solve this problem is using a Hash Table. It uses a hash function to reduce a key identifying the object to it's hash value in O(1) time, which is used to look up the object.
hashtable.cpp: http://pastebin.com/f66301bdd
The hash table I have written here is a template. It will work with any of your classes, as long as it has a public field name and pointer to the next node. Collision resolution is done by simple chaining. I used char name[NAME] as the key, but you can use anything you want; just replace all the strcmp() calls by the appropriate comparison function.
I used my own hashing function, so replace it if you must:
hash(): Converts a char array into a hash
key(): Converts the hash into a integer key
hash() gives almost no collisions while key() has less than 10% collision rate. Because the hashtable only stores 1000 pointers, collisions will occur quite often in this particular program (when 1000 strings are entered 40% register as collisions). Obviously you'd want to use a better hashing function before plugging this into any real application.
You may also want to read up on salting the input.
No comments:
Post a Comment