HashTable и векторные структуры данных в C99

Question

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

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

Answer 1

Если я правильно сделаю вывод, что вы хотите реализовать растущие хеш-таблицы полностью универсальным способом, то вам понадобится много 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) т.е. вам нужно передать по размеру.

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

Answer 2

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

http://en.wikipedia.org/wiki/The_C_Programming_Language_(book)

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

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

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