A has table basically revolves around having a hash function which is.. well, let's look at a linked list implementation of a hash table (see 6.6 of K&R for a more complete discussion). Obviously, you'll need to understand linked lists to do this code.
Code:
#define HASHSIZE 1000
typedef struct _node
{
char * name;
int score;
struct _node * next;
} NODE;
// returns a value from 0 to 999
int hash (char * name);
void addVal (char * name, int score);
int readVal (char * name);
void add2tail (NODE * list, NODE * addMe);
NODE * makeNode (char * name, int score);
// Global for simplicity
NODE * hTable [HASHSIZE];
The use of this program is going to be to keep track of the grades of several students in a class.
Code:
int main (void)
{
int JonnyScore;
addVal ("Jonny", 68);
addVal ("Susie", 24);
addVal ("QuestionC", 101);
JonnyScore = readVal ("Jonny");
return 0;
}
void addVal (char * name, int score)
{
NODE * p;
int hashval;
p = makeNode (name, score);
hashval = hash (name);
add2tail (hTable[hashval], p);
return;
}
int readVal (char * name)
{
int hashval;
NODE * p;
hashval = hash (name);
// Search untill you find the node with the same name.
for (p = hTable[hashval]; strcmp (p -> name, name) != 0; p = p -> next);
return p -> score;
}
No need to post the makeNode and add2tail functions I hope. Hopefully the code is complete enought to get the idea across. Let's discuss what the hash function should do. Obviously, as long as this function returns a value from 0 to 999, the program is going to work. In theory, the function could just return 0 every time, and the program would work, it would just be a rather bulky linked list program then. The point of the hash however is to replace what we'd normally do with a linked list with a table so that we don't have to perform the same old linear search. So ideally, we want our hash function to not return any duplicate values. If it does return a duplicate value, then we'll try to store two values in the same hash table entry. This program handles that by treating each hash table entry as a linked list. There are other ways.
Anyhow, it all revolves around our function hash, which we would like to have a fairly unbiased distribution (this is from K&R)
Code:
int hash (char * name)
{
int hashval;
for (hashval = 0; *name != '\0'; name++)
hashval = *name + 31 * hashval;
return hashval % HASHSIZE;
}
This function pretty much generates a number which is random with respect to name (obviously from 0 to HASHSIZE - 1 because of the return statement), which is what the function needs to be efficient.
Incidentally, I should say that the code I posted wasn't tested to see if it would compile, and even if it does, it still has an awful lot of problems with it (like, what happens if you try to add duplicate names to the table?, or try to read the score of a name not in the table), so just take if for explanatory value, and try and patch it up if you feel like making a hash table program.
Different hash table implementations pretty much differ on two points.
1) Their hash function.
2) How they handle collisions. Looking at that posted page, this example uses 'chaining'.
EDIT: Now to think of, the code certainly won't compile since it doesn't have the linked list functions.