Хеш-таблица, реализованная на C с открытой адресацией

Question 1

Публикуя это, я заметил, что есть довольно здесь уже есть несколько похожих реализаций хеш-таблицы C. Так что я решил, что еще один не повредит. 🙂 В любом случае, я пишу обучающую статью о том, «как реализовать хеш-таблицу на C», и мне интересно, могу ли я получить отзывы о своей реализации (ht.h и ht.c, с примером использования в demo.c). Цель нет максимальная производительность, но простота и хороший стиль.

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

Несколько замечаний о дизайне C API:

Для простоты мы используем строки в стиле C, оканчивающиеся NUL. Я знаю, что есть более эффективные подходы к обработке строк, но они подходят для стандартной библиотеки C.
В ht_set функция выделяет и копирует ключ (если вставляете впервые). Обычно вы не хотите, чтобы вызывающий абонент беспокоился об этом или о том, чтобы память ключей оставалась работоспособной. Обратите внимание, что ht_set возвращает указатель на дублированный ключ. В основном это используется как сигнал об ошибке «нехватки памяти» — в случае ошибки возвращается NULL.
Значения не могут быть NULL. Это делает возвращаемое значение ht_get немного проще (NULL означает отсутствие и не может означать значение NULL). Я не уверен, хорошая это идея или нет.
Есть несколько способов сделать итерацию. Использование явного типа итератора с циклом while кажется простым и естественным в C (см. Пример ниже). Значение, возвращаемое из ht_iterator — это значение, а не указатель, как для эффективности, так и для того, чтобы вызывающему абоненту не нужно было ничего освобождать.
Нет никаких ht_remove для удаления элемента из хеш-таблицы. Это было бы несложно написать, но мне не часто нужно удалять элементы при использовании хеш-таблицы, поэтому для простоты я оставил это.

ht.h:

#ifndef _HT_H
#define _HT_H

#include <stdbool.h>
#include <stddef.h>

// Hash table entry (this is not actually part of the public API).
typedef struct {
    char* key;
    void* value;
} _ht_entry;

// Hash table structure: create with ht_create, free with ht_destroy.
typedef struct {
    // Don't use these fields directly.
    _ht_entry* _entries; // hash buckets (entry.key != NULL if populated)
    size_t _capacity;    // size of _entries array
    size_t _length;      // number of items in hash table
} ht;

// Hash table iterator: create with ht_iterator, iterate with ht_next.
typedef struct {
    char* key;      // current key
    void* value;    // current value

    // Don't use these fields directly.
    ht* _table;     // reference to hash table being iterated
    size_t _index;  // current index into ht._entries
} hti;

// Create new hash table and return pointer to it, or NULL if out of
// memory.
ht* ht_create(void);

// Free memory allocated for hash table, including allocated keys.
void ht_destroy(ht* table);

// Get item with given key (NUL-terminated) from hash table. Return
// value (which was set with ht_set), or NULL if key not found.
void* ht_get(ht* table, const char* key);

// Set item with given key (NUL-terminated) to value (which must not
// be NULL). If not already present in table, key is copied to newly
// allocated memory (keys are freed automatically when ht_destroy is
// called). Return address of copied key, or NULL if out of memory.
const char* ht_set(ht* table, const char* key, void* value);

// Return number of items in hash table.
size_t ht_length(ht* table);

// Return new hash table iterator (for use with ht_next).
hti ht_iterator(ht* table);

// Move iterator to next item in hash table, update iterator's key
// and value to current item, and return true. If there are no more
// items, return false. Don't call ht_set during iteration.
bool ht_next(hti* it);

#endif // _HT_H

ht.c:

#include "ht.h"

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

#define INITIAL_SIZE 8

static ht* _ht_create(size_t size) {
    // Allocate space for hash table struct.
    ht* table = malloc(sizeof(ht));
    if (table == NULL) {
        return NULL;
    }
    table->_length = 0;
    table->_capacity = size * 2;

    // Allocate (zero'd) space for entry buckets.
    table->_entries = calloc(table->_capacity, sizeof(_ht_entry));
    if (table->_entries == NULL) {
        free(table); // error, free table before we return!
        return NULL;
    }
    return table;
}

ht* ht_create(void) {
    return _ht_create(INITIAL_SIZE);
}

void ht_destroy(ht* table) {
    // First free allocated keys.
    for (size_t i = 0; i < table->_capacity; i++) {
        if (table->_entries[i].key != NULL) {
            free(table->_entries[i].key);
        }
    }

    // Then free entries array and table itself.
    free(table->_entries);
    free(table);
}

#define FNV_OFFSET 14695981039346656037UL
#define FNV_PRIME 1099511628211UL

// Return 64-bit FNV-1 hash for key (NUL-terminated). See description at:
// https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
static uint64_t _hash(const char* key) {
    uint64_t hash = FNV_OFFSET;
    for (const char* p = key; *p; p++) {
        hash *= FNV_PRIME;
        hash ^= (uint64_t)(*p);
    }
    return hash;
}

void* ht_get(ht* table, const char* key) {
    // AND hash with capacity-1 to ensure it's within entries array.
    uint64_t hash = _hash(key);
    size_t index = (size_t)(hash & (uint64_t)(table->_capacity - 1));

    // Loop till we find an empty entry.
    while (table->_entries[index].key != NULL) {
        if (strcmp(key, table->_entries[index].key) == 0) {
            // Found key, return value.
            return table->_entries[index].value;
        }
        // Key wasn't in this slot, move to next (linear probing).
        index++;
        if (index >= table->_capacity) {
            // At end of entries array, wrap around.
            index = 0;
        }
    }
    return NULL;
}

// Expand hash table to twice its current size. Return true on success,
// false if out of memory.
static bool _ht_expand(ht* table) {
    // Creating new table so we can use ht_set to move items into it.
    ht* new_table = _ht_create(table->_capacity);
    if (new_table == NULL) {
        return false;
    }

    // Iterate entries, move all non-empty ones to new table's entries.
    for (size_t i = 0; i < table->_capacity; i++) {
        _ht_entry entry = table->_entries[i];
        if (entry.key != NULL) {
            const char* key = ht_set(new_table, entry.key, entry.value);
            if (key == NULL) {
                ht_destroy(new_table);
                return false;
            }
        }
    }

    // Free old entries array and update this table's details.
    free(table->_entries);
    table->_entries = new_table->_entries;
    table->_capacity = new_table->_capacity;

    // Free new table structure (we've updated the existing one).
    free(new_table);
    return true;
}

const char* ht_set(ht* table, const char* key, void* value) {
    assert(value != NULL);
    if (value == NULL) {
        return NULL;
    }

    // AND hash with capacity-1 to ensure it's within entries array.
    uint64_t hash = _hash(key);
    size_t index = (size_t)(hash & (uint64_t)(table->_capacity - 1));

    // If length will exceed half of current capacity, expand it.
    if (table->_length >= table->_capacity / 2) {
        if (!_ht_expand(table)) {
            return NULL;
        }
        // Recalculate index as capacity has changed.
        index = (size_t)(hash & (uint64_t)(table->_capacity - 1));
    }

    // Loop till we find an empty entry.
    while (table->_entries[index].key != NULL) {
        if (strcmp(key, table->_entries[index].key) == 0) {
            // Found key (it already exists), update value.
            table->_entries[index].value = value;
            return table->_entries[index].key;
        }
        // Key wasn't in this slot, move to next (linear probing).
        index++;
        if (index >= table->_capacity) {
            // At end of entries array, wrap around.
            index = 0;
        }
    }

    // Didn't find key, allocate/copy key and insert it.
    char* key_copy = strdup(key);
    if (key_copy == NULL) {
        return NULL;
    }
    table->_entries[index].key = key_copy;
    table->_entries[index].value = value;
    table->_length++; // be sure to update length
    return key_copy;
}

size_t ht_length(ht* table) {
    return table->_length;
}

hti ht_iterator(ht* table) {
    hti it;
    it._table = table;
    it._index = 0;
    return it;
}

bool ht_next(hti* it) {
    // Loop till we've hit end of entries array.
    ht* table = it->_table;
    while (it->_index < table->_capacity) {
        size_t i = it->_index;
        it->_index++;
        if (table->_entries[i].key != NULL) {
            // Found next non-empty item, update iterator key and value.
            _ht_entry entry = table->_entries[i];
            it->key = entry.key;
            it->value = entry.value;
            return true;
        }
    }
    return false;
}

А теперь простой пример использования:

demo.c:

#include "../ht.h"

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>

// Example:
// $ echo 'foo bar the bar bar bar the' | ./demo
// bar 4
// foo 1
// the 2
// 3

void exit_nomem(void) {
    fprintf(stderr, "out of memoryn");
    exit(1);
}

int main(void) {
    ht* counts = ht_create();
    if (counts == NULL) {
        exit_nomem();
    }

    // Read next word from stdin (at most 100 chars long).
    char word[101];
    while (scanf("%100s", word) != EOF) {
        // Look up word.
        void* value = ht_get(counts, word);
        if (value != NULL) {
            // Already exists, increment int that value points to.
            int* pcount = (int*)value;
            (*pcount)++;
            continue;
        }

        // Word not found, allocate space for new int and set to 1.
        int* pcount = malloc(sizeof(int));
        if (pcount == NULL) {
            exit_nomem();
        }
        *pcount = 1;
        if (ht_set(counts, word, pcount) == NULL) {
            exit_nomem();
        }
    }

    // Print out words and frequencies, freeing values as we go.
    hti it = ht_iterator(counts);
    while (ht_next(&it)) {
        printf("%s %dn", it.key, *(int*)it.value);
        free(it.value);
    }

    // Show the number of unique words.
    printf("%dn", (int)ht_length(counts));

    ht_destroy(counts);
    return 0;
}

Question 2

// Don't use these fields directly означает, что они не принадлежат общедоступному интерфейсу. Рассмотрите возможность объявления
```
  typedef struct ht ht;
```
в ht.h, и объясняя это в ht.c. То же самое для hti.
_ht_entry не должны быть видны клиенту; переместить свое объявление в ht.c также.
ht_set звонки _ht_expand. По очереди, _ht_expand звонки ht_set. Несмотря на то, что это (по-видимому) безопасно, все равно выглядит жутко.
Что хуже, ht_set делает strdup(key), но _ht_expand не освобождает старые ключи. Утечка памяти есть.
Значения должны быть постоянными, и я не вижу возможности для клиента не malloc их (демонстрационный код, кажется, со мной согласен). тем не мение ht_destroy не освобождает их. Это еще одна причина утечки памяти.
Я не уверен, что вам следует форсировать FNV. Пользователь, который знает характер распределения ключей, может захотеть использовать другой алгоритм хеширования. Кроме того, FNV хорошо разбросана по всему 64-битному пространству. Я серьезно сомневаюсь, что он будет хорошо работать после обрезки в более узком пространстве.

Question 3

Хороший заголовочный файл

…. помимо struct определения, принадлежащие файлу .c.

Слабый хеш

Код OP использует только наименьшее количество битов hash формировать index и так это ht упражнения полностью зависят от качества _hash().

// Only uses a few bits of `hash`
size_t index = (size_t)(hash & (uint64_t)(table->_capacity - 1));

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

Размер по отношению к объекту, на который указывает ссылка, а не по типу.

Рассмотрим ниже. Является sizeof(_ht_entry) правильный? Чтобы проверить, мне нужно было найти тип table (где-нибудь в начале функции) найдите ht, ищи ht определение (оно находится в другом файле).

// size by type: easy to code worng, slow to review, more maintenance on change.
table->_entries = calloc(table->_capacity, sizeof(_ht_entry));

Вместо этого рассмотрите

table->_entries = calloc(table->_capacity, sizeof table->_entries[0]);
// or
table->_entries = calloc(table->_capacity, sizeof *(table->_entries));

Легко правильно кодировать, проверять и поддерживать. Не нужно смотреть вверх table, ни _entries определение.

Держите пустые столы маленькими

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

Начальный _ht_create(INITIAL_SIZE) тратить память в таких случаях. Рассматривать _ht_create(0) вместо этого и соответствующим образом скорректируйте код. Это первое распределение до необходимости не дает много денег.

Баг в угловом корпусе

(OP не использует _ht_create(0) пока, но …)

Ниже приведены тесты на нехватку памяти table->_entries == NULL, но NULL является приемлемым возвращаемым значением, когда table->_capacity == 0. (C17 несколько решает этот вопрос, но недостаточно).

table->_entries = calloc(table->_capacity, sizeof(_ht_entry));
// if (table->_entries == NULL) {
// Suggest
if (table->_entries == NULL && table->_capacity > 0) {

Отбросьте префикс _

В этом нет необходимости.

Как установить / получить NULL данные

Я не согласен с ограничением использования «Значения не могут быть NULL».

С «NULL, если ключ не найден» подразумевает двусмысленность, если ранее сохраненное значение было NULL.

Вместо того, чтобы смешивать результат get() с зарезервированным значением указателя отделите флаг ошибки от данных. Значение данных должно быть разрешено Любые void *.

const

Функция заслуживает того, чтобы быть const по обычным причинам самостоятельной документации и расширенного использования.

// size_t ht_length(ht* table);
size_t ht_length(const ht* table);

Инициализировать весь итератор

hti ht_iterator(ht* table) {
    //hti it;
    //it._table = table;
    //it._index = 0;
    hti it = { ._table = table, ._index = 0 }; // other members become 0
    return it;
}

Сокращаться

жду с нетерпением ht_remove().

Нет поддержки для удаления записей или сжатия таблицы, кроме уничтожения.

Незначительный: L не нужно

//#define FNV_OFFSET 14695981039346656037UL
//#define FNV_PRIME 1099511628211UL
#define FNV_OFFSET 14695981039346656037U
#define FNV_PRIME 1099511628211U

Незначительное: избегайте расширения знака

// hash ^= (uint64_t)(*p);
hash ^= *(unsigned char *)p;

Хеш-таблица, реализованная на C с открытой адресацией

2 ответа
2

Добавить комментарий Отменить ответ

2 ответа 2

Похожие записи:

Добавить комментарий Отменить ответ

2 ответа
2