need help hash tables
i need to make a hash table using Open Addressing & Linear Probing but i pretty much have no information on it. is there some website or books that would help explain the fucntions of a hash table. I know how the hash tables works but i have no idea of the code to go into it.
The functions i need information on are:
Create table and mark all elements as empty
Clear the hash table
Remove data from table and print each value as it is removed
Print contents of table
Hope someone can point me in the right direction.
Thanks
The functions i need information on are:
Create table and mark all elements as empty
Clear the hash table
Remove data from table and print each value as it is removed
Print contents of table
Hope someone can point me in the right direction.
Thanks
Simply googling it should provide you with hundreds of sources, many of which even contain pseudo-code.
If you want a rather complete introduction to hash tables, I suggest getting a copy of "Introduction to Algorithms" (http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844). Chapter 11 deals with Hash Tables, 11.4 with Open Addressing & Linear Probing.
If you want a rather complete introduction to hash tables, I suggest getting a copy of "Introduction to Algorithms" (http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844). Chapter 11 deals with Hash Tables, 11.4 with Open Addressing & Linear Probing.
Almost forgot: the MIT OpenCourseWare has a video lecture on Hashing. They follow "Introduction to Algorithms" quite strongly, so it probably covers the basics quite thoroughly!
thanks for the suggestions but they focus a lot on the maths of the hash tables. I'm looking for the code to the hash functions. I did try googling it but i couldnt really find anything simple
The functions/code are the key to hashing. It's impossible to properly hash without knowing which functions work and why.
Anyway, most basic hashing functions are a mod/remainder operation in the style of K = A mod M, K being the key, A the entry and M the reserved memory size. It maps any range of numbers A to a [0,M[ range. A Open Addressing hash would simply look like this:
The entry is stored directly into the table under its key, rather than inside a list/chain/bucket attached to a key. The advantage is ease-of-use/implementation and "instant" lookup. The disadvantages are that the list can actually fill up (result: you need to make sure M >= |A|).
Linear probing is the easiest way to collision-handling in a OA hash table. Again, it's easy to code, but definitely not the best performance-wise. It would/could look something like this:
For anything beyond this, I really suggest taking a good book or article on hashing. The Wikipedia entries aren't bad, but they seem to be missing some of the basics for some reason.
Anyway, most basic hashing functions are a mod/remainder operation in the style of K = A mod M, K being the key, A the entry and M the reserved memory size. It maps any range of numbers A to a [0,M[ range. A Open Addressing hash would simply look like this:
myMemory[hash(A)] = A;The entry is stored directly into the table under its key, rather than inside a list/chain/bucket attached to a key. The advantage is ease-of-use/implementation and "instant" lookup. The disadvantages are that the list can actually fill up (result: you need to make sure M >= |A|).
Linear probing is the easiest way to collision-handling in a OA hash table. Again, it's easy to code, but definitely not the best performance-wise. It would/could look something like this:
|
|
For anything beyond this, I really suggest taking a good book or article on hashing. The Wikipedia entries aren't bad, but they seem to be missing some of the basics for some reason.
Last edited on
Topic archived. No new replies allowed.