Блог

Я хочу создать хэш-таблицу, которая опирается на независимую векторную структуру данных в C99. Я могу сделать это на C с помощью OO, но я не уверен, как подойти к этому, используя структуры и объединения.

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

Если я правильно понимаю, что вы хотите реализовать растущие хэш-таблицы полностью универсальным способом, тогда вам понадобится много void указателей. Вектор — это не так уж сложно, просто нужно много печатать:

 typedef struct {
    size_t capacity, nelems;
    void **contents;
} Vector;

enum { INITIAL_CAPACITY = 256 };

Vector *make_vector()
{
    Vector *v = malloc(sizeof(Vector));
    if (v == NULL)
        return NULL;
    v->capacity = INITIAL_CAPACITY;
    v->contents = malloc(sizeof(void *) * v->capacity);
    if (v->contents == NULL) {
        free(v);
        return NULL;
    }
    v->nelems = 0;
    return v;
}

// exercise for the reader
int vector_append(Vector *, void *);
void *vector_at(Vector const *);
 

Имейте в виду, что общая хэш-функция будет иметь прототип size_t hash(void const *, size_t) , т. Е. Вам нужно передать размер.

(Примечание: вы пропустите не функции ООП C ; это шаблоны, безопасность типов, которые они покупают, и синтаксический сахар, такой как перегрузка оператора. Взгляните на ohash библиотеку OpenBSD для получения дополнительных примеров.)

Следующая книга содержит, вероятно, лучшее описание как связанных списков, так и хэш-таблицы на C с использованием структур:

http://en.wikipedia.org/wiki/The_C_Programming_Language_ (книга)

Он также реализует простой алгоритм хеширования.

Другим простым, но равномерно распределенным алгоритмом хеширования является алгоритм cdb, как определено здесь:

http://cr.yp.to/cdb/cdb.txt