Реализация хеш-таблицы на языке C с открытой адресацией, линейным пробированием и динамическим расширением.
Проект реализует классическую хеш-таблицу типа string → int с интерактивным командным интерфейсом. Ключи — произвольные строки, значения — целые числа. Таблица автоматически расширяется при достижении порога заполненности.
Хеш-функция: DJB2 — быстрый и качественный алгоритм хеширования строк, разработанный Дэниелом Дж. Бернштейном.
| Характеристика | Значение |
|---|---|
| Хеш-функция | DJB2 |
| Метод разрешения коллизий | Линейное пробирование (открытая адресация) |
| Метод удаления | «Ленивое» удаление (tombstone) |
| Начальная ёмкость | 32 слота |
| Коэффициент загрузки | 0.6 (60%) |
| Масштабирование | ×2 при превышении load factor |
# Компиляция
gcc hash_djb2.c -o hash_table
# Запуск
# Powershell
./hash_table
# Cmd
hash_tableТребования: компилятор GCC или Clang, стандарт C99.
После запуска программа переходит в интерактивный режим с приглашением ?>.
put <ключ>, <значение> — добавить или обновить запись
get <ключ> — получить значение по ключу
del <ключ> — удалить запись и вернуть значение
exit — завершить программу
?> put apple, 42
?> put banana, 100
?> get apple
42
?> put apple, 99
?> get apple
99
?> del banana
100
?> get banana
Not found!
?> exit
hash = 5381
для каждого символа c:
hash = hash * 33 + cЭквивалентная битовая форма: hash = ((hash << 5) + hash) + c
Магические числа 5381 и 33 подобраны эмпирически — они обеспечивают хорошее лавинообразное распространение битов и минимальное число коллизий для типичных строковых данных.
hash_djb2.c
│
├── Item — структура одной записи (ключ, значение, флаг удаления)
│
├── djb2() — хеш-функция
├── put() — вставка / обновление
├── get() — поиск
├── delete() — логическое удаление (tombstone)
├── rehash_table() — перестройка таблицы при расширении
├── free_table() — освобождение памяти
│
└── main() — интерактивный командный цикл
Вставка (put)
│
▼
Вычислить индекс → djb2(key) & (capacity - 1)
│
▼
Ячейка свободна? ──Да──► Записать, table_size++
│
Нет
│
▼
Ключи совпадают? ──Да──► Обновить value (return)
│
Нет
│
▼
Линейный сдвиг: idx = (idx + 1) & (capacity - 1)
│
▼
table_size > load_factor * capacity? ──Да──► rehash_table()
- Ключи хранятся как динамически выделенные C-строки (
malloc). - При rehash старая таблица полностью освобождается (
free_table). - Программа корректно освобождает всю память при выходе.
| Счётчик | Описание |
|---|---|
collision_count |
Суммарное число коллизий за все операции put |
rehash_count |
Количество перестроений таблицы |