Skip to content

README.md

Latest commit

 

History

History
150 lines (113 loc) · 4.88 KB

README.md

File metadata and controls

150 lines (113 loc) · 4.88 KB
Raw

🗂️ Хеш-таблица на основе алгоритма DJB2

Реализация хеш-таблицы на языке 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

🔬 Алгоритм DJB2

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 Количество перестроений таблицы