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

#include

#include

#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

if (table[i] == NULL) {

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

} else {

printf("%2d: <%s,%d> ",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... ",key);

int hash = hashFunc(key);

int index = hash;

if (table[index] != NULL) {

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

// 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 ",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 ", "Ted", lookup(hashtable,"Ted"));

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

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

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

return 0;

}

If done correctly, you should get the following output:

0: 1: - 2: - 3: - 4: - 5: 6: 7: 8: - 9:

Lookup Ted - result: 1 Lookup Joe - result: 1 Lookup Bob - result: 1 Lookup Ken - result: 1

Please paste your code here: