Геш-таблиця — структура даних, що реалізує інтерфейс асоціативного масиву, а саме, вона дозволяє зберігати пари (ключ, значення) і здійснювати три операції: операцію додавання нової пари, операцію пошуку і операцію видалення за ключем.
Вступ
Існує два основних варіанта геш-таблиць: з ланцюжками і з відкритою адресацією. Геш-таблиця містить в собі деякий масив H, елементами якого є пари (геш-таблиця з відкритою адресацією) або списки пар (геш-таблиця з ланцюжками).
Виконання операцій в геш-таблиці починається з обчислення геш-функції від ключа. Отримане геш-значення i = hash(key) відіграє роль індексу в масиві H. Після цього операція (додавання, видалення, пошук) перенаправляється об'єктові, який зберігається у відповідній комірці масиву H[i].
Ситуація, коли для різних ключів отримується одне й те саме геш-значення, називається колізією. Такі події непоодинокі — наприклад, при додаванні в геш-таблицю розміром 365 комірок усього лише 23-х елементів ймовірність колізії вже перевищує 50 відсотків (якщо кожний елемент може з однаковою ймовірністю потрапити в будь-яку комірку) — див. парадокс днів народження. Через це механізм розв'язання колізій — важлива складова будь-якої геш-таблиці.
В деяких особливих випадках вдається взагалі уникнути колізій. Наприклад, якщо всі ключі елементів відомі заздалегідь (або дуже рідко змінюються), тоді для них можна знайти деяку [en], яка розподілить їх за комірками геш-таблиці без колізій. Геш-таблиці, які використовують подібні геш-функції, не потребують механізму розв'язання колізій, і називаються геш-таблицями з прямою адресацією.
Властивості геш-таблиці
Важлива властивість геш-таблиць полягає в тому, що, при деяких розумних припущеннях, всі три операції (пошук, вставлення і видалення елементів) зазвичай виконується за час O(1). Але при цьому не гарантується, що час виконання окремої операції малий, з певною імовірністю час може бути сумірним із пошуком у списку. З ростом коефіцієнта заповнення таблиці ця імовірність, і, відповідно, середній час виконання операцій, ростуть. Тому при досягненні деякого значення коефіцієнта заповнення необхідно здійснювати перебудову індексу геш-таблиці: збільшити розміри масиву H і заново додати в порожню геш-таблицю всі пари.
Розв'язання колізій
Існує декілька способів розв'язання колізій.
Метод ланцюжків
Кожна комірка масиву H є вказівником на зв'язаний список (ланцюжок) пар ключ-значення, відповідних одному і тому самому геш-значенню ключа. Колізії просто призводять до того, що з'являються ланцюжки довжиною більше одного елемента.
Операції пошуку або видалення елемента вимагають перегляду всіх елементів відповідного ланцюжка, щоб знайти в ньому елемент з заданим ключем. Для додавання нового елемента необхідно додати елемент в кінець або початок відповідного списку, і, у випадку якщо коефіцієнт заповнення стане занадто великим, збільшити розмір масиву H і перебудувати таблицю.
При припущенні, що кожний елемент може потрапити в будь-яку позицію таблиці H з однаковою ймовірністю і незалежно від того, куди потрапив будь-який елемент, пересічний час роботи операції пошуку елемента складає Θ(1 + α), де α — коефіцієнт заповнення таблиці.
Відкрита адресація
В стратегії, названій [en], всі записи зберігаються в самому масиві H. Коли додається новий запис, масив перевіряється в певному порядку, доки не буде знайдена вільна комірка, куди буде доданий елемент. У випадку пошуку елемента, масив сканується в тій самій послідовності, доки потрібний запис або порожня комірка не буде знайдена. Останнє — означає відсутність елемента. Назва «відкрита адресація» показує, що положення («адреса») елемента не визначається його геш-значенням. Цей метод також називають закритим гешуванням.
Загалом, послідовність, у якій переглядаються комірки геш-таблиці, залежить лише від ключа елемента. Тобто це послідовність h0(x), h1(x), …, hn-1(x), де x — ключ елемента, а hi(x) — довільна функція, яка порівнює кожен ключ комірки з геш-таблицею. Перший елемент послідовності, зазвичай, дорівнює значенню деякої геш-функції від ключа, а наступні обчислюються одним з наведених нижче способів. Для успішної роботи алгоритму пошуку, послідовність перебору має бути такою, щоб всі комірки геш-таблиці виявились переглянутими рівно по одному разу.
Алгоритм пошуку переглядає всі комірку геш-таблиці в тому самому порядку, що і при вставці, доки не знайдеться або елемент з шуканим ключем, або вільна комірка (що означає відсутність елемента в геш-таблиці).
Видалення елементів у такій схемі складніше. Зазвичай воно здійснюється таким чином: заводять булевий прапорець для кожної комірки. Він має означати видалений цей елемент з таблиці чи ні. Тобто видалення елемента означає встановлення цього прапорця. При цьому доведеться модифікувати процедуру пошуку існуючого елемента так, щоб вона вважала видалені комірки зайнятими, а процедуру додавання — щоб вона їх вважала вільними і скидала прапорець при доданні елемента.
Нижче наведені деякі розповсюджені варіанти переборів. Одразу зауважимо, що нумерація елементів послідовності спроб і комірок геш-таблиці при переборі ведеться від нуля, а N — розмір геш-таблиці.
- Лінійне зондування: комірки геш-таблиці послідовно переглядаються з деяким фіксованим інтервалом k між комірками (зазвичай, ), тобто i-й елемент послідовності — це комірка з номером (hash(x) + ik) mod N. Для того, щоб всі комірки виявились перебраними по одному разу, необхідно, щоб k було взаємно-простим з розміром геш-таблиці.
- : інтервал між комірками з кожним кроком збільшується на константу, що задається в загальному вигляді з допомогою деякого квадратичного поліному k1i+k2i2. У найпростішому випадку k1 = 0, k2 = 1 для і = 0,1,2,3,… отримаємо:
- h0 = hash(x) mod N, h1 = (hash(x) + 12) mod N, h2 = (hash(x) + 22) mod N, h3 = (hash(x) + 32) mod N, …
- : інтервал між комірками фіксований, як при лінійному переборі, але, на відміну від нього, розмір інтервалу обчислюється другою, допоміжною геш-функцією, тобто може бути різним для різним ключів. Значення цієї геш-функції мають бути ненульовими і взаємно простими з розміром геш-таблиці, що найпростіше всього зробити, якщо взяти просте число як розмір, і вимагати, щоб допоміжна геш-функція приймала значення від 1 до N − 1.
Недоліком усіх схем відкритої адресації є те, що кількість елементів, які можуть зберігатися в таблиці може досягти кількість комірок в масиві. Дійсно, навіть з хорошими геш-функціями, продуктивність серйозно падає при коефіцієнті завантаження більшому ніж 0,7 або біля того. Для багатьох застосувань, це обмеження викликає необхідність використання динамічної зміну розміру з відповідними затратами.
Схеми відкритої адресації також накладають суворіші вимоги до геш-функції: окрім рівномірного розподілу значень по всьому масиву, функція має також мінімізувати скупчення геш-значень, що слідують одна за одною в послідовності спроб.
Відкрита адресація зберігає пам'ять тільки у випадку якщо елементи малого розміру і коефіцієнт завантаження не дуже малий. Якщо коефіцієнт завантаження близький до нуля, відкрита адресація марнотратна навіть якщо кожен елемент займає лише два машинних слова.
Відкрита адресація уникає витрат на розміщення кожного нового елемента, і може бути реалізована навіть у відсутності розподільника пам'яті. Вона також уникає додаткових посилань для доступу до набору елементів з певним однаковим значенням геш-функції. З малими розмірами елементів, цей фактор може додати продуктивності порівняно з таблицею організованою методом ланцюжків особливо при пошуку.
Геш-таблиця з лінійною адресацією також легше серіалізується, через відсутність вказівників.
З іншого боку, зазвичай відкрита адресація — поганий вибір для великих елементів, через те, що такі елементи заповнюють весь кеш процесора (нівелюючи переваги кешу), також значна кількість місця втрачається через велику кількість порожніх комірок. Якщо відкрита адресація зберігає тільки вказівники на елементи, вона використовує кількість пам'яті, яку можна порівняти з використанням пам'яті методом ланцюжків, але втрачає перевагу в швидкості.
Узагальнюючи, відкриту адресацію краще використовувати для геш-таблиць з малими елементами, які зберігаються в таблиці. Вони особливо підходять для елементів в одне слово або менших. У випадку коли очікується високий коефіцієнт завантаження, елементи великі за розміром, або можуть мати різні розміри, метод ланцюжків показує таку ж або кращу продуктивність.
Зрештою, при розумному використанні, будь-який алгоритм зазвичай достатньо швидкий; і відсоток обчислень в геш-таблицях малий. Використання пам'яті рідко вважається надмірним. Отже, в більшості випадків різниця між цими двома алгоритмами мінімальні, і, як правило, інші міркування виходять на арену.
Гібрид методу ланцюжків та відкритої адресації (англ. Coalesced hashing), що розв'язує колізії з допомогою додаткових ланок між вузлами зв'язаних списків всередині таблиці. Як і метод ланцюжків, не має кластерних ефектів і геш-таблиця може бути ефективно заповнена.
Ще одна альтернатива відкритої адресації — англ. Cuckoo hashing,— забезпечує постійний час пошуку і сталий амортизований час для вставок і вилучень. Цей метод використовує дві чи більше геш-функції, а це означає, що будь-яка пара ключ/значення може знаходитись в двох або більше місцях. Для пошуку використовується перша геш-функція; якщо ключ/значення не знайдено, то використовується друга геш-функція, і так далі. Якщо колізія відбувається під час вставки, то ключ повторно гешується другою геш-функцією, щоб відобразити його в інший бакет. Якщо всі функції гешування використані, а колізія не розв'язана, то старий ключ на місці колізії видаляється, щоб звільнити місце для нового ключа, і цей попередній старий ключ повторно гешується однією з наступних геш-функцій, які відображають його в інший бакет. Якщо це також призводить до колізії, то процес повторюється, поки колізія не зникне або процес пройде через всі бакети в таблиці. Таким шляхом оптимізується використання пам'яті.
Інший альтернативний метод, поєднує в собі зозулине гешування та лінійне зондування але таким чином, щоб обійти обмеження цих методів. Зокрема, він добре працює навіть тоді, коли коефіцієнт завантаження таблиці зростає до 0,9.
Варіант гешування з відкритою адресацією, де в таблиці зберігається, крім ключа, кількість колізій при пошуку (PSL - probe sequence length, довжина послідовності перевірок). Якщо пошук місця для нового елемента має більший PSL, ніж в елемента таблиці, з яким виникла колізія, то новий елемент вставляється на це місце, і підшукується нове місце вже для цього елемента. Таким чином, алгоритм місця забирає у «багатих» (елементів з невеликим PSL) і віддає «бідним» (яких складно знайти), як, за легендою, чинив Робін Гуд. Це дозволяє навіть у гіршому разі робити пошук за O(log(n)) кроків, бо при заповненій таблиці статистично ймовірніше при колізії знайти елемент у середині ланцюжка, пошук елемента також можна оптимізувати, застосувавши так званий розумний пошук, що починається з середини ланцюжка і рухається по одному кроку до початку і до кінця ланцюжка (тобто в послідовності середній, середній-1, середній+1, середній-2, середній+2 і т.д.).
Див. також
Примітки
- геш-таблиця // Англійсько-український словник з математики та інформатики / уклад. Є. Мейнарович, М. Кратко. — 2010.
- Tenenbaum, Aaron M.; Langsam, Yedidyah; Augenstein, Moshe J. (1990). Data Structures Using C. Prentice Hall. с. 456–461, pp. 472. ISBN .
- Herlihy, Maurice; Shavit, Nir; Tzafrir, Moran (2008). Hopscotch Hashing. DISC '08: Proceedings of the 22nd international symposium on Distributed Computing. Berlin, Heidelberg: Springer-Verlag. с. 350—364.
- Celis, Pedro, Robin Hood Hashing (PDF), Univercity of Waterloo
Джерела
- Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 11. Геш-таблиці. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Gesh tablicya struktura danih sho realizuye interfejs asociativnogo masivu a same vona dozvolyaye zberigati pari klyuch znachennya i zdijsnyuvati tri operaciyi operaciyu dodavannya novoyi pari operaciyu poshuku i operaciyu vidalennya za klyuchem VstupIsnuye dva osnovnih varianta gesh tablic z lancyuzhkami i z vidkritoyu adresaciyeyu Gesh tablicya mistit v sobi deyakij masiv H elementami yakogo ye pari gesh tablicya z vidkritoyu adresaciyeyu abo spiski par gesh tablicya z lancyuzhkami Vikonannya operacij v gesh tablici pochinayetsya z obchislennya gesh funkciyi vid klyucha Otrimane gesh znachennya i hash key vidigraye rol indeksu v masivi H Pislya cogo operaciya dodavannya vidalennya poshuk perenapravlyayetsya ob yektovi yakij zberigayetsya u vidpovidnij komirci masivu H i Situaciya koli dlya riznih klyuchiv otrimuyetsya odne j te same gesh znachennya nazivayetsya koliziyeyu Taki podiyi nepoodinoki napriklad pri dodavanni v gesh tablicyu rozmirom 365 komirok usogo lishe 23 h elementiv jmovirnist koliziyi vzhe perevishuye 50 vidsotkiv yaksho kozhnij element mozhe z odnakovoyu jmovirnistyu potrapiti v bud yaku komirku div paradoks dniv narodzhennya Cherez ce mehanizm rozv yazannya kolizij vazhliva skladova bud yakoyi gesh tablici V deyakih osoblivih vipadkah vdayetsya vzagali uniknuti kolizij Napriklad yaksho vsi klyuchi elementiv vidomi zazdalegid abo duzhe ridko zminyuyutsya todi dlya nih mozhna znajti deyaku en yaka rozpodilit yih za komirkami gesh tablici bez kolizij Gesh tablici yaki vikoristovuyut podibni gesh funkciyi ne potrebuyut mehanizmu rozv yazannya kolizij i nazivayutsya gesh tablicyami z pryamoyu adresaciyeyu Vlastivosti gesh tabliciVazhliva vlastivist gesh tablic polyagaye v tomu sho pri deyakih rozumnih pripushennyah vsi tri operaciyi poshuk vstavlennya i vidalennya elementiv zazvichaj vikonuyetsya za chas O 1 Ale pri comu ne garantuyetsya sho chas vikonannya okremoyi operaciyi malij z pevnoyu imovirnistyu chas mozhe buti sumirnim iz poshukom u spisku Z rostom koeficiyenta zapovnennya tablici cya imovirnist i vidpovidno serednij chas vikonannya operacij rostut Tomu pri dosyagnenni deyakogo znachennya koeficiyenta zapovnennya neobhidno zdijsnyuvati perebudovu indeksu gesh tablici zbilshiti rozmiri masivu H i zanovo dodati v porozhnyu gesh tablicyu vsi pari Rozv yazannya kolizijIsnuye dekilka sposobiv rozv yazannya kolizij Metod lancyuzhkiv Rozv yazannya kolizij za dopomogoyu lancyuzhkiv Kozhna komirka masivu H ye vkazivnikom na zv yazanij spisok lancyuzhok par klyuch znachennya vidpovidnih odnomu i tomu samomu gesh znachennyu klyucha Koliziyi prosto prizvodyat do togo sho z yavlyayutsya lancyuzhki dovzhinoyu bilshe odnogo elementa Operaciyi poshuku abo vidalennya elementa vimagayut pereglyadu vsih elementiv vidpovidnogo lancyuzhka shob znajti v nomu element z zadanim klyuchem Dlya dodavannya novogo elementa neobhidno dodati element v kinec abo pochatok vidpovidnogo spisku i u vipadku yaksho koeficiyent zapovnennya stane zanadto velikim zbilshiti rozmir masivu H i perebuduvati tablicyu Pri pripushenni sho kozhnij element mozhe potrapiti v bud yaku poziciyu tablici H z odnakovoyu jmovirnistyu i nezalezhno vid togo kudi potrapiv bud yakij element peresichnij chas roboti operaciyi poshuku elementa skladaye 8 1 a de a koeficiyent zapovnennya tablici Vidkrita adresaciya Priklad rozv yazku kolizij v gesh tablici z vidkritoyu adresaciyeyu ta linijnim pereborom interval 1 Zauvazhte Ted Baker maye unikalne gesh znachennya ale vse odno utvoryuye koliziyu z Sandra Dee yaka pered cim stvorila koliziyu z John Smith V strategiyi nazvanij en vsi zapisi zberigayutsya v samomu masivi H Koli dodayetsya novij zapis masiv pereviryayetsya v pevnomu poryadku doki ne bude znajdena vilna komirka kudi bude dodanij element U vipadku poshuku elementa masiv skanuyetsya v tij samij poslidovnosti doki potribnij zapis abo porozhnya komirka ne bude znajdena Ostannye oznachaye vidsutnist elementa Nazva vidkrita adresaciya pokazuye sho polozhennya adresa elementa ne viznachayetsya jogo gesh znachennyam Cej metod takozh nazivayut zakritim geshuvannyam Zagalom poslidovnist u yakij pereglyadayutsya komirki gesh tablici zalezhit lishe vid klyucha elementa Tobto ce poslidovnist h0 x h1 x hn 1 x de x klyuch elementa a hi x dovilna funkciya yaka porivnyuye kozhen klyuch komirki z gesh tabliceyu Pershij element poslidovnosti zazvichaj dorivnyuye znachennyu deyakoyi gesh funkciyi vid klyucha a nastupni obchislyuyutsya odnim z navedenih nizhche sposobiv Dlya uspishnoyi roboti algoritmu poshuku poslidovnist pereboru maye buti takoyu shob vsi komirki gesh tablici viyavilis pereglyanutimi rivno po odnomu razu Algoritm poshuku pereglyadaye vsi komirku gesh tablici v tomu samomu poryadku sho i pri vstavci doki ne znajdetsya abo element z shukanim klyuchem abo vilna komirka sho oznachaye vidsutnist elementa v gesh tablici Vidalennya elementiv u takij shemi skladnishe Zazvichaj vono zdijsnyuyetsya takim chinom zavodyat bulevij praporec dlya kozhnoyi komirki Vin maye oznachati vidalenij cej element z tablici chi ni Tobto vidalennya elementa oznachaye vstanovlennya cogo praporcya Pri comu dovedetsya modifikuvati proceduru poshuku isnuyuchogo elementa tak shob vona vvazhala vidaleni komirki zajnyatimi a proceduru dodavannya shob vona yih vvazhala vilnimi i skidala praporec pri dodanni elementa Nizhche navedeni deyaki rozpovsyudzheni varianti pereboriv Odrazu zauvazhimo sho numeraciya elementiv poslidovnosti sprob i komirok gesh tablici pri perebori vedetsya vid nulya a N rozmir gesh tablici Linijne zonduvannya komirki gesh tablici poslidovno pereglyadayutsya z deyakim fiksovanim intervalom k mizh komirkami zazvichaj tobto i j element poslidovnosti ce komirka z nomerom hash x ik mod N Dlya togo shob vsi komirki viyavilis perebranimi po odnomu razu neobhidno shob k bulo vzayemno prostim z rozmirom gesh tablici interval mizh komirkami z kozhnim krokom zbilshuyetsya na konstantu sho zadayetsya v zagalnomu viglyadi z dopomogoyu deyakogo kvadratichnogo polinomu k1i k2i2 U najprostishomu vipadku k1 0 k2 1 dlya i 0 1 2 3 otrimayemo h0 hash x mod N h1 hash x 12 mod N h2 hash x 22 mod N h3 hash x 32 mod N interval mizh komirkami fiksovanij yak pri linijnomu perebori ale na vidminu vid nogo rozmir intervalu obchislyuyetsya drugoyu dopomizhnoyu gesh funkciyeyu tobto mozhe buti riznim dlya riznim klyuchiv Znachennya ciyeyi gesh funkciyi mayut buti nenulovimi i vzayemno prostimi z rozmirom gesh tablici sho najprostishe vsogo zrobiti yaksho vzyati proste chislo yak rozmir i vimagati shob dopomizhna gesh funkciya prijmala znachennya vid 1 do N 1 Nedolikom usih shem vidkritoyi adresaciyi ye te sho kilkist elementiv yaki mozhut zberigatisya v tablici mozhe dosyagti kilkist komirok v masivi Dijsno navit z horoshimi gesh funkciyami produktivnist serjozno padaye pri koeficiyenti zavantazhennya bilshomu nizh 0 7 abo bilya togo Dlya bagatoh zastosuvan ce obmezhennya viklikaye neobhidnist vikoristannya dinamichnoyi zminu rozmiru z vidpovidnimi zatratami Shemi vidkritoyi adresaciyi takozh nakladayut suvorishi vimogi do gesh funkciyi okrim rivnomirnogo rozpodilu znachen po vsomu masivu funkciya maye takozh minimizuvati skupchennya gesh znachen sho sliduyut odna za odnoyu v poslidovnosti sprob Vidkrita adresaciya zberigaye pam yat tilki u vipadku yaksho elementi malogo rozmiru i koeficiyent zavantazhennya ne duzhe malij Yaksho koeficiyent zavantazhennya blizkij do nulya vidkrita adresaciya marnotratna navit yaksho kozhen element zajmaye lishe dva mashinnih slova Grafik porivnyuye peresichnu kilkist vtrat potribnih dlya poshuku elementa v tablici metodom lancyuzhkiv i linijnim pereborom Koli tablicya zavantazhena bilshe nizh na 80 efektivnist linijnogo pereboru znachno padaye Vidkrita adresaciya unikaye vitrat na rozmishennya kozhnogo novogo elementa i mozhe buti realizovana navit u vidsutnosti rozpodilnika pam yati Vona takozh unikaye dodatkovih posilan dlya dostupu do naboru elementiv z pevnim odnakovim znachennyam gesh funkciyi Z malimi rozmirami elementiv cej faktor mozhe dodati produktivnosti porivnyano z tabliceyu organizovanoyu metodom lancyuzhkiv osoblivo pri poshuku Gesh tablicya z linijnoyu adresaciyeyu takozh legshe serializuyetsya cherez vidsutnist vkazivnikiv Z inshogo boku zazvichaj vidkrita adresaciya poganij vibir dlya velikih elementiv cherez te sho taki elementi zapovnyuyut ves kesh procesora nivelyuyuchi perevagi keshu takozh znachna kilkist miscya vtrachayetsya cherez veliku kilkist porozhnih komirok Yaksho vidkrita adresaciya zberigaye tilki vkazivniki na elementi vona vikoristovuye kilkist pam yati yaku mozhna porivnyati z vikoristannyam pam yati metodom lancyuzhkiv ale vtrachaye perevagu v shvidkosti Uzagalnyuyuchi vidkritu adresaciyu krashe vikoristovuvati dlya gesh tablic z malimi elementami yaki zberigayutsya v tablici Voni osoblivo pidhodyat dlya elementiv v odne slovo abo menshih U vipadku koli ochikuyetsya visokij koeficiyent zavantazhennya elementi veliki za rozmirom abo mozhut mati rizni rozmiri metod lancyuzhkiv pokazuye taku zh abo krashu produktivnist Zreshtoyu pri rozumnomu vikoristanni bud yakij algoritm zazvichaj dostatno shvidkij i vidsotok obchislen v gesh tablicyah malij Vikoristannya pam yati ridko vvazhayetsya nadmirnim Otzhe v bilshosti vipadkiv riznicya mizh cimi dvoma algoritmami minimalni i yak pravilo inshi mirkuvannya vihodyat na arenu Gibrid metodu lancyuzhkiv ta vidkritoyi adresaciyi angl Coalesced hashing sho rozv yazuye koliziyi z dopomogoyu dodatkovih lanok mizh vuzlami zv yazanih spiskiv vseredini tablici Yak i metod lancyuzhkiv ne maye klasternih efektiv i gesh tablicya mozhe buti efektivno zapovnena Zozuline geshuvannya She odna alternativa vidkritoyi adresaciyi angl Cuckoo hashing zabezpechuye postijnij chas poshuku i stalij amortizovanij chas dlya vstavok i viluchen Cej metod vikoristovuye dvi chi bilshe gesh funkciyi a ce oznachaye sho bud yaka para klyuch znachennya mozhe znahoditis v dvoh abo bilshe miscyah Dlya poshuku vikoristovuyetsya persha gesh funkciya yaksho klyuch znachennya ne znajdeno to vikoristovuyetsya druga gesh funkciya i tak dali Yaksho koliziya vidbuvayetsya pid chas vstavki to klyuch povtorno geshuyetsya drugoyu gesh funkciyeyu shob vidobraziti jogo v inshij baket Yaksho vsi funkciyi geshuvannya vikoristani a koliziya ne rozv yazana to starij klyuch na misci koliziyi vidalyayetsya shob zvilniti misce dlya novogo klyucha i cej poperednij starij klyuch povtorno geshuyetsya odniyeyu z nastupnih gesh funkcij yaki vidobrazhayut jogo v inshij baket Yaksho ce takozh prizvodit do koliziyi to proces povtoryuyetsya poki koliziya ne znikne abo proces projde cherez vsi baketi v tablici Takim shlyahom optimizuyetsya vikoristannya pam yati Inshij alternativnij metod poyednuye v sobi zozuline geshuvannya ta linijne zonduvannya ale takim chinom shob obijti obmezhennya cih metodiv Zokrema vin dobre pracyuye navit todi koli koeficiyent zavantazhennya tablici zrostaye do 0 9 Variant geshuvannya z vidkritoyu adresaciyeyu de v tablici zberigayetsya krim klyucha kilkist kolizij pri poshuku PSL probe sequence length dovzhina poslidovnosti perevirok Yaksho poshuk miscya dlya novogo elementa maye bilshij PSL nizh v elementa tablici z yakim vinikla koliziya to novij element vstavlyayetsya na ce misce i pidshukuyetsya nove misce vzhe dlya cogo elementa Takim chinom algoritm miscya zabiraye u bagatih elementiv z nevelikim PSL i viddaye bidnim yakih skladno znajti yak za legendoyu chiniv Robin Gud Ce dozvolyaye navit u girshomu razi robiti poshuk za O log n krokiv bo pri zapovnenij tablici statistichno jmovirnishe pri koliziyi znajti element u seredini lancyuzhka poshuk elementa takozh mozhna optimizuvati zastosuvavshi tak zvanij rozumnij poshuk sho pochinayetsya z seredini lancyuzhka i ruhayetsya po odnomu kroku do pochatku i do kincya lancyuzhka tobto v poslidovnosti serednij serednij 1 serednij 1 serednij 2 serednij 2 i t d Div takozhTablicya poshuku AvtovivifikaciyaPrimitkigesh tablicya Anglijsko ukrayinskij slovnik z matematiki ta informatiki uklad Ye Mejnarovich M Kratko 2010 Tenenbaum Aaron M Langsam Yedidyah Augenstein Moshe J 1990 Data Structures Using C Prentice Hall s 456 461 pp 472 ISBN 0 13 199746 7 Herlihy Maurice Shavit Nir Tzafrir Moran 2008 Hopscotch Hashing DISC 08 Proceedings of the 22nd international symposium on Distributed Computing Berlin Heidelberg Springer Verlag s 350 364 Celis Pedro Robin Hood Hashing PDF Univercity of WaterlooDzherelaT Kormen Ch Lejzerson R Rivest K Stajn 2009 1990 11 Gesh tablici Vstup do algoritmiv vid 3rd MIT Press i McGraw Hill ISBN 0 262 03384 4