dbh.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define PRIME_1 53 //around 52, num of lower and uppercase letters
#define PRIME_2 89
#define STR_SZ 31 //30 + 1 nullchar

typedef enum {
    NIL, EXISTS, DELETED
} state;

typedef struct kv_pair {
    state state;
    char key[STR_SZ];
    char value[STR_SZ];
} kv_pair;

typedef struct dict {
    kv_pair *dict;
    int n; //power of 2, >= m
    int m;
} dict;

//polynomial rolling hash function, assuming n is prime
//see: https://cp-algorithms.com/string/string-hashing.html
int hash_string_primary(char *string, int m) {
    int result = 0;
    int prime_power = 1;
    while (*string) {
        result = (result + *string * prime_power) % m; //'a' == 1, otherwise: "a", "aa", "aaa"... == 0
        prime_power = (prime_power * PRIME_1) % m;
        string++;
    }
    return result;
}

//seconary hash must be always odd
int hash_string_secondary(char *string, int m) {
    int result = 0;
    int prime_power = 1;
    while (*string) {
        result = (result + *string * prime_power) % m; //'a' == 1, otherwise: "a", "aa", "aaa"... == 0
        prime_power = (prime_power * PRIME_2) % m;
        string++;
    }
    if (result % 2 == 0) {
        result++;
    }
    return result;
}

dict dict_init(int m) {
    dict result;
    result.m = m;
    result.n = 2;

    while (result.n < result.m) {
        result.n *= 2;
    }

    result.dict = malloc(result.n * sizeof(*result.dict));

    for (int i = 0; i < result.n; i++) {
        result.dict[i].state = NIL;
    }

    return result;
}

void dict_free(dict *dict) {
    free(dict->dict);
}

void dict_add(dict *dict, char *key, char *value) {
    int i = 0;
    int h1 = hash_string_primary(key, dict->m);
    int h2 = hash_string_secondary(key, dict->n);
    while (i < dict->n) {
        //assuming m is prime, n is power of 2, >= m, secondary hash is always odd
        int hash = (h1 + i * h2) % dict->n;
        if (dict->dict[hash].state != EXISTS) {
            strcpy(dict->dict[hash].key, key);
            strcpy(dict->dict[hash].value, value);
            dict->dict[hash].state = EXISTS;
            return;
        }
        i++;
    }
}

char *dict_get(dict *dict, char *key) {
    int i = 0;
    int h1 = hash_string_primary(key, dict->m);
    int h2 = hash_string_secondary(key, dict->n);
    while (i < dict->n) {
        //assuming m is prime, n is power of 2, >= m, secondary hash is always odd
        int hash = (h1 + i * h2) % dict->n;
        if (dict->dict[hash].state != NIL) {
            if (dict->dict[hash].state == EXISTS && strcmp(dict->dict[hash].key, key) == 0) {
                return dict->dict[hash].value;
            }
        }
        else {
            break;
        }
        i++;
    }
    return NULL;
}

void dict_remove(dict *dict, char *key) {
    int i = 0;
    int h1 = hash_string_primary(key, dict->m);
    int h2 = hash_string_secondary(key, dict->n);
    while (i < dict->n) {
        //assuming m is prime, n is power of 2, >= m, secondary hash is always odd
        int hash = (h1 + i * h2) % dict->n;
        if (dict->dict[hash].state != NIL) {
            if (dict->dict[hash].state == EXISTS && strcmp(dict->dict[hash].key, key) == 0) {
                dict->dict[hash].state = DELETED;
                return;
            }
        }
        else {
            return;
        }
        i++;
    }
}

int main() {
    int Z;
    scanf("%d", &Z);

    while (Z--) {
        int n, k;
        char op[2], key[STR_SZ], value[STR_SZ], *result;

        scanf("%d %d", &n, &k);
        dict dict = dict_init(n);

        while (k--) {
            scanf("%s %s", op, key);
            switch(op[0]) {
                case 'a':
                    scanf("%s", value);
                    dict_add(&dict, key, value);
                    break;
                case 'g':
                    result = dict_get(&dict, key);
                    printf("%s\n", (result ? result : ""));
                    break;
                case 'r':
                    dict_remove(&dict, key);
                    break;
            }
        }

        dict_free(&dict);
    }
}

has.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define PRIME 53 //around 52, num of lower and uppercase letters
#define STR_SZ 31 //30 + 1 nullchar

typedef struct kv_pair {
    char key[STR_SZ];
    char value[STR_SZ];
    struct kv_pair *next;
} kv_pair;

typedef struct dict {
    kv_pair **dict;
    int n;
} dict;

//polynomial rolling hash function, assuming n is prime
//see: https://cp-algorithms.com/string/string-hashing.html
int hash_string(char *string, int n) {
    int result = 0;
    int prime_power = 1;
    while (*string) {
        result = (result + *string * prime_power) % n; //'a' == 1, otherwise: "a", "aa", "aaa"... == 0
        prime_power = (prime_power * PRIME) % n;
        string++;
    }
    return result;
}

dict dict_init(int n) {
    dict result;
    result.n = n;
    result.dict = malloc(result.n * sizeof(*result.dict));
    for (int i = 0; i < n; i++) {
        result.dict[i] = NULL;
    }
    return result;
}

void dict_free(dict *dict) {
    for (int i = 0; i < dict->n; i++) {
        kv_pair *to_free = dict->dict[i];
        while (to_free) {
            kv_pair *next = to_free->next;
            free(to_free);
            to_free = next;
        }
    }
    free(dict->dict);
}

void dict_add(dict *dict, char *key, char *value) {
    int hash = hash_string(key, dict->n);
    kv_pair *to_add = malloc(sizeof(*to_add));
    strcpy(to_add->key, key);
    strcpy(to_add->value, value);
    to_add->next = dict->dict[hash];
    dict->dict[hash] = to_add;
}

char *dict_get(dict *dict, char *key) {
    kv_pair *kv_list = dict->dict[hash_string(key, dict->n)];
    while (kv_list && strcmp(key, kv_list->key)) {
        kv_list = kv_list->next;
    }
    return kv_list ? kv_list->value : NULL;
}

void dict_remove(dict *dict, char *key) {
    int hash = hash_string(key, dict->n);
    kv_pair *to_free;
    
    //first element must be treated specially
    if (strcmp(key, dict->dict[hash]->key) == 0) {
        to_free = dict->dict[hash];
        dict->dict[hash] = to_free->next;
    }
    else {
        kv_pair *kv_list = dict->dict[hash];
        while (strcmp(key, kv_list->next->key)) {
            kv_list = kv_list->next;
        }
        to_free = kv_list->next;
        kv_list->next = kv_list->next->next;
    }
    
    free(to_free);
}

int main() {
    int Z;
    scanf("%d", &Z);

    while (Z--) {
        int n, k;
        char op[2], key[STR_SZ], value[STR_SZ], *result;

        scanf("%d %d", &n, &k);
        dict dict = dict_init(n);

        while (k--) {
            scanf("%s %s", op, key);
            switch(op[0]) {
                case 'a':
                    scanf("%s", value);
                    dict_add(&dict, key, value);
                    break;
                case 'g':
                    result = dict_get(&dict, key);
                    printf("%s\n", (result ? result : ""));
                    break;
                case 'r':
                    dict_remove(&dict, key);
                    break;
            }
            
            #ifdef DEBUG
            printf("Current key hash: %d\n", hash_string(key, n));
            for (int i = 0; i < n; i++) {
                printf("%d: ", i);
                if (dict.dict[i]) {
                    kv_pair *list = dict.dict[i];
                    while (list) {
                        printf("<%s, %s> ", list->key, list->value);
                        list = list->next;
                    }
                }
                else {
                    printf("NULL");
                }
                printf("\n");
            }
            #endif
        }

        dict_free(&dict);
    }
}

pho.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define PRIME 53 //around 52, num of lower and uppercase letters
#define STR_SZ 31 //30 + 1 nullchar

typedef enum {
    NIL, EXISTS, DELETED
} state;

typedef struct kv_pair {
    state state;
    char *key;
    char *value;
} kv_pair;

typedef struct dict {
    kv_pair *dict;
    int n; //power of 2, >= m
    int m;
} dict;

//polynomial rolling hash function, assuming n is prime
//see: https://cp-algorithms.com/string/string-hashing.html
int hash_string(char *string, int m) {
    int result = 0;
    int prime_power = 1;
    while (*string) {
        result = (result + *string * prime_power) % m; //'a' == 1, otherwise: "a", "aa", "aaa"... == 0
        prime_power = (prime_power * PRIME) % m;
        string++;
    }
    return result;
}

dict dict_init(int m) {
    dict result;
    result.m = m;
    result.n = 2;

    while (result.n < result.m) {
        result.n *= 2;
    }

    result.dict = malloc(result.n * sizeof(*result.dict));

    for (int i = 0; i < result.n; i++) {
        result.dict[i].state = NIL;
    }

    return result;
}

void dict_free(dict *dict) {
    for (int i = 0; i < dict->n; i++) {
        if (dict->dict[i].state == EXISTS) {
            free(dict->dict[i].key);
            free(dict->dict[i].value);
        }
    }
    free(dict->dict);
}

void dict_add(dict *dict, char *key, char *value) {
    int i = 0;
    int h1 = hash_string(key, dict->m);
    while (i < dict->n) {
        //assuming n is power of 2, >= m
        //c1=c2=1/2 - this leads to triangular numbers, which are unique in [0..n-1]
        int hash = (h1 + (i + i * i) / 2) % dict->n;
        if (dict->dict[hash].state != EXISTS) {
            dict->dict[hash].key = malloc((strlen(key) + 1) * sizeof(*dict->dict[hash].key));
            dict->dict[hash].value = malloc((strlen(value) + 1) * sizeof(*dict->dict[hash].value));
            strcpy(dict->dict[hash].key, key);
            strcpy(dict->dict[hash].value, value);
            dict->dict[hash].state = EXISTS;
            return;
        }
        i++;
    }
}

char *dict_get(dict *dict, char *key) {
    int i = 0;
    int h1 = hash_string(key, dict->m);
    while (i < dict->n) {
        //assuming n is power of 2, >= m
        //c1=c2=1/2 - this leads to triangular numbers, which are unique in [0..n-1]
        int hash = (h1 + (i + i * i) / 2) % dict->n;
        if (dict->dict[hash].state != NIL) {
            if (dict->dict[hash].state == EXISTS && strcmp(dict->dict[hash].key, key) == 0) {
                return dict->dict[hash].value;
            }
        }
        else {
            break;
        }
        i++;
    }
    return NULL;
}

void dict_remove(dict *dict, char *key) {
    int i = 0;
    int h1 = hash_string(key, dict->m);
    while (i < dict->n) {
        //assuming n is power of 2, >= m
        //c1=c2=1/2 - this leads to triangular numbers, which are unique in [0..n-1]
        int hash = (h1 + (i + i * i) / 2) % dict->n;
        if (dict->dict[hash].state != NIL) {
            if (dict->dict[hash].state == EXISTS && strcmp(dict->dict[hash].key, key) == 0) {
                free(dict->dict[hash].key);
                free(dict->dict[hash].value);
                dict->dict[hash].state = DELETED;
                return;
            }
        }
        else {
            return;
        }
        i++;
    }
}

int main() {
    int Z;
    scanf("%d", &Z);

    while (Z--) {
        int n, k;
        char op[2], key[STR_SZ], value[STR_SZ], *result;

        scanf("%d %d", &n, &k);
        dict dict = dict_init(n);

        while (k--) {
            scanf("%s %s", op, key);
            switch(op[0]) {
                case 'a':
                    scanf("%s", value);
                    dict_add(&dict, key, value);
                    break;
                case 'g':
                    result = dict_get(&dict, key);
                    printf("%s\n", (result ? result : ""));
                    break;
                case 'r':
                    dict_remove(&dict, key);
                    break;
            }
        }

        dict_free(&dict);
    }
}