Попытка чистой реализации этой важной структуры данных на C.

Трудно сделать такие структуры универсальными в C без потери производительности, поэтому мы специализируемся на char* ключи и int values, но использует некоторые псевдонимы типов, так что для изменения типа ключа или значения нужно изменить только несколько мест.

Хеш-таблица динамически увеличивается в 2 раза, когда используется 80% слотов для поддержания высокой эффективности.

В качестве демонстрации мы разбираем полное собрание сочинений Шекспира, вызов ht_inc() за каждое слово. Затем постройте плоское «представление» хеш-таблицы, отсортируйте и запишите 10 самых распространенных слов. На моей машине вся задача занимает всего 50 мсек.

Отзывы о качестве стиля кодирования.

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef char* ht_key_t;
typedef int   ht_value_t;

// key => value plus pointer to next item for hash collisions
typedef struct HashTableItem HashTableItem;
struct HashTableItem {
  ht_key_t       key;
  ht_value_t     value;
  HashTableItem* next;
};

// Array of pointers to HashTableItems, plus counters
typedef struct HashTable {
  HashTableItem** slots;
  size_t          size;      // how many slots are there
  size_t          scount;    // how many slots are used
  size_t          itemcount; // how many items are there
} HashTable;

// Creates a new HashTableItem 
HashTableItem* ht_create_item(ht_key_t key, ht_value_t value) {
  HashTableItem* item = malloc(sizeof *item);
  if (!item) {
    perror("malloc item");
    exit(EXIT_FAILURE);
  }
  item->key   = strdup(key); // take a copy
  item->value = value;
  item->next  = NULL;
  return item;
}

// Creates a new HashTable
HashTable* ht_create(size_t size) {
  HashTable* table = malloc(sizeof *table);
  if (!table) {
    perror("malloc table");
    exit(EXIT_FAILURE);
  }
  table->size      = size;
  table->scount    = 0;
  table->itemcount = 0;
  table->slots     = calloc(table->size, sizeof *table->slots); // NOLINT
  if (!table->slots) {
    perror("calloc items");
    exit(EXIT_FAILURE);
  }
  return table;
}

// Frees an item depending on their types, if the key or value members
// need freeing that needs to happen here too
void ht_free_item(HashTableItem* item) {
  free(item->key);
  free(item);
}

// Frees the whole hashtable
void ht_free(HashTable* table) {
  // free the HashTableItems in the linked lists
  for (size_t i = 0; i < table->size; i++) {
    HashTableItem* item = table->slots[i];
    while (item) {
      HashTableItem* next = item->next;
      ht_free_item(item);
      item = next;
    }
  }
  // free the array of pointers to HashTableItems
  free(table->slots);
  free(table);
}

// hash function. crucial to efficient operation
// returns value in range [0, size)
// an appropriate hash function for short strings is FNV-1a
// https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function#FNV-1a_hash
size_t ht_hash(size_t size, const char* str) {
  uint64_t hash = 0xcbf29ce484222325; // FNV_offset_basis
  while (*str) hash = (hash ^ (uint8_t)*str++) * 0x100000001b3; // FNV_prime
  return hash % size;                                           // fit to table
}

void ht_grow(HashTable* table) {
  table->scount++;
  if (table->scount * 100 / table->size >= 80) {
    size_t          nsize  = table->size * 2;
    HashTableItem** nslots = calloc(nsize, sizeof *table->slots); // NOLINT
    if (!nslots) {
      perror("calloc nitems");
      exit(EXIT_FAILURE);
    }

    size_t ncount = 0;
    for (size_t i = 0; i < table->size; i++) {
      HashTableItem* item = table->slots[i];
      while (item) {
        HashTableItem*  next  = item->next; // save next
        HashTableItem** nslot = &nslots[ht_hash(nsize, item->key)];
        if (!*nslot) ++ncount;
        item->next = *nslot; // push into new list
        *nslot     = item;
        item       = next;
      }
    }
    free(table->slots);
    table->scount = ncount;
    table->size   = nsize;
    table->slots  = nslots;
  }
}

// Inserts an item (or updates if exists)
void ht_insert(HashTable* table, ht_key_t key, ht_value_t value) {
  HashTableItem** slot           = &table->slots[ht_hash(table->size, key)];
  HashTableItem*  item           = *slot;
  bool            direct_slot     = true;
  while (item) {
    if (strcmp(item->key, key) == 0) {
      // exists, update value, free old value if needed
      item->value = value;
      return;
    }
    slot           = &item->next;
    item           = *slot;
    direct_slot     = false;
  }
  *slot = ht_create_item(key, value); // new entry
  ++table->itemcount;
  if (direct_slot) ht_grow(table); // HashTable accounting
}

// increments the value for a key or inserts with value = 1
// specialised for ht_value_t=int and faster than search then update.
void ht_inc(HashTable* table, ht_key_t key) {
  HashTableItem** slot           = &table->slots[ht_hash(table->size, key)];
  HashTableItem*  item           = *slot;
  bool            direct_slot     = true;
  while (item) {
    if (strcmp(item->key, key) == 0) {
      ++item->value;
      return;
    }
    slot           = &item->next;
    item           = *slot;
    direct_slot     = false;
  }
  *slot = ht_create_item(key, 1); // not found, init with one
  ++table->itemcount;
  if (direct_slot) ht_grow(table); // HashTable accounting
}

// Deletes an item from the table
void ht_delete(HashTable* table, ht_key_t key) {
  HashTableItem** slot           = &table->slots[ht_hash(table->size, key)];
  HashTableItem*  item           = *slot;
  bool            direct_slot     = true;
  while (item) {
    if (strcmp(item->key, key) == 0) {
      *slot = item->next; // remove item from linked list
      ht_free_item(item);
      --table->itemcount;
      if (direct_slot) --table->scount; // HashTable accounting
      return;
    }
    slot           = &item->next;
    item           = *slot;
    direct_slot     = false;
  }
}

// Searches the key in the hashtable
// and returns NULL ptr if it doesn't exist
HashTableItem* ht_search(HashTable* table, ht_key_t key) {
  HashTableItem* item = table->slots[ht_hash(table->size, key)];
  while (item) {
    if (strcmp(item->key, key) == 0) return item;
    item = item->next;
  }
  return NULL;
}

// debug printing. customise printf format strings by key & value types
void ht_print(HashTable* table) {
  printf("n---- Hash Table ---n");
  for (size_t i = 0; i < table->size; i++) {
    printf("@%zu: ", i);
    HashTableItem* item = table->slots[i];
    while (item) {
      printf("%s => %d | ", item->key, item->value);
      item = item->next;
    }
    printf("n");
  }
  printf("-------------------n");
}

// debug printing. customise printf format strings by key & value types
void ht_print_search(HashTable* table, ht_key_t key) {
  HashTableItem* val;
  if ((val = ht_search(table, key)) == NULL) {
    printf("Key:%s does not existn", key);
    return;
  }
  printf("Key:%s => %dn", key, val->value);
}

static inline bool ht_is_alpha(char c) {
  return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z');
}
static inline char ht_tolower(char c) { return (c < 'a') ? c + 'a' - 'A' : c; }

int cmp_ht_items(const void* a, const void* b) {
  int a_val = (*(HashTableItem**)a)->value;
  int b_val = (*(HashTableItem**)b)->value;
  if (a_val == b_val) return 0;
  return a_val < b_val ? 1 : -1;
}

int main() {
  // some tests
  HashTable* ht = ht_create(4);
  ht_insert(ht, "1", 10);
  ht_insert(ht, "2", 20);
  ht_insert(ht, "Hel3", 30);
  ht_insert(ht, "Cau4", 40);
  ht_print(ht);
  ht_insert(ht, "Cau6", 60); // grow!
  ht_print(ht);
  ht_inc(ht, "11"); // increment
  ht_inc(ht, "21"); // increment
  ht_inc(ht, "31"); // increment
  ht_inc(ht, "41"); // increment
  ht_inc(ht, "51"); // increment
  ht_inc(ht, "61"); // increment
  ht_inc(ht, "71"); // increment
  ht_inc(ht, "81"); // increment and grow again
  ht_print(ht);

  ht_print_search(ht, "1");
  ht_print_search(ht, "2");
  ht_print_search(ht, "3");
  ht_print_search(ht, "Hel3");
  ht_print_search(ht, "Cau4");

  ht_insert(ht, "Cau6", 61); // update
  ht_inc(ht, "1");           // increment
  ht_inc(ht, "Hel3");        // increment
  ht_inc(ht, "new");         // increment
  ht_print(ht);

  ht_delete(ht, "Hel3");
  ht_delete(ht, "Cau6");
  ht_delete(ht, "1");
  ht_print(ht);

  ht_free(ht);
  // end of tests

  // shakespeare demo
  FILE* fp = fopen("shakespeare.txt", "re");
  if (!fp) {
    perror("fopen");
    exit(EXIT_FAILURE);
  }
  ht = ht_create(32 * 1024);

#define BUFSIZE 1024
#define WORDSIZE 50
  char  buf[BUFSIZE];
  char  word[WORDSIZE];
  char* word_ptr = word;
  while (!ferror(fp) && !feof(fp)) {
    size_t bytes_read = fread(buf, 1, BUFSIZE, fp);
    char*  buf_ptr    = buf;
    while ((buf_ptr < buf + bytes_read)) {
      char c = *buf_ptr;
      if (ht_is_alpha(c)) {
        *(word_ptr++) = ht_tolower(c);
        if (word_ptr - word == WORDSIZE - 1) { // -1 for NULL terminator
          fputs("word too long. terminatingn", stderr);
          exit(EXIT_FAILURE);
        }
      } else if (word_ptr == word) {
        // ignore repeated terminators
      } else {
        *(word_ptr++) = '';
        ht_inc(ht, word); // record
        word_ptr = word;  // restart new word
      }
      ++buf_ptr; // next char from buf
    }
  }
  fclose(fp);

  // build a flat view of the hashtable items
  HashTableItem** itemview = malloc(ht->itemcount * sizeof *itemview); // NOLINT
  if (!itemview) {
    perror("malloc itemview");
    exit(EXIT_FAILURE);
  }
  HashTableItem** curritem = itemview;
  for (size_t i = 0; i < ht->size; i++) {
    HashTableItem* item = ht->slots[i];
    while (item) {
      *curritem++ = item;
      item        = item->next;
    }
  }
  // now sort that view and print the top 10
  qsort(itemview, ht->itemcount, sizeof *itemview, cmp_ht_items); // NOLINT
  for (size_t i = 0; i < 10; i++)
    printf("%s => %dn", itemview[i]->key, itemview[i]->value);

  free(itemview);

  // ht_print(ht);
  ht_free(ht);
}

Используйте больше calloc()

я хотел бы использовать calloc() почти везде. Это гарантирует, что память обнулена, поэтому у вас не будет сюрпризов, если вы забудете инициализировать переменную-член. Я бы не стал сильно беспокоиться о производительности; компилятор должен иметь возможность оптимизировать обнуление, если он видит, что вы устанавливаете для переменной-члена что-то другое. Итак, используйте его в ht_create_item() и ht_create() где вы в настоящее время используете malloc().

Старайтесь избегать косвенного обращения

В вашей хеш-таблице есть массив slots который содержит указатели на элементы, однако сами элементы довольно маленькие, это всего лишь два указателя и int. Поскольку вы стремитесь к коэффициенту загрузки от 0,4 до 0,8, он будет использовать меньше памяти для устранения косвенного обращения:

typedef struct HashTable {
  HashTableItem* slots;
  ...
} HashTable;

Это также должно дать небольшой прирост производительности.

Избегайте дублирования кода

ht_inc() и ht_delete() выглядят очень похоже. Можно было бы выделить общие части в отдельную функцию. Я думаю, вы можете сделать это, создав функцию, которая находит указатель на то, где должен быть / идти элемент, и возвращает указатель на этот указатель. По сути, ht_search() который возвращает слот вместо самого элемента.

static HashTableItem** ht_search_slot(HashTable* table, ht_key_t key, bool *direct) {
  HashTableItem** slot = &table->slots[ht_hash(table->size, key)];
  *direct = true;
  while (*slot) {
    if (strcmp((*slot)->key, key) == 0) break;
    *direct = false;
    slot = &(*slot)->next;
  }
  return slot;
}

void ht_inc(HashTable* table, ht_key_t key) {
  bool direct_slot;
  HashTableItem** slot = ht_search_slot(table, key, &direct_slot);
  HashTableItem*  item = *slot;
  if (item) {
    ++item->value;
    return;
  }
  *slot = ht_create_item(key, 1); // not found, init with one
  ++table->itemcount;
  if (direct_slot) ht_grow(table); // HashTable accounting
}

void ht_delete(HashTable* table, ht_key_t key) {
  bool direct_slot;
  HashTableItem** slot = ht_search_slot(table, key, &direct_slot);
  HashTableItem*  item = *slot;
  if (item) {
    *slot = item->next; // remove item from linked list
    ht_free_item(item);
    --table->itemcount;
    if (direct_slot) --table->scount; // HashTable accounting
  }
}

HashTableItem* ht_search(HashTable* table, ht_key_t key) {
  bool direct_slot;
  return *ht_search_slot(table, key, &direct_slot);
}

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

Всегда звонить ht_grow() при вставке элементов

Ты только звонишь ht_grow() когда используется пустой прямой слот. Однако, если элемент вставлен в уже используемый слот, вы его не вызываете. Это означает, что если вам не повезло, все хешируется в один и тот же слот, и вы никогда не сможете расти и балансировать. Я бы перестраховался и просто безоговорочно позвонил ht_grow() при вставке элемента. Конечно, ht_grow() следует использовать itemcount вместо scount чтобы проверить, нужно ли увеличивать хеш-таблицу.

Избегайте операций деления и по модулю

Деления (а значит, и операции по модулю) довольно дороги. Я бы избегал их, следя за тем, чтобы размер хеш-таблицы всегда был степенью двойки. А если вы проследите, чтобы размер был не менее 16 элементов, то вы можете заменить чек в ht_grow() по:

if (table->itemcount >= 13 * (table->size >> 4)) {
  ...
}

Это приведет к изменению размера, когда хеш-таблица заполнена на 81,25%. Вы даже можете избавиться от умножения, сохранив двоичный логарифм размера, но если вы не планируете запускать этот код на микроконтроллерах, я бы не стал беспокоиться об этом. А в хэш-функции вы можете заменить модуль следующим образом:

return hash & (size - 1);