open hash using chained lists
Hi!
As a homework from college i have to create an open hash to store certain struct called "server".
I defined the hash as the following:
struct ListOfServers
{
server* serverr;
ListOfServers* next;
}
ListOfServers** HashOfservers
This is an array of lists of servers, when the index of the array is determinated by the hash function and the insertion its always at the start of the list.
Is this a correct implementation of an open hash? Since i googled and i find other implementations much larger in terms of code etc.
As a homework from college i have to create an open hash to store certain struct called "server".
I defined the hash as the following:
struct ListOfServers
{
server* serverr;
ListOfServers* next;
}
ListOfServers** HashOfservers
This is an array of lists of servers, when the index of the array is determinated by the hash function and the insertion its always at the start of the list.
Is this a correct implementation of an open hash? Since i googled and i find other implementations much larger in terms of code etc.
the structure and concept sounds right.
The code to hash will be larger.
By the way the declaration
The code to hash will be larger.
By the way the declaration
ListOfServers** HashOfservers is double dimension array of servers. I think you only need single dimension array of servers, with each element in the array is the "Head" of the linked list of server. Each node of this list is then the hashed (and chained) server *
1. You need an array (std::vector<>) of linked lists.
2. You need a good hash function for your server struct. Generally, you'll generate an index into your vector. If the numbers you generate are bigger than the vector's size, you can (mod size) them. Try to create as few collisions (Same hash for different servers) as possible.
3. Use the hashed index to stick the server struct onto the end of the linked list at that index.
This is obviously a very basic hash table, but it sounds like that's all you need. If you need to dynamically re-size your table you can just change the (mod) value in your hashing function and rehash the whole table.
2. You need a good hash function for your server struct. Generally, you'll generate an index into your vector. If the numbers you generate are bigger than the vector's size, you can (mod size) them. Try to create as few collisions (Same hash for different servers) as possible.
3. Use the hashed index to stick the server struct onto the end of the linked list at that index.
This is obviously a very basic hash table, but it sounds like that's all you need. If you need to dynamically re-size your table you can just change the (mod) value in your hashing function and rehash the whole table.
Last edited on
thanks for both answers, i know it looks kind of a matrix, double dimensional array, but thats not entirely true since the size of the lists is different for each cell of the array, it all depends on how many times i ยก have added an element to list contained in that cell..
I have my hash function, when i want to add a server* to my hash, i use
f = serverID mod HASHarraySize;
and i add the Server at the start of the ListOfServers* located at HashOfservers[f]
The way f is defined, i know its a good hash function ( it produces as few collisions as possible)
So my question basically is,, if this implementation could be considered correct, or i have to use (std::vector<>) no matter what... Thats my doubt, because the way i see it, it is correctly implemented by the struct definitions i posted above, but if i do a google search i do not find an implementation similar to what i posted.
I have my hash function, when i want to add a server* to my hash, i use
f = serverID mod HASHarraySize;
and i add the Server at the start of the ListOfServers* located at HashOfservers[f]
The way f is defined, i know its a good hash function ( it produces as few collisions as possible)
So my question basically is,, if this implementation could be considered correct, or i have to use (std::vector<>) no matter what... Thats my doubt, because the way i see it, it is correctly implemented by the struct definitions i posted above, but if i do a google search i do not find an implementation similar to what i posted.
Sure, you can use a double pointer/array of pointers (if your hash table has a constant size), but you'd be writing your own linked list class. Generally if the standard library already has a class for what you need and your assignment doesn't restrict it then it's best to just use it.
Not only is it faster, it's also safer because you don't have to work with raw pointers.
In your case
is what you need.
Also, I think new elements are generally pushed to the back of the linked list, not the front in a hash table.
Not only is it faster, it's also safer because you don't have to work with raw pointers.
In your case
std::vector<std::list>is what you need.
Also, I think new elements are generally pushed to the back of the linked list, not the front in a hash table.
Topic archived. No new replies allowed.