320 lines
14 KiB
C
320 lines
14 KiB
C
// ============================================================
|
||
// Реализация хеш-таблицы с открытой адресацией
|
||
// ============================================================
|
||
|
||
#включить "руси.з"
|
||
#включить <stdint.h> // стандартная библиотека
|
||
#включить <string.h> // стандартная библиотека
|
||
#включить <stdlib.h> // стандартная библиотека
|
||
#включить <assert.h> // стандартная библиотека
|
||
#включить <stdio.h> // стандартная библиотека
|
||
|
||
// ============================================================
|
||
// Константы
|
||
// ============================================================
|
||
|
||
#определить НАЧАЛЬНЫЙ_РАЗМЕР 16 // Начальный размер таблицы
|
||
#определить ВЕРХНИЙ_ПОРОГ 70 // Перестройка при заполнении > 70%
|
||
#определить НИЖНИЙ_ПОРОГ 50 // Целевое заполнение после перестройки < 50%
|
||
#определить УДАЛЕНО ((пусто *)-1) // Маркер удаленного элемента
|
||
|
||
// ============================================================
|
||
// Хеш-функция FNV-1a
|
||
// ============================================================
|
||
|
||
стат uint64_t хеш_fnv(конст символ *данные, цел длина) {
|
||
uint64_t хеш = 0xcbf29ce484222325ULL; // FNV offset basis
|
||
|
||
для (цел ш = 0; ш < длина; ш++) {
|
||
хеш *= 0x100000001b3ULL; // FNV prime
|
||
хеш ^= (беззнак символ)данные[ш];
|
||
}
|
||
|
||
возврат хеш;
|
||
}
|
||
|
||
// ============================================================
|
||
// Проверка совпадения ключей
|
||
// ============================================================
|
||
|
||
стат бул ключи_совпадают(ЗаписьХеша *запись, конст символ *ключ, цел длина_ключа) {
|
||
если (!запись->ключ || запись->ключ == УДАЛЕНО) {
|
||
возврат ложь;
|
||
}
|
||
|
||
возврат (запись->длина_ключа == длина_ключа) &&
|
||
(memcmp(запись->ключ, ключ, длина_ключа) == 0);
|
||
}
|
||
|
||
// ============================================================
|
||
// Перестройка хеш-таблицы
|
||
// ============================================================
|
||
|
||
стат пусто перестроить(ХешТаблица *таблица) {
|
||
если (!таблица) возврат;
|
||
|
||
// Подсчитываем количество активных записей
|
||
цел активных = 0;
|
||
для (цел ш = 0; ш < таблица->вместимость; ш++) {
|
||
пусто *ключ = таблица->корзины[ш].ключ;
|
||
если (ключ && ключ != УДАЛЕНО) {
|
||
активных++;
|
||
}
|
||
}
|
||
|
||
// Вычисляем новый размер
|
||
цел новая_вместимость = таблица->вместимость;
|
||
пока ((активных * 100) / новая_вместимость >= НИЖНИЙ_ПОРОГ) {
|
||
новая_вместимость *= 2;
|
||
}
|
||
assert(новая_вместимость > 0);
|
||
|
||
// Создаем новую таблицу
|
||
ХешТаблица новая = {0};
|
||
новая.корзины = (ЗаписьХеша *)calloc(новая_вместимость, размер(ЗаписьХеша));
|
||
новая.вместимость = новая_вместимость;
|
||
|
||
// Копируем все активные записи
|
||
для (цел ш = 0; ш < таблица->вместимость; ш++) {
|
||
ЗаписьХеша *запись = &таблица->корзины[ш];
|
||
если (запись->ключ && запись->ключ != УДАЛЕНО) {
|
||
хеш_вставить2(&новая, запись->ключ, запись->длина_ключа, запись->значение);
|
||
}
|
||
}
|
||
|
||
assert(новая.использовано == активных);
|
||
|
||
// Освобождаем старую таблицу
|
||
если (таблица->корзины) {
|
||
free(таблица->корзины);
|
||
}
|
||
|
||
// Копируем новую таблицу
|
||
*таблица = новая;
|
||
}
|
||
|
||
// ============================================================
|
||
// Поиск записи по ключу
|
||
// ============================================================
|
||
|
||
стат ЗаписьХеша *найти_запись(ХешТаблица *таблица, конст символ *ключ, цел длина_ключа) {
|
||
если (!таблица || !таблица->корзины) {
|
||
возврат NULL;
|
||
}
|
||
|
||
uint64_t хеш = хеш_fnv(ключ, длина_ключа);
|
||
|
||
для (цел ш = 0; ш < таблица->вместимость; ш++) {
|
||
цел индекс = (хеш + ш) % таблица->вместимость;
|
||
ЗаписьХеша *запись = &таблица->корзины[индекс];
|
||
|
||
если (ключи_совпадают(запись, ключ, длина_ключа)) {
|
||
возврат запись;
|
||
}
|
||
|
||
если (запись->ключ == NULL) {
|
||
возврат NULL;
|
||
}
|
||
}
|
||
|
||
unreachable();
|
||
возврат NULL;
|
||
}
|
||
|
||
// ============================================================
|
||
// Поиск или создание записи
|
||
// ============================================================
|
||
|
||
стат ЗаписьХеша *найти_или_создать(ХешТаблица *таблица, конст символ *ключ, цел длина_ключа) {
|
||
// Инициализация при первом использовании
|
||
если (!таблица->корзины) {
|
||
таблица->корзины = (ЗаписьХеша *)calloc(НАЧАЛЬНЫЙ_РАЗМЕР, размер(ЗаписьХеша));
|
||
таблица->вместимость = НАЧАЛЬНЫЙ_РАЗМЕР;
|
||
если (!таблица->корзины) {
|
||
возврат NULL;
|
||
}
|
||
}
|
||
|
||
// Перестройка при переполнении
|
||
если ((таблица->использовано * 100) / таблица->вместимость >= ВЕРХНИЙ_ПОРОГ) {
|
||
перестроить(таблица);
|
||
}
|
||
|
||
uint64_t хеш = хеш_fnv(ключ, длина_ключа);
|
||
|
||
для (цел ш = 0; ш < таблица->вместимость; ш++) {
|
||
цел индекс = (хеш + ш) % таблица->вместимость;
|
||
ЗаписьХеша *запись = &таблица->корзины[индекс];
|
||
|
||
// Нашли существующую запись
|
||
если (ключи_совпадают(запись, ключ, длина_ключа)) {
|
||
возврат запись;
|
||
}
|
||
|
||
// Нашли tombstone - используем его
|
||
если (запись->ключ == УДАЛЕНО) {
|
||
запись->ключ = (символ *)ключ;
|
||
запись->длина_ключа = длина_ключа;
|
||
возврат запись;
|
||
}
|
||
|
||
// Нашли пустую запись
|
||
если (запись->ключ == NULL) {
|
||
запись->ключ = (символ *)ключ;
|
||
запись->длина_ключа = длина_ключа;
|
||
таблица->использовано++;
|
||
возврат запись;
|
||
}
|
||
}
|
||
|
||
unreachable();
|
||
возврат NULL;
|
||
}
|
||
|
||
// ============================================================
|
||
// Публичные функции
|
||
// ============================================================
|
||
|
||
пусто *хеш_получить(ХешТаблица *таблица, символ *ключ) {
|
||
если (!таблица || !ключ) возврат NULL;
|
||
возврат хеш_получить2(таблица, ключ, (цел)strlen(ключ));
|
||
}
|
||
|
||
пусто *хеш_получить2(ХешТаблица *таблица, символ *ключ, цел длина_ключа) {
|
||
если (!таблица || !ключ || длина_ключа <= 0) возврат NULL;
|
||
|
||
ЗаписьХеша *запись = найти_запись(таблица, ключ, длина_ключа);
|
||
возврат запись ? запись->значение : NULL;
|
||
}
|
||
|
||
пусто хеш_вставить(ХешТаблица *таблица, символ *ключ, пусто *значение) {
|
||
если (!таблица || !ключ) возврат;
|
||
хеш_вставить2(таблица, ключ, (цел)strlen(ключ), значение);
|
||
}
|
||
|
||
пусто хеш_вставить2(ХешТаблица *таблица, символ *ключ, цел длина_ключа, пусто *значение) {
|
||
если (!таблица || !ключ || длина_ключа <= 0) возврат;
|
||
|
||
ЗаписьХеша *запись = найти_или_создать(таблица, ключ, длина_ключа);
|
||
если (запись) {
|
||
запись->значение = значение;
|
||
}
|
||
}
|
||
|
||
пусто хеш_удалить(ХешТаблица *таблица, символ *ключ) {
|
||
если (!таблица || !ключ) возврат;
|
||
хеш_удалить2(таблица, ключ, (цел)strlen(ключ));
|
||
}
|
||
|
||
пусто хеш_удалить2(ХешТаблица *таблица, символ *ключ, цел длина_ключа) {
|
||
если (!таблица || !ключ || длина_ключа <= 0) возврат;
|
||
|
||
ЗаписьХеша *запись = найти_запись(таблица, ключ, длина_ключа);
|
||
если (запись) {
|
||
запись->ключ = УДАЛЕНО;
|
||
}
|
||
}
|
||
|
||
// ============================================================
|
||
// Тестирование хеш-таблицы
|
||
// ============================================================
|
||
|
||
пусто хеш_тест(пусто) {
|
||
ХешТаблица *таблица = (ХешТаблица *)calloc(1, размер(ХешТаблица));
|
||
если (!таблица) {
|
||
fprintf(stderr, "Failed to allocate hashmap for testing\n");
|
||
возврат;
|
||
}
|
||
|
||
printf("Testing hashmap...\n");
|
||
|
||
// Вставка 5000 записей
|
||
для (цел ш = 0; ш < 5000; ш++) {
|
||
символ *ключ = формат("key %d", ш);
|
||
хеш_вставить(таблица, ключ, (пусто *)(intptr_t)ш);
|
||
}
|
||
|
||
// Удаление записей 1000-1999
|
||
для (цел ш = 1000; ш < 2000; ш++) {
|
||
символ *ключ = формат("key %d", ш);
|
||
хеш_удалить(таблица, ключ);
|
||
}
|
||
|
||
// Повторная вставка 1500-1599
|
||
для (цел ш = 1500; ш < 1600; ш++) {
|
||
символ *ключ = формат("key %d", ш);
|
||
хеш_вставить(таблица, ключ, (пусто *)(intptr_t)ш);
|
||
}
|
||
|
||
// Вставка 6000-6999
|
||
для (цел ш = 6000; ш < 7000; ш++) {
|
||
символ *ключ = формат("key %d", ш);
|
||
хеш_вставить(таблица, ключ, (пусто *)(intptr_t)ш);
|
||
}
|
||
|
||
// Проверка записей 0-999
|
||
для (цел ш = 0; ш < 1000; ш++) {
|
||
символ *ключ = формат("key %d", ш);
|
||
пусто *значение = хеш_получить(таблица, ключ);
|
||
assert((intptr_t)значение == ш);
|
||
}
|
||
|
||
// Проверка удаленных записей 1000-1499
|
||
для (цел ш = 1000; ш < 1500; ш++) {
|
||
символ *ключ = формат("key %d", ш);
|
||
пусто *значение = хеш_получить(таблица, ключ);
|
||
assert(значение == NULL);
|
||
}
|
||
|
||
// Проверка восстановленных записей 1500-1599
|
||
для (цел ш = 1500; ш < 1600; ш++) {
|
||
символ *ключ = формат("key %d", ш);
|
||
пусто *значение = хеш_получить(таблица, ключ);
|
||
assert((intptr_t)значение == ш);
|
||
}
|
||
|
||
// Проверка удаленных записей 1600-1999
|
||
для (цел ш = 1600; ш < 2000; ш++) {
|
||
символ *ключ = формат("key %d", ш);
|
||
пусто *значение = хеш_получить(таблица, ключ);
|
||
assert(значение == NULL);
|
||
}
|
||
|
||
// Проверка записей 2000-4999
|
||
для (цел ш = 2000; ш < 5000; ш++) {
|
||
символ *ключ = формат("key %d", ш);
|
||
пусто *значение = хеш_получить(таблица, ключ);
|
||
assert((intptr_t)значение == ш);
|
||
}
|
||
|
||
// Проверка несуществующих записей 5000-5999
|
||
для (цел ш = 5000; ш < 6000; ш++) {
|
||
символ *ключ = формат("key %d", ш);
|
||
пусто *значение = хеш_получить(таблица, ключ);
|
||
assert(значение == NULL);
|
||
}
|
||
|
||
// Обновление записей 6000-6999
|
||
для (цел ш = 6000; ш < 7000; ш++) {
|
||
символ *ключ = формат("key %d", ш);
|
||
хеш_вставить(таблица, ключ, (пусто *)(intptr_t)(ш * 2));
|
||
}
|
||
|
||
// Проверка обновленных записей
|
||
для (цел ш = 6000; ш < 7000; ш++) {
|
||
символ *ключ = формат("key %d", ш);
|
||
пусто *значение = хеш_получить(таблица, ключ);
|
||
assert((intptr_t)значение == ш * 2);
|
||
}
|
||
|
||
// Проверка несуществующего ключа
|
||
assert(хеш_получить(таблица, "no such key") == NULL);
|
||
|
||
// Освобождаем память
|
||
если (таблица->корзины) {
|
||
free(таблица->корзины);
|
||
}
|
||
free(таблица);
|
||
|
||
printf("All hashmap tests passed!\n");
|
||
} |