Публикуя это, я заметил, что есть довольно здесь уже есть несколько похожих реализаций хеш-таблицы 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;
}
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-битному пространству. Я серьезно сомневаюсь, что он будет хорошо работать после обрезки в более узком пространстве.
Хороший заголовочный файл
…. помимо 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;
Спасибо! Хорошие моменты в переносе непубличных вещей на ht.c. Хорошая находка на
_ht_expand
утечка памяти! Я не уверен насчетht_destroy
освобождение значений — пользователь может выделить блок значений и указать на него, поэтому ему нужен контроль. Re FNV и вырезка — интересный момент. Похоже isthe.com/chongo/tech/comp/fnv есть полезная информация.— Бен Хойт
FNV, кажется, имеет довольно хорошую «дисперсию» (как ее называют) для хешей, которые являются степенями двойки. Однако я только что заметил, что FNV-1a работает намного лучше, чем FNV-1 для подобных ключей, таких как
key1
,key2
и т.д. Так что думаю перейду на 1а.— Бен Хойт