Ви часто бачите, як інженери в інтернеті говорять про створення чогось з нуля. Я колись вважав, що немає сенсу писати все з нуля. Чому страждати, створюючи щось, якщо це вже майже досконало реалізовано?
Нещодавно я вирішив повернутися до програмування так, як це було на початку, коли я почав кодувати — насолоджуватися пробами і невдачами. Під час цього процесу я вирішив вивчати мову C. Можливо, ви запитаєте: чому C? Якщо чесно, я сам не знаю. Можливо, я просто хотів кинути собі виклик, чи мені сподобалася ідея відповідати на питання “Якими мовами програмування ви пишете?” і відповідати — C та Python.
У своєму шляху вивчення C я працював над проєктом, який дійшов до моменту, коли я мав використовувати HashTable (HashMap або Dictionary) для ефективного пошуку. Єдина проблема полягала в тому, що стандартна бібліотека C не має реалізації HashTable або HashSet.
Моя перша думка була — ігнорувати використання HashTable і застосувати масив (не список), але я уявив, скільки ітерацій моєму програмному забезпеченню доведеться зробити, щоб перевірити певний елемент. C швидкий, так, але чи хочу я ризикувати?
Тоді я вирішив створити структуру даних HashTable з нуля.
Примітка: Це не є підручником, який покроково проводить через процес створення HashTable з нуля.
Що таке HashTable?
HashTable — це структура даних, яка дозволяє зберігати та отримувати елемент ефективно у вигляді пари ключ-значення. Можливо, ви вже знайомі з цим. Якщо ви використовуєте Python, то це більше відоме як Словники, в інших мовах програмування це часто називають HashMaps або Maps.
Як працюють HashTable?
HashTable — це колекція Вузлів (Nodes). Кожен вузол є основним елементом, що містить ключ, значення та вказівник на інший вузол.
Воно працює так: спочатку збирається ключ і значення, що повинні бути збережені. Генерується хеш для ключа, додається ключ і значення до вузла, а вузол зберігається за індексом, створеним хеш-функцією.
Важливо зазначити, що за кожним HashTable стоїть хеш-функція (hash function). Ця хеш-функція створює індекс на основі ключа, який ми хочемо зберегти для певного вузла.
Вказівник вузла діє як вказівник на інший вузол, схожий на наступний вказівник у LinkedList. Він використовується для обробки колізій (collisions).
Колізія виникає, коли хеш одного ключа збігається з хешем іншого ключа. Хеш-функції створюються унікальними, щоб зменшити ймовірність цього результату, але ж, як відомо, Закон Мерфі, так?
Існують різні методи обробки колізій, для моєї реалізації я використовував метод ланцюгового розділення (separation chain) в деяких функціях. Метод ланцюгового розділення передбачає використання вказівника, який вказує на інший вузол, коли для двох різних ключів генерується той самий індекс.
Реалізація коду
По-перше, ми маємо встановити розмір нашого HashTable.
const int HASHTABLE_SIZE = 10;
У цьому випадку ми хочемо, щоб наш HashTable містив лише 10 значень.
Тепер створимо Вузол, який містить ключ, значення та вказівник на інший вузол (для обробки колізій).
typedef struct Node {
char *key;
char *value;
struct Node *ptrNode; // Обробляє колізії
} Node;
Далі створимо структуру HashTable, яка містить вузли.
typedef struct HashTable {
Node **nodes;
} HashTable;
Після визначення структур для вузлів та HashTable, нам потрібна функція, яка генерує хеш для конкретного ключа.
unsigned int hashFunction(char *key) {
int i = 0;
unsigned int hash = 0;
int prime = 31;
while (key[i] != '\0') {
hash = (hash * prime) + key[i];
i ++;
}
return hash % HASHTABLE_SIZE;
}
Хеш-функція приймає ключ і ініціалізує важливі значення, такі як hash та prime. Значення хешу позначене типом даних unsigned int.
Ми робимо це, тому що під час обчислення хешу ми можемо отримати велике ціле число, яке перевищує стандартне значення int, що може призвести до того, що залишки переповнюються, створюючи від'ємне значення.
СТВОРЕННЯ HASHTABLE
Функція createHashtable виділяє пам'ять для нашої структури HashTable, що дозволяє маніпулювати нею, використовуючи основні функції search, insert та get цієї структури даних.
Ця структура матиме розмір HASHTABLE_SIZE, з нульовим індексом (звісно). В кінці функція повертає вказівник на HashTable.
HashTable *createHashTable() {
HashTable *table = malloc(sizeof(HashTable));
if (!table) {
printf("Не вдалося виділити пам'ять");
exit(1);
}
table->node = malloc(sizeof(HashNode*) * HASHTABLE_SIZE);
for (int i = 0; i < HASHTABLE_SIZE; i++) {
table->node[i] = NULL;
}
return table;
}
ФУНКЦІЯ GET
Функція get використовується для отримання значення за ключем у вузлі HashTable.
char *get(HashTable *table, char *key) {
if (!table) {
printf("Невірна таблиця");
return NULL;
}
unsigned int hash = hash_function(key);
HashNode *node = table->buckets[hash];
if (!node) {
return NULL;
}
return node->value;
}
Щоб отримати значення за ключем, нам потрібен вказівник на HashTable та сам ключ. Спочатку перевіряємо вказівник, щоб впевнитись, що він не є NULL, тобто він вказує на коректну пам'ять — невірна посилання на HashTable.
Якщо вказівник веде до HashTable, ми отримуємо ключ і обчислюємо хеш цього ключа. Після цього ми отримуємо вузол за індексом у HashTable. Знову перевіряємо, чи цей вузол не є NULL, і в кінці повертаємо значення ключа цього вузла.
ФУНКЦІЯ SEARCH
Функція search перевіряє, чи існує ключ у нашій HashTable.
int search(HashTable *table, char *key) {
unsigned int index = hash_function(key);
HashNode *node = table->buckets[index];
if (node != NULL) {
if(strcmp(node->key, key) != 0) {
return 1;
}
return 0;
} else {
return 1;
}
}
Ми обчислюємо індекс ключа (це буде основою для більшості методів), після чого отримуємо вузол за цим індексом. Якщо вузол не є NULL, ми перевіряємо, чи збігається ключ цього вузла з ключем, який ми шукаємо.
ФУНКЦІЯ INSERT
Функція insert вставляє вузли у HashTable.
void insert(HashTable *table, char *key, char *value) {
unsigned int index = hash_function(key);
HashNode *existing_node = table->buckets[index];
if (existing_node != NULL) {
char *node_key = existing_node->key;
if(strcmp(node_key, key) == 0) {
return;
}
} else {
HashNode *node = malloc(sizeof(HashNode));
node->key = key;
node->value = value;
node->next_node = table->buckets[index];
table->buckets[index] = node;
}
}
Ми отримуємо вузол за індексом ключа, в який хочемо вставити пару ключ-значення. Перевіряємо, чи не є вузол NULL, що означає наявність пари ключ-значення. Якщо ключ у вузлі збігається з ключем, який ми намагаємося вставити, ми повертаємося, нічого не роблячи.
Якщо вузол є NULL, ми оновлюємо ключ і значення вузла відповідно до тих, які ми хочемо вставити.
Примітка: Я не реалізував обробку колізій у поточній реалізації.
Ви можете спробувати обробити це у своїй реалізації як цікаву функцію.
ДРУК HASHTABLE
Функція print виведе всі пари ключ-значення для вузлів, що знаходяться у відповідних індексах HashTable.
void print_hashtable(HashTable *table) {
for (int i = 0; i < HASHTABLE_SIZE; i ++) {
HashNode *node = table->buckets[i];
if (node == NULL) {
printf("index: %d \n", i);
} else {
while (node != NULL) {
printf("index: %d -> {%s:%s}\n", i, node->key, node->value);
node = node->next_node;
}
}
}
}
Ми перебираємо HashTable і виводимо пару ключ-значення вузла, якщо вузол не є NULL.
Примітка: Я знаю, що, можливо, реалізував перевірку на виведення колізій тут, а не в деяких інших функціях, але пробачте, це мій перший раз реалізації HashTable на C 🙂
DELETE HASHTABLE
Функція delete_table видаляє всі вузли в нашій HashTable і звільняє пам'ять, а також видаляє саму HashTable і звільняє пам'ять, яку вона використовує.
void delete_table(HashTable *table) {
for (int index = 0; index < HASHTABLE_SIZE; index ++) {
HashNode *node = table->buckets[index];
while (node != NULL) {
HashNode *temp = node;
node = node->next_node;
free(temp);
}
}
free(table->buckets);
free(table);
printf("Deleted hashtable\n");
}
Для кожного вузла в HashTable, якщо вузол не є NULL, ми звільняємо пам'ять, яку використовує цей вузол, і переходимо до наступного вузла в ланцюгу, якщо він є, а в кінці звільняємо пам'ять, використану самою HashTable.
ВИСНОВОК
Мені було цікаво будувати свою власну HashTable з нуля. Це було весело, і я багато чого навчився. Чи була вона найкраща? Точно ні. Чи була середньою? Мабуть, але тепер я маю чітке розуміння того, як працюють HashTable (не ставте мені питання на цю тему).
Сподіваюся, вам сподобалося читати це так само, як мені було цікаво це писати.
Перекладено з: Building a HashTable from Scratch In C