Research indexJournal article
АЛГОРИТМИ ХЕШУВАННЯ ДЛЯ РОЗПОДІЛЕНИХ ХЕШУЮЧИХ СЕРЕДОВИЩ
Дорошенко, Хмелюк, Букасов
Наука і техніка сьогодні30 Apr 2026Open access
NobleIDark:/48914/w1/20261105/94FBA720DOI10.52058/2786-6025-2026-3(57)-2355-2374
АЛГОРИТМИ ХЕШУВАННЯ ДЛЯ РОЗПОДІЛЕНИХ ХЕШУЮЧИХ СЕРЕДОВИЩ
Дорошенко, Хмелюк, Букасов · Наука і техніка сьогодні · 2026
NobleIDark:/48914/w1/20261105/94FBA720DOI10.52058/2786-6025-2026-3(57)-2355-2374
Abstract
АЛГОРИТМИ ХЕШУВАННЯ ДЛЯ РОЗПОДІЛЕНИХ ХЕШУЮЧИХ СЕРЕДОВИЩ Анотація.У статті досліджуються алгоритми хешування, зокрема метод «Гопскотч» від англійського «Hopscotch Hashing».Розглядаються його переваги та недоліки в порівнянні з класичними методами, та методами, що використовують дві таблиці, (вибрано метод зозулиного хешування «Cuckoo Hashing»).Проводиться аналіз часу виконання основних операцій: «додавання», «видалення», «пошук» та пропонуються методи оптимізації, спрямовані на зменшення часу доступу до елементів.Приведено огляд серії експериментів, що підтверджують успішне/не успішне застосування досліджуваного методу у досліджуваному програмному хешуючому середовищі.Дослідження класичних методів хешування показало різке падіння ефективності при високому рівні заповнення таблиці хешування, що обумовлює потребу у спеціалізованих алгоритмах.Розглянутий алгоритм зозулиного хешування гарантує детермінований пошук за O(1), проте має ризик частих перебудов таблиці при α>0.5.Спеціалізований алгоритм Гопскотч хешування завдяки використанню «сусідства» та бітових масок забезпечує стабільно низький час доступу до елементів навіть при високій ймовірності колізій, а також оптимізує розподіл даних для кешу процесора..