Question

C programming

Problem 3 [Set via Hashing]

As mentioned in the lecture, a hash table can be used to implement a Set ADT. Let's try to use the template below to implement a Set with double hashing. Here we assume the Set contains names with 3 characters long. Since it is a Set, we do not need to have an explicit value for each key. We will use a token value of 1 if a name belongs to the Set. Let's reuse the exact hash functions we have seen in example in Part 7 of the lecture notes, page 3. As a reminder, we had the following hash function for the string s of length n on a table size m = 10:

h(s) = (s[0] * 31^n-1 + s[1] * 31^n-2 + … s[n-1]) % m For the double hashing we will use the following second hash function (we want to avoid 0 for an obvious reason):

h₂(s) = (s[0] * 37^n-1 + s[1] * 37^n-2 + … s[n-1]) % 7 + 1

where 7 is a random prime number we picked. By definition, for double hashing, when collision happens, we will pick the next index for probing by the formula:

(h(s) + i * h₂(s)) % m

for i = 1...m-1 consecutively.

#include <stdio.h> #include <stdlib.h> #include <string.h> #define HASHTABLE_SIZE 10 typedef struct {     char key[4];     // in this example, key is always 3 characters long!     int value;     // since we are implementing a set, value is 1 or 0 } 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<HASHTABLE_SIZE;i++) {         if (table[i] == NULL) {             printf("%2d: -\n",i);         } else {             printf("%2d: <%s,%d>\n",i,table[i]->key,table[i]->value);         }        } } int hashFunc(char key[]) {     // we assume key is always 3 characters long and always valid characters!         // TODO implement     return 0; } int hashFunc2(char key[]) {     // same assumption as hashFunc         // TODO implement     return 1; } void insert(KeyValuePair* table[], char key[]) {     // insert a key and value     printf("inserting %s to the set...\n",key);     int hash = hashFunc(key);     int index = hash;     if (table[index] != NULL) {         printf("collision! we should use double hashing this time\n");                 // TODO implement         // HINT: int newIndex = (index + hashFunc2(key) * i) % HASHTABLE_SIZE;         return;     } else {         // add the new key-value pair to the correct position         printf("Entry inserted at position %d\n",index);         KeyValuePair* newEntry = (KeyValuePair*) malloc(sizeof(KeyValuePair));         strcpy(newEntry->key,key);         newEntry->value = 1;         table[index] = newEntry;     } } int lookup(KeyValuePair *table[], int key) {     // look up a key and return 1 if it is in the set, 0 otherwise     int hash = hashFunc(key);     int index = hash;     if (table[index] != NULL) {         if (strcmp(table[index]->key,key) == 0)             return 1;         else             // collision happened? should we do something?             // TODO implement                return 0;     } else {         return 0;     } } int main() {         KeyValuePair* hashtable[HASHTABLE_SIZE] = {NULL};     insert(hashtable,"Ted");     insert(hashtable,"Joe");     insert(hashtable,"May");     insert(hashtable,"Ken");     insert(hashtable,"Bob");         printHashtable(hashtable);     printf("Lookup %s - result: %d\n", "Ted", lookup(hashtable,"Ted"));     printf("Lookup %s - result: %d\n", "Joe", lookup(hashtable,"Joe"));     printf("Lookup %s - result: %d\n", "Bob", lookup(hashtable,"Bob"));     printf("Lookup %s - result: %d\n", "Ken", lookup(hashtable,"Ken"));     return 0; }

If done correctly, you should get the following output:

0: <Ken,1>                                                                                                                  1: -                                                                                                           2: -                                                                                                                  3: -                                                                                                                   4: -                                                                                                                  5: <Ted,1>                                                                                                             6: <Joe,1>                                                                                                            7: <May,1>                                                                                                             8: -                                                                                                                  9: <Bob,1>                                                                                                            Lookup Ted - result: 1                                                                                                 Lookup Joe - result: 1                                                                                                 Lookup Bob - result: 1                                                                                                 Lookup Ken - result: 1

Please paste your code here:

Answer 1

EXECUTABLE CODE:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include<math.h>
#define HASHTABLE_SIZE 10

typedef struct {

char key[4];

int value;

} KeyValuePair;

void printHashtable(KeyValuePair* table[]) {

int i;

for (i=0;i<HASHTABLE_SIZE;i++) {

if (table[i] == NULL) {

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

} else {

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

}

}

}

int hashFunc(char key[]) {

int hash= key[0]*pow(31,2)+key[1]*pow(31,1)+key[2]*pow(31,0);

hash=hash%HASHTABLE_SIZE;

return hash;

}

int hashFunc2(char key[]) {

int hash= key[0]*pow(37,2)+key[1]*pow(37,1)+key[2]*pow(37,0);

hash=(hash%7)+1;

return hash;

}

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

printf("inserting %s to the set...\n",key);

int hash = hashFunc(key);
int index = hash;

if (table[index] != NULL) {

printf("collision! we should use double hashing this time\n");

int index2=hashFunc2(key);
int i=1;
while(1)
{

int newIndex=(index+ i*index2)%HASHTABLE_SIZE;
if (table[newIndex] ==NULL)
{
printf("Entry inserted at position %d\n",newIndex);

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

strcpy(newEntry->key,key);

newEntry->value = 1;

table[newIndex] = newEntry;
break;
}
i++;
}

  

return;

} else {

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

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

strcpy(newEntry->key,key);

newEntry->value = 1;

table[index] = newEntry;

}

}

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

int hash = hashFunc(key);

int index = hash;

if (table[index] != NULL) {

if (strcmp(table[index]->key,key) == 0)

return 1;

else
{

int index2=hashFunc2(key);
int i=1;
while(1)
{

int newIndex=(index+ i*index2)%HASHTABLE_SIZE;
if (strcmp(table[newIndex]->key,key) == 0)
{
return 1;
}
i++;
}

  

return 0;
}   
} else {

return 0;

}

}

int main()

{

KeyValuePair* hashtable[HASHTABLE_SIZE] = {NULL};

insert(hashtable,"Ted");

insert(hashtable,"Joe");

insert(hashtable,"May");

insert(hashtable,"Ken");

insert(hashtable,"Bob");

printHashtable(hashtable);

printf("Lookup %s - result: %d\n", "Ted", lookup(hashtable,"Ted"));

printf("Lookup %s - result: %d\n", "Joe", lookup(hashtable,"Joe"));

printf("Lookup %s - result: %d\n", "Bob", lookup(hashtable,"Bob"));

printf("Lookup %s - result: %d\n", "Ken", lookup(hashtable,"Ken"));

return 0;

}