C programming linear probing

(most program are complete , only need to update function insert and lookup)

We cannot allow collisions unhandled, right? Let's use linear probing to handle the collision. According to the lecture notes, in linear probing, if collision happens (the slot is already occupied by someone else), we will check for next slots one by one until an empty slot is found.

Note: If you probe beyond the maximum index of the hash table, go back to 0 and continue the probing.

Let's add linear probing to insert and lookup functions in this program. Please paste your updated functions below:

#include  #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[]) { // things correctly! int i; for (i=0;i ",i,table[i]->key,table[i]->value); } } } int hashFunc(int key) { return (5 * key % 11) % HASHTABLE_SIZE; // a new 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; }

If you have updated the functions properly, the table should look like this at the output:

0: <1450677,Perry> 1: <1450922,Claire> 2: <1450957,Arthur> 3: - 4: - 5: - 6: - 7: <1450017,Ted> 8: <1450345,Jerry> 9: <1450191,Bill> Lookup 1450017 - result: Ted Lookup 9999999 - result: (null) Lookup 1450677 - result: Perry Lookup 1450957 - result: Arthur