Реализовать хеш-таблицу

Question

Я пытаюсь создать эффективную справочную таблицу в C .

У меня есть целое число в качестве ключа и переменная длина char* в качестве значения.

Я смотрел на uthash, но для этого требуется фиксированная длина char*.Если я сделаю это большое число, то я использую слишком много памяти.

struct my_struct {
    int key;
    char value[10];             
    UT_hash_handle hh;
};

У кого-нибудь есть указатели?Любое понимание высоко ценится.

---

Спасибо всем за ответы.Я пошел с uthash и определил свою собственную структуру для размещения моих данных.

Answer 1

Сначала вы должны подумать о своей стратегии коллизий:

1. Будет ли у вас несколько хеш-функций?
2. Или вам придется использовать контейнеры внутри хеш-таблицы?

Мы выберем 1.

Затем вы должны выбрать красиво распределенную хеш-функцию.Например, мы выберем

int hash_fun(int key, int try, int max) {
    return (key + try) % max;
}

Если вам нужно что-то лучше, возможно, взгляните на метод среднего квадрата .

Затем вам нужно будет решить, что такое хеш-таблица.

struct hash_table {
    int max;
    int number_of_elements;
    struct my_struct **elements;
};

Затем нам нужно будет определить, как вставлять и получать.

int hash_insert(struct my_struct *data, struct hash_table *hash_table) {
    int try, hash;
    if(hash_table->number_of_elements >= hash_table->max) {
        return 0; // FULL
    }
    for(try = 0; true; try++) {
        hash = hash_fun(data->key, try, hash_table->max);
        if(hash_table->elements[hash] == 0) { // empty cell
            hash_table->elements[hash] = data;
            hash_table->number_of_elements++;
            return 1;
        }
    }
    return 0;
}

struct my_struct *hash_retrieve(int key, struct hash_table *hash_table) {
    int try, hash;
    for(try = 0; true; try++) {
        hash = hash_fun(key, try, hash_table->max);
        if(hash_table->elements[hash] == 0) {
            return 0; // Nothing found
        }
        if(hash_table->elements[hash]->key == key) {
            return hash_table->elements[hash];
        }
    }
    return 0;
}

И хотя бы метод удаления:

int hash_delete(int key, struct hash_table *hash_table) {
    int try, hash;
    for(try = 0; true; try++) {
        hash = hash_fun(key, try, hash_table->max);
        if(hash_table->elements[hash] == 0) {
            return 0; // Nothing found
        }
        if(hash_table->elements[hash]->key == key) {
            hash_table->number_of_elements--;
            hash_table->elements[hash] = 0;
            return 1; // Success
        }
    }
    return 0;
}

Answer 2

Объявите поле value как void *value.

Таким образом, вы можете использовать любой тип данных в качестве значения, но ответственность за его распределение и освобождение будет делегирована клиентскому коду.

Answer 3

Это действительно зависит от распределения вашего ключевого поля.Например, если это уникальное значение всегда в диапазоне от 0 до 255 включительно, просто используйте key % 256 для выбора сегмента, и вы получите идеальный хеш.

Если оно равномерно распределено по всем возможным значениям int, любоеФункция, которая дает вам одинаково распределенное значение хеша (например, вышеупомянутый key % 256), хотя и с несколькими значениями в каждом сегменте.

Не зная распределения, говорить об эффективных хешах немного сложно.