CODEWITHSUNDEEP
c++hashhashtable
Joshua
Joshua

Reputation: 4320

How to create a hash table

I would like to mention before continuing that I have looked at other questions asking the same thing on this site as well as on other sites. I hope that I can get a good answer, because my goal is twofold:

  1. Foremost, I would like to learn how to create a hash table.
  2. Secondly, I find that a lot of answers on Stack Overflow tend to assume a certain level of knowledge on a subject that is often not there, especially for the newer types. That being said, I hope to edit my main message to include an explanation of the process a bit more in depth once I figure it out myself.

Onto the main course:

As I understand them so far, a hash table is an array of lists (or a similar data structure) that hopes to, optimally, have as few collisions as possible in order to preserve it's lauded O(1) complexity. The following is my current process:

So my first step is to create an array of pointers:

Elem ** table;
table = new Elem*[size];//size is the desired size of the array

My second step is to create a hashing function( a very simple one ).

int hashed = 0;
hashed = ( atoi( name.c_str() ) + id ) % size;
//name is a std string, and id is a large integer. Size is the size of the array.

My third step would be to create something to detect collisions, which is the part I'm currently at.

Here's some pseudo-code:

while( table[hashedValue] != empty )
    hashedValue++

else
    put in the list at that index.

It's relatively inelegant, but I am still at the "what is this" stage. Bear with me.

Is there anything else? Did I miss something or do something incorrectly?

Thanks

Upvotes: 9

Views: 12260

Answers (3)

Xeo
Xeo

Reputation: 131799

A hash function produces the same value for the same data. Your collision check, however, modifies that value, which means that the hash value not only depends on the input, but also on the presence of other elements in the hash map. This is bad, as you almost never will be able to actually access the element you put in before through its name, only through iterating over the map.

Second, your collision check is vulnerable to overflow / range errors, as you just increase the hash value without checking against the size of the map (though, as I said before, you shouldn't even be doing this).

Upvotes: 0

Fred Foo
Fred Foo

Reputation: 363567

You're missing a definition for Elem. That's not trivial, as it depends on whether you want a chaining or a probing hash table.

Upvotes: 1

Martin Beckett
Martin Beckett

Reputation: 96109

Handle finding no empty slots and resizing the table.

Upvotes: 4

Related Questions