How to create a hash table

Question

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

Answer 1

Handle finding no empty slots and resizing the table.

Answer 2

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.