Хеш-функции
Отображайте ключи на корзины
«Хеш-функции» — бесплатный урок C Academy на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения C Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс C Academy содержит 4 уроков всего.
Что такое хеш-функция
Хеш-функция принимает ключ и возвращает целочисленный индекс в массиве корзин. Это основа хеш-таблицы: она преобразует произвольные ключи, например строки, в позиции массива для быстрого доступа.
- Вход: ключ (строка, целое число и т. д.)
- Выход: индекс корзины в диапазоне
[0, capacity)
Свойства хорошей хеш-функции
Хорошая хеш-функция должна быть детерминированной, быстрой и равномерно распределять ключи по корзинам.
- Один и тот же ключ всегда даёт один и тот же индекс
- Небольшие изменения ключа приводят к большим изменениям индекса (лавинный эффект)
- Для типичных данных возникает мало коллизий
Отображение в корзину
Вычислив исходное хеш-значение, отобразите его в таблицу с помощью оператора остатка от деления: index = hash % capacity.
Используйте тип unsigned, чтобы остаток никогда не давал отрицательный индекс.
#include <stdio.h>
int main(void) {
unsigned long hash = 123456789UL;
unsigned capacity = 16;
unsigned index = (unsigned)(hash % capacity);
printf("bucket = %u\n", index);
return 0;
}Простая суммирующая хеш-функция
Самая простая хеш-функция для строк складывает значения символов. Она проста, но плохо распределяет ключи, поскольку анаграммы сталкиваются.
Запустите её, чтобы увидеть, как две разные строки дают близкие хеш-значения.
#include <stdio.h>
unsigned long sum_hash(const char *s) {
unsigned long h = 0;
while (*s) h += (unsigned char)*s++;
return h;
}
int main(void) {
printf("%lu\n", sum_hash("abc"));
printf("%lu\n", sum_hash("cba"));
return 0;
}Хеш-функция DJB2
DJB2 — классическая хеш-функция для строк с хорошим распределением, разработанная Даниэлем Дж. Бернстайном. Она начинается со значения 5381 и использует hash * 33 + c.
Умножение с последующим сложением перемешивает биты значительно лучше, чем простая сумма.
#include <stdio.h>
unsigned long djb2(const char *s) {
unsigned long h = 5381;
int c;
while ((c = (unsigned char)*s++))
h = ((h << 5) + h) + c; /* h * 33 + c */
return h;
}
int main(void) {
printf("%lu\n", djb2("hello"));
printf("%lu\n", djb2("world"));
return 0;
}Хеш-функция FNV-1a
FNV-1a применяет XOR к каждому байту, а затем умножает результат на простое число. Она проста, быстра и широко используется.
Порядок такой: сначала XOR, затем умножение — это вариант 1a.
#include <stdio.h>
unsigned long fnv1a(const char *s) {
unsigned long h = 1469598103934665603UL;
while (*s) {
h ^= (unsigned char)*s++;
h *= 1099511628211UL;
}
return h;
}
int main(void) {
printf("%lu\n", fnv1a("key1"));
printf("%lu\n", fnv1a("key2"));
return 0;
}Хеширование целых чисел
Ключи-целые числа тоже требуют перемешивания, поскольку одного x % capacity недостаточно: при общих закономерностях в ключах значения группируются. Мультипликативное перемешивание (Кнута) распределяет биты.
#include <stdio.h>
unsigned hash_int(unsigned x, unsigned cap) {
x *= 2654435761u; /* Knuth multiplicative */
return x % cap;
}
int main(void) {
for (unsigned i = 0; i < 5; i++)
printf("%u -> %u\n", i, hash_int(i, 8));
return 0;
}Размеры, являющиеся степенями двойки
Если размер таблицы является степенью двойки, можно заменить % capacity быстрым побитовым AND: hash & (capacity - 1).
Это работает потому, что младшие биты числа, меньшего степени двойки на единицу, образуют полную маску.
#include <stdio.h>
int main(void) {
unsigned long hash = 123456789UL;
unsigned capacity = 16; /* power of two */
unsigned index = (unsigned)(hash & (capacity - 1));
printf("bucket = %u\n", index);
return 0;
}Почему остаток от деления может быть медленным
Оператор % компилируется в инструкцию деления, которая медленнее операции AND. В тесных циклах это имеет значение.
- Таблица размера степени двойки: используйте маску AND
- Таблица простого размера: используйте остаток от деления (для слабых хеш-функций распределение лучше)
Коллизии неизбежны
Согласно принципу Дирихле, отображение множества ключей в меньшее число корзин неизбежно приводит к коллизиям. Хорошая хеш-функция сводит их к минимуму, но не может устранить полностью.
В следующем уроке рассматриваются способы разрешения коллизий.
Демонстрация распределения
Посчитаем, как DJB2 распределяет несколько ключей по 8 корзинам. Хорошие хеш-функции распределяют ключи достаточно равномерно.
#include <stdio.h>
unsigned long djb2(const char *s) {
unsigned long h = 5381;
int c;
while ((c = (unsigned char)*s++)) h = ((h << 5) + h) + c;
return h;
}
int main(void) {
const char *keys[] = {"apple", "banana", "cherry", "date"};
int counts[8] = {0};
for (int i = 0; i < 4; i++)
counts[djb2(keys[i]) % 8]++;
for (int i = 0; i < 8; i++)
printf("bucket %d: %d\n", i, counts[i]);
return 0;
}Быстрая проверка
Проверьте своё понимание основ хеш-функций.
Итоги
Вы узнали, что делает хеш-функция и как отображать ключи в корзины.
- Хорошие хеш-функции детерминированы, быстры и равномерны
- DJB2 и FNV-1a — надёжные хеш-функции для строк
- Используйте
% capacityили& (capacity-1)для степеней двойки - Используйте беззнаковые типы; коллизии неизбежны
Часто задаваемые вопросы
Урок «Хеш-функции» бесплатный?
Да — полный текст урока «Хеш-функции» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C Academy, подпишись на CoddyKit PRO. Курс C Academy содержит 4 уроков всего.
Чему я научусь в уроке «Хеш-функции»?
Отображайте ключи на корзины Ты практикуешь C Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать C Academy?
Предыдущий опыт не требуется. C Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Хеш-функции»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке C Academy?
Да. Каждый урок C Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.