C programming hash table

Problem 1

Below you will find an example implementation of a hash table in C. The collision function is currently very lousy, and the insertion function will refuse to insert an entry if collision happens! Please run the program once and see the result.

#include

#include

#define HASHTABLE_SIZE 10

typedef struct {

int key; // in this example, key is some long id

char* value; // value is a string

} KeyValuePair;

void printHashtable(KeyValuePair* table[]) {

// print out the hash table so that you will see if you have done

// things correctly!

int i;

for (i=0;i

if (table[i] == NULL) {

printf("%2d: - ",i);

} else {

printf("%2d: <%d,%s> ",i,table[i]->key,table[i]->value);

}

}

}

int hashFunc(int key) {

// turns the key into hash and returns it

return key / 1000 % HASHTABLE_SIZE; // a very bad hash function

}

void insert(KeyValuePair* table[], int key, char value[]) {

// insert a key and value

printf("inserting %d,%s to the table... ",key, value);

int hash = hashFunc(key);

int index = hash;

if (table[index] != NULL) {

printf("collision! I refuse to do anything! ");

return;

} else {

// add the new key-value pair to the correct position

printf("Entry inserted at position %d ",index);

KeyValuePair* newEntry = (KeyValuePair*) malloc(sizeof(KeyValuePair));

newEntry->key = key;

newEntry->value = value;

table[index] = newEntry;

}

}

char* lookup(KeyValuePair *table[], int key) {

// look up a key and return the value

int hash = hashFunc(key);

int index = hash;

if (table[index] != NULL) {

if (table[index]->key == key)

return table[index]->value;

else

// collision happened? should we do something?

return NULL;

} else {

return NULL;

}

}

int main()

{

KeyValuePair* hashtable[HASHTABLE_SIZE] = {NULL};

insert(hashtable,1450017, "Ted");

insert(hashtable,1450345, "Jerry");

insert(hashtable,1450191, "Bill");

insert(hashtable,1450677, "Perry");

insert(hashtable,1450922, "Claire");

insert(hashtable,1450957, "Arthur");

printHashtable(hashtable);

printf("Lookup %d - result: %s ", 1450017, lookup(hashtable,1450017));

printf("Lookup %d - result: %s ", 9999999, lookup(hashtable,9999999));

printf("Lookup %d - result: %s ", 1450677, lookup(hashtable,1450677));

printf("Lookup %d - result: %s ", 1450957, lookup(hashtable,1450957));

return 0;

}

Let's warm up by changing the hash function to a less lousy one. According to lecture notes, the following function would be a universal hashing function:

h(k) = (5 * k % 11) % m

where m is the size of the hash table. Please show your updated "int hashFunc(int key)" below:

If you have updated the function correctly, the table should look like this at the end of the program (the last two lookup fails because we haven't handled collisions yet):

0: <1450922,Claire> 1: - 2: - 3: - 4: - 5: - 6: - 7: <1450017,Ted> 8: <1450345,Jerry> 9: -

Lookup 1450017 - result: Ted

Lookup 9999999 - result: (null) Lookup 1450677 - result: (null) Lookup 1450957 - result: (null)