Хэш-таблица с отдельной реализации сцепления в C


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

hashtable.h

#ifndef HASHTABLE_H
#define HASHTABLE_H


enum data_type {
    INTEGER, FLOAT, DOUBLE,
    CHARACTER, STRING,
    SET, LIST, HASH
};

struct node_t {
    char *key;
    void *value;
    enum data_type type;
    struct node_t *next, *prev;
};

struct hashtable_t {
    int size, used;
    struct node_t **table;
};

struct hashtable_t *create_ht();
void delete_ht(struct hashtable_t *ht);

void ht_insert(struct hashtable_t *ht, char *key, void *value, enum data_type type);
struct node_t *ht_search(struct hashtable_t *ht, char *key);
void ht_delete(struct hashtable_t *ht, char *key);
void ht_update(struct hashtable_t *ht, char *key, void *value, enum data_type type);


#endif // HASHTABLE_H

hashtable.c

#include "hashtable.h"

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

#define HT_INITIAL_SIZE 11


static int hash(char *key, int size) {
    long hash = strlen(key);
    for (int i = 0; i < strlen(key); ++key, ++i) {
        hash = ((hash << 5) ^ (hash >> 27)) ^ (*key);
        hash %= size;
    }

    return (int) hash;
}

static int check_prime(int n) {
    if (n <= 1)
        return 0;

    for (int i = 2; i*i <= n; i++) {
        if (n % i == 0)
            return 0;
    }

    return 1;
}

static int next_prime(int n) {
    while (check_prime(n) != 1)
        n++;

    return n;
}

static struct hashtable_t *create_new_sized_ht(int size) {
    struct hashtable_t *ht = malloc(sizeof(struct hashtable_t));
    ht->table = calloc((size_t) size, sizeof(struct node_t *));
    ht->size = size;
    ht->used = 0;

    return ht;
}

static void resize_ht(struct hashtable_t *ht, int size) {
    if (ht->used > size || size < HT_INITIAL_SIZE)
        return;

    struct hashtable_t *resized_ht = create_new_sized_ht(size);
    for (int i = 0; i < ht->size; i++) {
        struct node_t *nd = ht->table[i], *next;
        while (nd) {
            ht_insert(resized_ht, nd->key, nd->value, nd->type);
            nd = nd->next;
        }
    }

    ht->size = resized_ht->size;

    struct node_t **temp_table = ht->table;
    ht->table = resized_ht->table;
    resized_ht->table = temp_table;

    delete_ht(resized_ht);
}

static void resize_up_ht(struct hashtable_t *ht) {
    int size = next_prime(ht->size * 2);
    resize_ht(ht, size);
}

static void resize_down_ht(struct hashtable_t *ht) {
    int size = next_prime(ht->size / 2);
    resize_ht(ht, size);
}

struct hashtable_t *create_ht() {
    return create_new_sized_ht(HT_INITIAL_SIZE);
}

void delete_ht(struct hashtable_t *ht) {
    for (int i = 0; i < ht->size; i++) {
        struct node_t *head = ht->table[i], *next;
        while (head) {
            next = head->next;
            free(head);
            head = next;
        }
    }

    free(ht->table);
    free(ht);
}

void ht_insert(struct hashtable_t *ht, char *key, void *value, enum data_type type) {
    if (ht->used >= ht->size * 0.80)
        resize_up_ht(ht);

    int h = hash(key, ht->size);

    struct node_t *head = ht->table[h], *prev = NULL;
    while (head) {
        prev = head;
        head = head->next;
    }

    struct node_t *nd = malloc(sizeof(struct node_t));
    nd->key = key;
    nd->value = value;
    nd->type = type;
    nd->prev = prev;
    nd->next = NULL;

    if (prev)
        prev->next = nd;
    else
        ht->table[h] = nd;

    ht->used++;
}

struct node_t *ht_search(struct hashtable_t *ht, char *key) {
    int h = hash(key, ht->size);

    struct node_t *head = ht->table[h];
    while (head) {
        if (strcmp(head->key, key) == 0)
            return head;
        else
            head = head->next;
    }

    return NULL;
}

void ht_delete(struct hashtable_t *ht, char *key) {
    if (ht->used <= ht->size * 0.10)
        resize_down_ht(ht);

    struct node_t *nd = ht_search(ht, key);

    if (nd) {
        if (nd->prev && nd->next) {
            nd->prev->next = nd->next;
            nd->next->prev = nd->prev;
        } else if (!nd->prev) {
            ht->table[hash(nd->key, ht->size)] = nd->next;
        } else if (nd->prev && !nd->next) {
            nd->prev->next = NULL;
        }

        free(nd);
        ht->used--;
    }
}

void ht_update(struct hashtable_t *ht, char *key, void *value, enum data_type type) {
    struct node_t *nd = ht_search(ht, key);

    if (nd) {
        nd->value = value;
        nd->type = type;
    }
}


1175
6
задан 30 марта 2018 в 04:03 Источник Поделиться
Комментарии
1 ответ

Да, вы должны кое-что оптимизировать. Я буду краток в ответе на этот вопрос.


  • Ваш код не используя встроенные функции. Они необходимы для наилучшей производительности.

  • Ключ и значение должны быть выделены в качестве отдельных блоков памяти в вашем решении.

  • Ваш хэш-таблицы ограничен независимо от типов данных, которые вы определили.

  • Ваши ключи всегда должны быть строками

  • Ваш хэш-функция жестко и уязвим для атак при столкновении в отличии от например SipHash.

Посмотрите на ядре Linux container_of макросов и их реализация отдельно прикован хэш-таблицы. Это лучший хэш-таблицу реализации на языке Си. Просто не копируйте их использование фиксированной хеш-функции; позволяют использовать некоторые разумные почти криптографически безопасную хэш-функцию, как SipHash.

Ваш хэш-таблицы ограничен независимо от типов данных, которые вы определили. Ключ и значение должны быть указатели. Это ограничивает работу хэш-таблицы очень много.

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

Вот патч, который добавил хэш-таблице: https://lwn.net/Articles/510271/

Это содержит хэш-список сам: https://github.com/torvalds/linux/blob/master/include/linux/list.h

1
ответ дан 30 марта 2018 в 06:03 Источник Поделиться