C programming (quadratic probing)

Unfortunately, as you see, there is primary clustering happening in our table. When primary clustering happens, the entries are lumped together and we need to go through a lot of probing to search for a key.

Let's use quadratic probing instead. With quadratic probing, instead of probing one by one, we will look at the +1 slot, +4 slot and +9 slot until a proper slot is found.

e.g. Suppose the hash is 2 and there is collision; we will first look at 2+1=3, then 2+4=6, then 2+9 = 11 % 10 = 1 and on and on

Please update again the insert and lookup functions in this program . Paste your updated functions below:

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

if (table[i] == NULL) {

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

} else {

printf("%2d: <%d,%s> ",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. We can see that the clustering seem to have improved a little bit. :)

0: <1450922,Claire> 1: <1450677,Perry> 2: - 3: - 4: <1450957,Arthur> 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