Hashmap со строковым массивом в качестве значения в C

Question

Я строю программу на C, которая читает файл базы данных и переводит его в некоторые C-структуры.

Можно ли реализовать хеш-таблицу, которая использует int в качестве ключа и возвращает строковый массив (char **) в качестве значения (это для получения определенного кортежа в базе данных по id).

Спасибо!

Answer 1

Да, вы можете, вот пример использования SuperFastHash (комментарии в коде):

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

typedef struct data {
    int index;
    char name[16];
    struct data *next;
} data;

extern char *strdup(const char *);

#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
                       +(uint32_t)(((const uint8_t *)(d))[0]))

uint32_t SuperFastHash(const char * data, int len)
{
    uint32_t hash = len, tmp;
    int rem;

    if (len <= 0 || data == NULL) return 0;

    rem = len & 3;
    len >>= 2;

    /* Main loop */
    for (;len > 0; len--) {
        hash  += (get16bits(data));
        tmp    = (get16bits(data + 2) << 11) ^ hash;
        hash   = (hash << 16) ^ tmp;
        data  += 2 * sizeof(uint16_t);
        hash  += hash >> 11;
    }

    /* Handle end cases */
    switch (rem) {
        case 3:
            hash += get16bits(data);
            hash ^= hash << 16;
            hash ^= ((signed char)data[sizeof(uint16_t)]) << 18;
            hash += hash >> 11;
            break;
        case 2:
            hash += get16bits(data);
            hash ^= hash << 11;
            hash += hash >> 17;
            break;
        case 1:
            hash += (signed char)*data;
            hash ^= hash << 10;
            hash += hash >> 1;
    }

    /* Force "avalanching" of final 127 bits */
    hash ^= hash << 3;
    hash += hash >> 5;
    hash ^= hash << 4;
    hash += hash >> 17;
    hash ^= hash << 25;
    hash += hash >> 6;

    return hash;
}

/* return data (or NULL if exists) */
data *insert(data **table, data *value, size_t n)
{
    uint32_t hash;
    data *temp;
    char s[10];
    int len;

    /* convert index to string */
    len = sprintf(s, "%d", value->index);
    hash = SuperFastHash(s, len) % n;
    if (table[hash] == NULL) {
        /* not found, insert */
        table[hash] = value;
    } else {
        temp = table[hash];
        while (1) {
            if (temp == value) return NULL;
            if (temp->next) {
                temp = temp->next;
            } else break;
        }
        /* not found, insert */
        temp->next = value;
    }
    return value;
}

/* return data as array of strings (or NULL if not found) */
char **search(data **table, int index, size_t n)
{
    char **record;
    uint32_t hash;
    data *temp;
    char s[10];
    int len;

    /* convert index to string */
    len = sprintf(s, "%d", index);
    hash = SuperFastHash(s, len) % n;
    if (table[hash] != NULL) {
        temp = table[hash];
        while (temp) {
            if (temp->index == index) {
                /* struct to array of strings (check mallocs) */
                record = malloc(sizeof(*record) * 2);
                record[0] = strdup(s);
                record[1] = strdup(temp->name);
                return record;
            }
            temp = temp->next;
        }
    }
    /* not found */
    return NULL;
}

void free_record(char **record)
{
    free(record[0]);
    free(record[1]);
    free(record);
}

int main(void)
{
    data values[] = {
        {4611, "Kessie", NULL},
        {5141, "Neville", NULL},
        {6484, "Dominic", NULL},
        {2074, "Kelly", NULL},
        {9969, "Petra", NULL},
        {9663, "Laura", NULL},
        {6136, "Bianca", NULL},
        {1647, "Aurelia", NULL},
        {8512, "Britanney", NULL},
        {2613, "Oprah", NULL},
        {2610, "Shay", NULL},
        {6591, "Ralph", NULL},
        {9302, "Charity", NULL},
        {2593, "Lillian", NULL},
        {9732, "Hop", NULL}
    };
    size_t i, n = sizeof(values) / sizeof(values[0]);
    /* array of pointers to values */
    data **table = calloc(n, sizeof(*table));
    /* value as array of strings */
    char **record;

    if (table == NULL) {
        perror("calloc");
        exit(EXIT_FAILURE);
    }
    puts("Inserting ...");
    for (i = 0; i < n; i++) {
        printf("%d %s\n", values[i].index, values[i].name);
        insert(table, &values[i], n);
    }
    if (!insert(table, &values[1], n)) puts("Exists");
    puts("Searching ...");
    for (i = 2610; i < 2615; i++) {
        record = search(table, i, n);
        if (record == NULL) {
            printf("%zu Not found\n", i);
        } else {
            printf("%s %s\n", record[0], record[1]);
            free_record(record);
        }
    }
    free(table);
    return 0;
}

Но, как отметил Рикайан, сбалансированное бинарное дерево поиска - лучший вариант.

Answer 2

Да, это возможно. Но это действительно зависит от характера ключа. Если вы не можете найти образец того, как ключ соответствует значению, очень трудно реализовать хеш-функцию. Один из подходов заключается в реализации сбалансированного по высоте дерева двоичного поиска по ключам и сохранению значений. Это гарантировало бы наихудшую временную сложность O(logn) для каждой операции.