Question

C programming

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

//Your C code

#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 pw(int m,int p){
   int k=1;
   while(p--)
   k=k*m;
return k;
}
int hashFunc(char key[]) {
    // we assume key is always 3 characters long and always valid characters!
    // TODO implement
    int i,l = strlen(key),h=0;
    for( i = 0 ; i < l ; i++ ){
    if(i != l-1)
   h += key[i]*pw(31,l-(i+1));
   else
   h += key[i] ;
    }
    h=h%(HASHTABLE_SIZE);
    return h;
}
int hashFunc2(char key[]) {
    // same assumption as hashFunc
    // TODO implement
    int i,l = strlen(key),h=0;
    for( i = 0 ; i < l ; i++ ){
    if(i != l-1)
   h += key[i]*pw(37,l-(i+1));
   else
   h += key[i] ;
    }
    h=h%(7);
    h = h+1;
    return h;
}
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");
            int i = 1;
            while (i < HASHTABLE_SIZE) {
                int newIndex = (index + hashFunc2(key) * i) % 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 {
        // 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[], char 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{
        int i = 1;
            while (i < HASHTABLE_SIZE) {
                int newIndex = (index + hashFunc2(key) * i) % HASHTABLE_SIZE;
                if (table[newIndex] !=NULL) {
                    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;
}

//screenshot of my editor

//My output terminal

//If you have any doubt.Please feel free to ask.Thanks