В комментарии OP упомянули, что они лучше учатся на примере.(Это не ответ как таковой, а только пример. Пожалуйста, рассмотрите это скорее расширенный комментарий, а не ответ.)
Тогда давайте рассмотрим простой, реальный пример;но что-то, что нельзя просто скопировать и представить как собственную работу.
Давайте предположим, что нам нужна хеш-таблица текста или токенов, скажем
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
struct hashentry {
struct hashentry *next;
size_t hash;
unsigned char data[];
};
struct hashtable {
size_t size;
struct hashentry **slot;
};
, где сама таблица являетсяМассив указателей и коллизий хешей решаются с помощью цепочки.Обратите внимание, что вместо пар ключ-значение я, по сути, использую только ключи;это сделано для того, чтобы избежать копирования и вставки этого примера кода как чьей-то собственной работы.Я написал это, чтобы помочь новым программистам понять, а не для мошенников, чтобы представить их в качестве домашней работы.(Я не имею в виду OP, эти вопросы часто можно найти с помощью веб-поиска, и я пишу эти ответы для всей группы, а не только для спрашивающего.)
Инициализация таблицы для определенного размера:
static inline void hashtable_init(struct hashtable *const ht, const size_t size)
{
size_t i;
if (!ht) {
fprintf(stderr, "hashtable_init(): No hashtable specified (ht == NULL).\n");
exit(EXIT_FAILURE);
} else
if (size < 1) {
fprintf(stderr, "hashtable_init(): Invalid hashtable size (size == %zu).\n", size);
exit(EXIT_FAILURE);
}
/* Allocate an array of pointers. */
ht->slot = calloc(size, sizeof ht->slot[0]);
if (!ht->slot) {
fprintf(stderr, "hashtable_init(): Failed to allocate an array of %zu slots.\n", size);
exit(EXIT_FAILURE);
}
ht->size = size;
/* Mark each slot unused. (On all current architectures, this is unnecessary,
as calloc() does initialize the pointers to NULL, but let's do it anyway.) */
for (i = 0; i < size; i++)
ht->slot[i] = NULL;
}
Для хэш-функции мне нравится вариант DJB2 Xor для текстовых строк.Это не особенно хорошо (будут столкновения), но это очень просто и быстро:
static inline size_t hash_data(const char *data, const size_t datalen)
{
const char *const ends = data + datalen;
size_t hash = 5381;
while (data < ends)
hash = (33 * hash) ^ (unsigned char)(*(data++));
return hash;
}
Обратите внимание, что я использую size_t в качестве типа для хэша.Вы можете использовать любой тип, который вам нужен, но на большинстве архитектур он имеет тот же размер, что и указатель.
Чтобы добавить запись данных в хеш-таблицу:
static inline void hashtable_add(struct hashtable *ht, const char *data, const size_t datalen)
{
struct hashentry *entry;
size_t hash, slotnum;
if (!ht) {
fprintf(stderr, "hashtable_add(): No hashtable specified (ht == NULL).\n");
exit(EXIT_FAILURE);
} else
if (ht->size < 1) {
fprintf(stderr, "hashtable_add(): Hashtable has zero size.\n");
exit(EXIT_FAILURE);
} else
if (!data && datalen > 0) {
fprintf(stderr, "hashtable_add(): data is NULL, but datalen == %zu.\n", datalen);
exit(EXIT_FAILURE);
}
/* Allocate memory for the entry, including the data, and the string-terminating nul '\0'. */
entry = malloc(sizeof (struct hashentry) + datalen + 1);
if (!entry) {
fprintf(stderr, "hashtable_add(): Out of memory (datalen = %zu).\n", datalen);
exit(EXIT_FAILURE);
}
/* Copy the data, if any. */
if (datalen > 0)
memcpy(entry->data, data, datalen);
/* Ensure the data is terminated with a nul, '\0'. */
entry->data[datalen] = '\0';
/* Compute the hash. */
hash = hash_data(data, datalen);
entry->hash = hash;
/* The slot number is the hash modulo hash table size. */
slotnum = hash % ht->size;
/* Prepend entry to the corresponding slot chain. */
entry->next = ht->slot[slotnum];
ht->slot[slotnum] = entry;
}
КогдаСначала я пишу код, подобный описанному выше, я всегда пишу его как тестовую программу и тестирую.(Технически это подпадает под парадигму модульного тестирования .)
В этом случае мы можем просто взять число слотов в качестве параметра командной строки и считать каждую строку из стандартного ввода какданные, которые будут добавлены в хеш-таблицу.
Поскольку стандарт C не поддерживает getline(), вместо этого лучше использовать fgets() с линейным буфером фиксированного размера.Если мы объявим
#ifndef MAX_LINE_LEN
#define MAX_LINE_LEN 16383
#endif
, у нас будет макрос препроцессора MAX_LINE_LEN, который по умолчанию равен 16383, но может быть переопределен во время компиляции с помощью параметров компилятора.(С GCC, Intel CC и clang вы можете использовать, например, -DMAX_LINE_LEN=8191, чтобы разделить его пополам.)
В main() мне нравится распечатывать использование, если счетчик параметров неверен, или -hили --help - первый параметр:
int main(int argc, char *argv[])
{
char buffer[MAX_LINE_LEN + 1];
char *line;
size_t size, i;
struct hashtable table;
char dummy;
if (argc != 2 || !strcmp(argv[1], "-h") || !strcmp(argv[1], "--help")) {
fprintf(stderr, "\n");
fprintf(stderr, "Usage: %s [ -h | --help ]\n", argv[0]);
fprintf(stderr, " %s ENTRIES < DATA-FILE > DOT-FILE\n", argv[0]);
fprintf(stderr, "\n");
fprintf(stderr, "This program reads lines from DATA-FILE, adding them to\n");
fprintf(stderr, "a hash table with ENTRIES slots and hash chaining.\n");
fprintf(stderr, "When all input lines have been read, the contents of the\n");
fprintf(stderr, "hash table slots will be output as a Graphviz DOT format graph.\n");
fprintf(stderr, "\n");
return EXIT_SUCCESS;
}
Далее мы можем попытаться разобрать первый параметр командной строки в size_t size;.Мне нравится использовать символ «страж», чтобы определить, не содержит ли параметр мусор после значения (кроме пробелов):
if (sscanf(argv[1], "%zu %c", &size, &dummy) != 1 || size < 1) {
fprintf(stderr, "%s: Invalid number of hash table entries.\n", argv[1]);
return EXIT_FAILURE;
}
hashtable_init(&table, size);
Следующая часть - прочитать каждую строку из стандартного ввода и добавить ихк хеш-таблице.
while (1) {
line = fgets(buffer, sizeof buffer, stdin);
if (!line)
break;
/* Skip leading ASCII whitespace. */
line += strspn(line, "\t\n\v\f\r ");
/* Find out the remaining length of the line. */
size = strlen(line);
/* Ignore trailing ASCII whitespace. */
while (size > 0 && (line[size-1] == '\t' || line[size-1] == '\n' ||
line[size-1] == '\v' || line[size-1] == '\f' ||
line[size-1] == '\r' || line[size-1] == ' '))
size--;
/* Ignore empty lines. */
if (size < 1)
continue;
/* Add line to the hash table. */
hashtable_add(&table, line, size);
}
/* Check if fgets() failed due to an error, and not EOF. */
if (ferror(stdin) || !feof(stdin)) {
fprintf(stderr, "Error reading from standard input.\n");
return EXIT_FAILURE;
}
На данный момент у нас есть table с size слотами.Я пишу свои тестовые программы для записи либо в виде простого текста (если он прост), либо в формате Graphviz DOT (если он структурирован как графики).В этом случае формат вывода графика звучит лучше.
/* Print the hash table contents as a directed graph, with slots as boxes. */
printf("digraph {\n");
for (i = 0; i < table.size; i++) {
struct hashentry *next = table.slot[i];
/* The slot box. */
printf(" \"%zu\" [ shape=\"box\", label=\"%zu\" ];\n", i, i);
if (next) {
/* The edge from the slot box to the entry oval. */
printf(" \"%zu\" -> \"%p\";\n", i, (void *)next);
while (next) {
struct hashentry *curr = next;
/* Each entry oval; text shown is the value read from the file. */
printf(" \"%p\" [ shape=\"oval\", label=\"%s\" ];\n", (void *)curr, curr->data);
next = next->next;
/* The edge to the next oval, if any. */
if (next)
printf(" \"%p\" -> \"%p\";\n", (void *)curr, (void *)next);
}
}
}
printf("}\n");
return EXIT_SUCCESS;
}
Вот и все.Если вы скомпилируете и запустите вышеупомянутую программу с 10 в качестве аргумента командной строки и подадите
one
two
three
four
five
six
seven
eight
nine
ten
на стандартный ввод, она выведет
digraph {
"0" [ shape="box", label="0" ];
"1" [ shape="box", label="1" ];
"1" -> "0xb460c0";
"0xb460c0" [ shape="oval", label="three" ];
"0xb460c0" -> "0xb46080";
"0xb46080" [ shape="oval", label="one" ];
"2" [ shape="box", label="2" ];
"3" [ shape="box", label="3" ];
"3" -> "0xb46180";
"0xb46180" [ shape="oval", label="nine" ];
"0xb46180" -> "0xb460a0";
"0xb460a0" [ shape="oval", label="two" ];
"4" [ shape="box", label="4" ];
"4" -> "0xb46160";
"0xb46160" [ shape="oval", label="eight" ];
"0xb46160" -> "0xb46140";
"0xb46140" [ shape="oval", label="seven" ];
"5" [ shape="box", label="5" ];
"5" -> "0xb46100";
"0xb46100" [ shape="oval", label="five" ];
"6" [ shape="box", label="6" ];
"6" -> "0xb461a0";
"0xb461a0" [ shape="oval", label="ten" ];
"7" [ shape="box", label="7" ];
"7" -> "0xb46120";
"0xb46120" [ shape="oval", label="six" ];
"0xb46120" -> "0xb460e0";
"0xb460e0" [ shape="oval", label="four" ];
"8" [ shape="box", label="8" ];
"9" [ shape="box", label="9" ];
}
, который передается вGraphviz dot сгенерирует хороший график:
Если вы хотите увидеть фактические значения хеша над строками данных, измените на
/* Each entry oval; text shown is the value read from the file. */
printf(" \"%p\" [ shape=oval, label=\"%zu:\\n%s\" ];\n", (void *)curr, curr->hash, curr->data);
Как я уже сказал, хеш DJB2 Xor не особенно хорош, и для вышеуказанного ввода вам нужно как минимум 43 слота хеш-таблицы, чтобы избежать цепочки.