Тріо дослідників зробили відкриття, яке може призвести до ефективнішого зберігання та пошуку даних у комп’ютерах.
Висновки групи відносяться до так званих «хеш-таблиць з лінійним зондуванням», які були введені в 1954 році і є одними з найстаріших, найпростіших і найшвидших структур даних, доступних сьогодні. Вони надають способи організації та зберігання даних на комп’ютерах, причому хеш-таблиці є одним з найчастіше використовуваних підходів. У хеш-таблиці з лінійним зондуванням позиції, у яких може зберігатися інформація, лежать уздовж лінійного масиву.
Припустимо, що база даних призначена для зберігання номерів соціального страхування 10 тис осіб, пропонує Вільям Кусмаул, аспірант комп’ютерних наук у Массачусетському технологічному інституті. «Ми беремо ваш номер соціального страхування x, а потім обчислюємо хеш-функцію x, h(x), яка дає випадкове число від 1 до 10 000». Наступний крок – взяти це випадкове число h (x), перейти до цієї позиції в масиві і помістити в це місце x номер соціального страхування.
Якщо на цьому місці вже щось є, каже Кусмаул, ви просто переходите до наступної вільної позиції і кладете це туди. Звідси і термін «лінійне зондування», оскільки ви продовжуєте рухатися вперед лінійно, доки не знайдете відкрите місце». Щоб пізніше отримати цей номер соціального страхування, x, ви просто йдете у вказане місце, h(x), і, якщо його там немає, ви рухаєтеся вперед, поки не знайдете x, або не прийдете у вільну позицію і не зробите висновок, що x немає у вашій базі.
Існує дещо інший протокол видалення елемента, наприклад, номери соціального страхування. Якщо ви просто залишили порожнє місце в хеш-таблиці після видалення інформації, це може викликати плутанину, коли пізніше спробуєте знайти ще щось, оскільки порожнє місце може помилково припустити, що потрібний елемент ніде не знайдений у базі даних. Щоб уникнути цієї проблеми, пояснює Кусмаул, «ви можете піти до місця, де елемент був вилучений, і поставити там невеликий маркер, званий надгробком, який вказує, що раніше тут був елемент, але тепер його немає».
Ця загальна процедура застосовувалася понад півстоліття. Але весь цей час майже всі, хто використовував хеш-таблиці з лінійним зондуванням, припускали, що якщо дозволити їм переповнитися, довгі ділянки зайнятих місць зіллються разом, утворюючи «кластери». В результаті час, необхідний для пошуку вільного місця, різко зросте і займатиме стільки часу, що це буде недоцільним. Отже, люди були навчені роботі з хеш-таблицями з низькою пропускною спроможністю — практика, яка може призвести до економічних втрат, оскільки впливає на кількість обладнання, яке компанія має купувати та обслуговувати.
Але цей перевірений часом принцип, який тривалий час перешкоджав високим коефіцієнтам навантаження, був повністю перевернутий роботою Кусмаула та його колег з Університету Стоуні-Брук. Вони виявили, що для застосунків, в яких кількість вставок і видалень залишається приблизно однаковою, а кількість даних, що додаються приблизно дорівнює кількості видалених, хеш-таблиці з лінійним зондуванням можуть працювати з великими обсягами пам’яті без шкоди для швидкості.
Крім того, команда розробила нову стратегію під назвою «хешування цвинтаря», яка включає штучне збільшення кількості надгробків, що розміщуються в масиві, доки вони не займуть приблизно половину вільних місць. Потім ці надгробки резервують місця, які можна використовувати для майбутніх вставок.
Цей підхід, який суперечить тому, що люди зазвичай інструктують робити, за словами Кусмаула, «може призвести до оптимальної продуктивності в хеш-таблицях з лінійним зондуванням». Або, як він та його співавтори стверджують у своїй статті, «добре продумане використання надгробків може повністю змінити… ландшафт того, як поводиться лінійне зондування».
Що стосується застосування отриманих результатів на практиці, Кушмаул зазначає, що «існує безліч міркувань, пов’язаних із побудовою хеш-таблиці. Хоча ми значно просунулися в теоретичному плані, ми лише починаємо вивчати експериментальний бік питання».
Читайте також:
- realme спрямовує 90% своїх досліджень та розробок на технологію 5G
- Виявлено незрозуміле з точки зору фізики явище