Лінійне зондування

Лінійне зондування (англ. Linear probing) — це схема в комп’ютерному програмуванні для вирішення колізій у хеш-таблицях, структурах даних для підтримки колекції пар ключ-значення та пошуку значення, пов’язаного з даним ключем. Він був винайдений у 1954 році Джином Амдалом, Елейн М. Макгроу та Артуром Самуелем і вперше проаналізований у 1963 році Дональдом Кнутом .

Колізія між Джоном Смітом і Сандрою Ді (обидва хешуються до комірки 873) вирішується шляхом розміщення Сандри Ді в наступному вільному місці, комірці 874.

Разом із квадратичним зондуванням і подвійним хешуванням, лінійне зондування є формою відкритої адресації . У цих схемах кожна комірка хеш-таблиці зберігає одну пару ключ-значення. Коли хеш-функція викликає колізію, відображаючи новий ключ із коміркою хеш-таблиці, яка вже зайнята іншим ключем, лінійне зондування шукає в таблиці найближчу вільну комірку та вставляє туди новий ключ. Пошук значення виконується таким же чином, шляхом послідовного пошуку в таблиці, починаючи з позиції, заданої хеш-функцією, доки не буде знайдена комірка з відповідним ключем або порожня комірка.

Як пишуть Thorup та Zhang, (2012), «хеш-таблиці — це найбільш часто використовувані нетривіальні структури даних, а найпопулярніша реалізація на стандартному обладнанні використовує лінійне зондування, яке одночасно є швидким і простим». Лінійне зондування може забезпечити високу продуктивність завдяки хорошій локальності значень, але більш чутливе до якості своєї хеш-функції, ніж деякі інші схеми вирішення колізій. Середній очікуваний час операції пошук є константним, так само і для операцій вставки або видалення, якщо вони реалізовані за допомогою випадкової хеш-функції, 5-незалежної хеш-функції або хешування таблиці . Гарних результатів також можна досягти на практиці за допомогою інших хеш-функцій, таких як MurmurHash .

Операції

Лінійне зондування є компонентом схем з відкритою адресацією для використання в хеш-таблиці для вирішення проблем пошуку у словнику. У задачі пошуку в словнику структура даних повинна працювати з набором пар ключ-значення, і повинна підтримувати можливість вставки та видалення цих пар, а також пошук значення яке асоційоване з даним ключем. Для рішення цієї задачі за допомогою відкритої адресаціїї структурою даних є масив T (хеш-таблиця), де кожна з комірок T[i] (якщо вона непорожня) зберігає одну пару ключ–значення. Хеш-функція використовується для відображення кожного ключа в комірку T, де цей ключ має зберігатися, зазвичай перемішуючи ключі, щоб ключі з подібними значеннями не розміщувалися поруч один з одним у таблиці. Хеш-колізія виникає, коли хеш-функція відображає ключ у комірці, яка вже зайнята іншим ключем. Лінійне зондування — це стратегія вирішення колізій шляхом розміщення нового ключа в найближчій порожній клітинці.

Пошук

Для пошуку заданого ключа x перевіряються комірки T, починаючи з комірки з індексом h(x) (де h — хеш-функція) і далі комірки h(x) + 1, h(x) + 2, ..., аж поки не буде знайдено порожню комірку або комірку, ключ якої дорівнює x. Якщо знайдено комірку, що містить ключ, пошук повертає значення з цієї комірки. Інакше, якщо знайдено порожню комірку, ключ не може бути в таблиці, оскільки він був би розміщений у цій комірці, а не в будь-якій наступній комірці, у якій ще не проводився пошук. У цьому випадку пошук повертає, що ключ відсутній у словнику.

Вставка

Щоб вставити пару ключ-значення (x,v) у таблицю (можливо, замінивши будь-яку існуючу пару з таким же ключем), алгоритм вставки проходить ту саму послідовність комірок, що і для пошуку, доки не буде знайдено порожню комірку або комірку з ключем x . Нова пара ключ-значення записується в цю комірку.

Якщо вставка призведе до зростання коефіцієнта завантаження таблиці (частка зайнятих комірок) вище деякого попередньо встановленого порогу, всю таблицю можна замінити новою таблицею, більшою на постійний коефіцієнт (подібно до роботи динамічного масиву) з новою хеш-функцією. Встановлення цього порогу, близьким до нуля, і використання високої швидкості зростання для розміру таблиці призводить до швидших операцій хеш-таблиці, але більшого використання пам’яті. Зазвичай розмір таблиці збільшують вдвічі, коли коефіцієнт завантаження перевищує 1/2, в результаті чого фактичне завантаження перебуває між 1/4 і 1/2.

Видалення

Коли пару ключ–значення видалено, може знадобитися перемістити іншу пару назад у її комірку.

Також можна видалити пару ключ-значення A зі словника. Однак просто очистити його комірку i недостатньо. Можливо існує інша пара ключ-значення B з таким же хеш значенням, яка була розміщена після зайнятої комірки. В такому випадку пошук B зупиниться на пустій комірці i (де раніше був A), і B не буде найдена.

Тому, після очистки комірки i, необхідно провести пошук у наступних комірках таблиці, доки не буде знайдена інша порожня комірка або ключ, який можна перемістити до комірки i (тобто ключ, хеш-значення якого дорівнює або менший ніж i ). Якщо знайдено порожню комірку, очищення комірки i є безпечним і процес видалення припиняється. Але, коли пошук знаходить ключ, який можна перемістити до клітинки i, необхідно виконати це переміщення. Процес має бути повторений таким же чином, доки він не завершиться досягненням комірки, яка вже була порожньою. У процесі переміщення ключів до попередніх клітинок кожен ключ перевіряється лише один раз. Таким чином, час завершення всього процесу пропорційний довжині блоку зайнятих комірок, що містить видалений ключ, що відповідає часу виконання інших операцій хеш-таблиці.

Альтернативно, можна використати стратегію лінивого видалення, коли пара ключ-значення видаляється шляхом заміни значення спеціальним булевим прапорцем, що вказує на те що ключ видалений. Однак ці прапорці призводять до збільшення коефіцієнту завантаження хеш-таблиці. Але за цієї стратегії, якщо надто велика частка масиву стає зайнятою видаленими прапорцями, виникає необхідність очистити всі комірки з прапорцями та повторно перехешувати всі пари ключ-значення.

Властивості

Лінійне зондування забезпечує хорошу локальність посилань, це що для кожної операції потрібно всього кілька звернень до некезашованої пам’яті. Через це при низьких і помірних коефіцієнтах завантаження можна досягти високої продуктивність. Однак, у порівнянні з деякими іншими стратегіями відкритої адресації, його продуктивність деградує швидше при високих факторах завантаження через первинну кластеризацію, та тому що колізія має тенденцію викликати більше колізій поблизу. Крім того, для досягнення високої продуктивності за допомогою цього методу потрібна хеш-функція вищої якості, ніж для деяких інших схем вирішення колізій. При використанні з низькоякісними хеш-функціями, які не можуть усунути нерівномірності у розподілі вхідних даних, лінійне зондування може бути повільнішим, ніж інші стратегії відкритої адресації, такі як подвійне хешування, яке перебирає послідовність комірок, розділення яких визначається другою хеш-функцією, або квадратичне зондування, де розмір кожного кроку змінюється залежно від його положення в послідовності проб.

Аналіз

Використовуючи лінійне зондування, словникові операції можна реалізувати за константнийочікуваний час. Іншими словами, операції вставки, видалення та пошуку можуть бути реалізовані за час O(1), якщо коефіцієнт завантаження хеш-таблиці є константою, строго меншою за одиницю.

Більш детально, час для будь-якої конкретної операції (пошук, вставка або видалення) пропорційний довжині безперервного блоку зайнятих комірок, з якого починається операція. Якщо в хеш-таблиці з N комірок усі початкові комірки є однаково вірогідними, то максимальний блок із k зайнятих комірок міститиме початкове пошуку з ймовірністю k/N та потребуватиме часу O(k) незалежно від початкового місця пошуку. Таким чином, очікуваний час виконання операції можна обчислити як добуток цих двох членів, O(k²/N), сумованих по всіх максимальних блоках неперервних комірок у таблиці. Подібна сума квадратів довжин блоків дає границю очікування часу для випадкової хеш-функції (а не для випадкового початкового розташування в певному стані хеш-таблиці), шляхом підсумовування всіх блоків, які можуть існувати (а не тих, що фактично існує в даному стані таблиці), і множення члена для кожного потенційного блоку на ймовірність того, що блок фактично зайнятий. Тобто, якщо визначити Block(i,k) як подію, що максимальний безперервний блок зайнятих комірок довжиною k починаючи з індексу i, то очікуваний час на операцію буде

Цю формулу можна спростити, замінивши Block(i,k) на простішу необхідну умову Full(k), якщо принаймні k елементів мають хеш-значення, що знаходяться в блоці комірок довжиною k . Після цієї заміни значення в сумі більше не залежить від i, а фактор 1/N скасовує N членів зовнішньої суми. Ці спрощення зводять до межі

Але згідно з мультиплікативною формою обмеження Чернова, коли коефіцієнт завантаження менший одиницею, ймовірність того, що блок довжиною k містить принаймні k хешованих значень, є експоненційно малою як функція k, через що ця сума буде обмежена константою, незалежною від n. Також можна виконати такий же аналіз, використовуючи наближення Стірлінга замість обмеження Чернова, щоб оцінити ймовірність того, що блок містить рівно k хешованих значень.

З точки зору коефіцієнта завантаження α, очікуваний час успішного пошуку дорівнює O(1 + 1/(1 − α)), а очікуваний час невдалого пошуку (або введення нового ключа) дорівнює O(1 + 1/(1 − α)²) . Для постійних коефіцієнтів завантаження з високою ймовірністю, найдовша послідовність зондування (серед послідовностей зондування для всіх ключів, збережених у таблиці) має логарифмічну довжину.

Вибір хеш-функції

Оскільки лінійне зондування особливо чутливе до нерівномірно розподілених хеш-значень, важливо поєднати його з високоякісною хеш-функцією, яка не створює таких нерівномірностей.

Наведений вище аналіз передбачає, що хеш кожного ключа є випадковим числом, незалежним від хешів усіх інших ключів. Це припущення є нереалістичним для більшості застосувань хешування. Однак випадкові чи псевдовипадкові хеш-значення можуть використовуватися під час хешування об’єктів по ідентифікатору, а не за по значенню. Наприклад, це робиться за допомогою лінійного зондування за допомогою класу IdentityHashMap з Java collections framework. Хеш-значення, яке цей клас асоціює з кожним об’єктом, його identityHashCode, гарантовано залишатиметься незмінним протягом усього життя об’єкта, але в іншому випадку є довільним. Оскільки identityHashCode створюється лише один раз для кожного об’єкта, і не обов’язково має бути пов’язаним з адресою чи значенням об’єкта, його побудова може включати повільніші обчислення, такі як виклик генератора випадкових чи псевдовипадкових чисел. Наприклад, Java 8 використовує генератор псевдовипадкових чисел Xorshift для створення цих значень.

Для більшості застосувань хешування необхідно обчислювати хеш-функцію для кожного значення кожного разу, коли потрібен хеш, а не один раз під час створення об’єкта. У таких програмах випадкові чи псевдовипадкові числа не можна використовувати як хеш-значення, оскільки тоді різні об’єкти з однаковим значенням матимуть різні хеші. А криптографічні хеш-функції (які розроблені таким чином, що не відрізняються від справді випадкових функцій) зазвичай надто повільні для використання в хеш-таблицях. Замість цього були розроблені інші методи побудови хеш-функцій. Ці методи швидко обчислюють хеш-функцію та можуть добре працювати з лінійним зондуванням. Зокрема, лінійне зондування було проаналізовано на основі <span about="#mwt143" class="texhtml mvar" data-cx="[{&quot;adapted&quot;:true,&quot;partial&quot;:false,&quot;targetExists&quot;:true,&quot;mandatoryTargetParams&quot;:[],&quot;optionalTargetParams&quot;:[]}]" data-mw="{&quot;parts&quot;:[{&quot;template&quot;:{&quot;target&quot;:{&quot;wt&quot;:&quot;Mvar&quot;,&quot;href&quot;:&quot;./Шаблон:Mvar&quot;},&quot;params&quot;:{&quot;1&quot;:{&quot;wt&quot;:&quot;k&quot;}},&quot;i&quot;:0}}]}" data-ve-no-generated-contents="true" id="mwtw" style="font-style:italic;" typeof="mw:Transclusion">k</span> -незалежного хешування, класу хеш-функцій, які ініціалізуються з невеликого випадкового початкового числа та з однаковою ймовірністю відображають будь-який k -кортеж різних ключів в будь-який k -кортеж індексів. Параметр k можна розглядати як міру якості хеш-функції: чим більше k, тим більше часу знадобиться для обчислення хеш-функції, але вона поводитиметься подібніше до абсолютно випадкових функцій. Для лінійного зондування достатньо 5-незалежності, щоб гарантувати константний очікуваний час на операцію , тоді як деякі 4-незалежні хеш-функції працюють погано, і потребують логарифмічний час на операцію.

Інший метод побудови хеш-функцій з високою якістю та достатньою швидкістю — це табличне хешування . У цьому методі хеш-значення для ключа обчислюється шляхом використання кожного байта ключа як індексу в таблиці випадкових чисел (маючи окрему таблицю на кожну позицію байту). Числа з цих комірок таблиці потім об’єднуються за допомогою побітової операції виключне «АБО» . Хеш-функції, побудовані таким чином, є 3-незалежні. Тим не менш, лінійне зондування з використанням цих хеш-функцій має константний очікуваний час на операцію. Табличне хешування, і стандартні методи генерації 5-незалежних хеш-функцій обмежені ключами, які мають фіксовану кількість бітів. Для обробки рядків або інших типів ключів змінної довжини можна скомбінувати простішу універсальну техніку хешування, яка відображає ключі на проміжні значення, і хеш-функцію вищої якості (5-незалежну або табуляцію), яка відображає проміжні значення на індекси хеш-таблиці.

За допомогою експериментальних порівнянь Richter et al. виявив, що сімейство хеш-функцій Multiply-Shift (визначених як ) є «найшвидшою хеш-функцією, інтегрованою з усіма схемами хешування, тобто забезпечує найвищу пропускну здатність і хорошу якість», тоді як табличне хешування дає «найнижчу пропускну здатність». Вони зазначають, що кожен пошук у таблиці потребує кількох циклів, що коштує дорожче, ніж прості арифметичні операції. Вони також виявили, що MurmurHash є кращим за табличне хешування: «Вивчаючи результати, надані Mult і Murmur, ми вважаємо, що використання табличного хешування (...) є менш привабливим на практиці».

Історія

Ідея асоціативного масиву, який дозволяє отримати доступ до даних за їх значенням, а не за адресою, сягає середини 1940-х років до робіт Конрада Цузе та Ванневара Буша , але хеш-таблиці не були описані, поки їх не описав Ганс Петер Лун в меморандум IBM в 1953 році. Лун використав інший метод вирішення колізій, ланцюжок, а не лінійне зондування.

Дональд Кнут підсумовує ранню історію лінійного зондувания. Це був перший метод відкритої адресації і на початку він був синонімом відкритої адресації. Згідно Кнуту, метод першим використав Джин Амдал, МакГроу, Элані М.^[en] та Артур Семюел в 1954 в асемблерній програмі для комп'ютера IBM 701. Перша опублікований опис лінійного зондування дав Пітерсон, який згадав Семюеля, Амдала и МакГроу, але додав, що «система настільни органічна, що могла бути створена незалежно і іншими в той же час».

Перший теоретичний аналіз лінійного зондування, показав, що операція з випадковими хеш-функціями займає константний очікуваний час, був проведений Кнутом. Седжвік називає роботу Кнута «визначною віхою в аналізі алгоритмів». Значно пізніші розробки включають більш детальний аналіз розподілу ймовірностей часу роботи і доказ того, що лінійне зондування виконується за константний час на операцію з хеш-функціями зручними для практичного використання, а не з ідеалізованими випадковими функціями, проаналізованими раніше.

Список літератури

1. Thorup, Mikkel; Zhang, Yin (2012). Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation. SIAM Journal on Computing 41 (2): 293–331. MR 2914329. doi:10.1137/100800774. 
2. Richter, Stefan; Alvarez, Victor; Dittrich, Jens (2015). A seven-dimensional analysis of hashing methods and its implications on query processing. Proceedings of the VLDB Endowment 9 (3): 293–331. doi:10.14778/2850583.2850585. 
3. Goodrich, Michael T.; Tamassia, Roberto (2015). Section 6.3.3: Linear Probing. Algorithm Design and Applications. Wiley. с. 200–203. 
4. Morin, Pat (22 лютого 2014). Section 5.2: LinearHashTable: Linear Probing. Open Data Structures (in pseudocode) (вид. 0.1Gβ). с. 108–116. Процитовано 15 січня 2016. 
5. Sedgewick, Robert; Wayne, Kevin (2011). Algorithms (вид. 4th). Addison-Wesley Professional. с. 471. ISBN 9780321573513. . Sedgewick and Wayne also halve the table size when a deletion would cause the load factor to become too low, causing them to use a wider range [1/8,1/2] in the possible values of the load factor.
6. Pătraşcu, Mihai; Thorup, Mikkel (2010). On the k-independence required by linear probing and minwise independence. Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6–10, 2010, Proceedings, Part I. Lecture Notes in Computer Science 6198. Springer. с. 715–726. arXiv:1302.5127. doi:10.1007/978-3-642-14165-2_60. 
7. Heileman, Gregory L.; Luo, Wenbin (2005). How caching affects hashing. Seventh Workshop on Algorithm Engineering and Experiments (ALENEX 2005). с. 141–154. 
8. Knuth, Donald (1963). . Архів оригіналу за 3 березня 2016. 
9. Eppstein, David (13 жовтня 2011). Linear probing made easy. 0xDE. 
10. Sedgewick, Robert (2003). Section 14.3: Linear Probing. Algorithms in Java, Parts 1–4: Fundamentals, Data Structures, Sorting, Searching (вид. 3rd). Addison Wesley. с. 615–620. ISBN 9780321623973. 
11. Pittel, B. (1987). Linear probing: the probable largest search time grows logarithmically with the number of records. Journal of Algorithms 8 (2): 236–249. MR 890874. doi:10.1016/0196-6774(87)90040-X. 
12. IdentityHashMap. Java SE 7 Documentation (Oracle). Процитовано 15 січня 2016. 
13. Friesen, Jeff (2012). Beginning Java 7. Expert's voice in Java. Apress. с. 376. ISBN 9781430239109. 
14. Kabutz, Heinz M. (9 вересня 2014). Identity Crisis. The Java Specialists' Newsletter 222. 
15. Weiss, Mark Allen (2014). Chapter 3: Data Structures. У Gonzalez, Teofilo; Diaz-Herrera, Jorge; Tucker, Allen. Computing Handbook 1 (вид. 3rd). CRC Press. с. 3—11. ISBN 9781439898536. .
16. Pagh, Anna; Pagh, Rasmus; Ružić, Milan (2009). Linear probing with constant independence. SIAM Journal on Computing 39 (3): 1107–1120. MR 2538852. arXiv:cs/0612055. doi:10.1137/070702278. 
17. Pătraşcu, Mihai; Thorup, Mikkel (2011). The power of simple tabulation hashing. Proceedings of the 43rd annual ACM Symposium on Theory of Computing (STOC '11). с. 1–10. arXiv:1011.5200. doi:10.1145/1993636.1993638. 
18. Parhami, Behrooz (2006). Introduction to Parallel Processing: Algorithms and Architectures. Series in Computer Science. Springer. 4.1 Development of early models, p. 67. ISBN 9780306469640. 
19. Morin, Pat (2004). Hash tables. У Mehta, Dinesh P.; Sahni, Sartaj. Handbook of Data Structures and Applications. Chapman & Hall / CRC. с. 9Шаблон:Hyphen15. ISBN 9781420035179. .
20. Flajolet, P.; Poblete, P.; Viola, A. (1998). On the analysis of linear probing hashing. Algorithmica 22 (4): 490–515. MR 1701625. doi:10.1007/PL00009236. 
21. Knuth, D. E. (1998). Linear probing and graphs. Algorithmica 22 (4): 561–568. MR 1701629. arXiv:cs/9801103. doi:10.1007/PL00009240.