www.wikidata.uk-ua.nina.az

Зозулине хешування це схема в програмуванні для вирішення колізій значень хеш функцій в геш таблиці з постійним часом ви

Зозулине хешування

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

Приклад зозулиного хешування. Стрілки показують альтернативне положення ключа. Нове значення, яке вставляється в клітинку A, виштовхуючи A в альтернативну клітинку, займану ключем B, значення B переноситься в інше місце, яке в даний час вільне. Вставка нового значення в клітинку H завершується невдачею — H входить у цикл (разом з W), так що тільки що вставлений елемент повинен бути виштовхнутий.

Історія ред.

Зозулине хешування було вперше описане Расмусом Пажом і Флеммінгом Фрішем Родлером у 2001.

Операції ред.

Зозулине хешування є видом відкритої адресації, де кожна непуста комірка геш-таблиці містить ключ або пару ключ-значення. Хеш-функція використовується для визначення місця кожного ключа, його наявності в таблиці (або значення, асоційованого з ним) і може бути знайдене за допомогою перевірки цієї комірки в таблиці. Однак, відкрита адресація потерпає від колізій, які трапляються, коли більше одного ключа потрапляють в одну клітинку. Основна ідея зозулиного хешування полягає у розв'язанні колізій за допомогою використання двох хеш-функцій замість однієї. Це забезпечує два можливі положення у хеш-таблиці для кожного ключа. У одному з звичайних варіантів алгоритму хеш-таблиця розбивається на дві менші таблиці меншого розміру і кожна хеш-функція дає індекс у одну з цих двох таблиць. Можна забезпечити також для обох хеш-функцій індексування всередині однієї таблиці.

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

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

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

— Pagh & Rodler, «Cuckoo Hashing»

Теорія ред.

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

Щоб забезпечити це, використовується теорія випадкових графів — можна утворити неорієнтований граф, званий «зозулиним графом», в якому вершинами є комірки хеш-таблиці, а ребра для кожного хешованого з'єднують два можливих положення (комірки хеш-таблиці). Тоді жадібний алгоритм вставки множини значень в зозулину хеш-таблицю успішно завершується тоді і тільки тоді, коли зозулин граф для цієї множини значень є псевдолісом — графом максимум з одним циклом в кожній компоненті зв'язності. Будь-який породжений вершинами підграф з числом ребер, більшим числа вершин, відповідає безлічі ключів, для яких число слотів в хеш-таблиці недостатнє. Якщо хеш-функція вибирається випадково, зозулиний граф буде випадковим графом в моделі Ердьоша — Ренї [en]. З високим ступенем ймовірності для випадкового графу, в якому відношення числа ребер до числа вершин обмежена зверху 1/2, граф є псевдолісом і алгоритм зозулиного хешування успішно розподіляє всі ключі. Більше того, та ж теорія доводить, що очікуваний розмір компонент зв'язності зозулиного графу малий, що забезпечує постійний очікуваний час вставки .

Приклад ред.

Нехай дано такі дві хеш-функції:

k h (k) h '(k)
20 9 1
50 6 4
53 9 4
75 9 6
100 1 9
67 1 6
105 6 9
3 3 0
36 3 3
39 6 3

Стовпці в наступних двох таблицях показують стан хеш-таблиці після вставки елементів.

1. table for h(k)
20 50 53 75 100 67 105 3 36 39
0
1 100 67 67 67 67 100
2
3 3 36 36
4
5
6 50 50 50 50 50 105 105 105 50
7
8
9 20 20 53 75 75 75 53 53 53 75
10
2. table for h'(k)
20 50 53 75 100 67 105 3 36 39
0 3 3
1 20 20 20 20 20 20 20 20
2
3 39
4 53 53 53 50 50 50 53
5
6 75 75 75 67
7
8
9 100 100 100 100 105
10

Цикли ред.

Якщо ви хочете вставити елемент 6, ви отримаєте нескінченний цикл. В останньому рядку таблиці ми знаходимо ту ж початкову ситуацію, що і на початку.

ключ table 1 table 2
старі значення нові значення старі значення нові значення
6 50 6 53 50
53 75 53 67 75
67 100 67 105 100
105 6 105 3 6
3 36 3 39 36
39 105 39 100 105
100 67 100 75 67
75 53 75 50 53
50 39 50 36 39
36 3 36 6 3
6 50 6 53 50

Варіації ред.

Вивчалися деякі варіації зозулиного хешування, в основному з метою поліпшити використання простору шляхом збільшення коефіцієнта завантаження. У цих варіантах може досягатися поріг навантаження більше 50 %. Деякі з цих методів можуть бути використані для істотного зменшення числа необхідних перебудов структури даних.

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

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

Деякі дослідники пропонують використовувати в деяких кешах процесора спрощене узагальнення зозулиного хешування, званого несиметричним асоціативним кешем.

Порівняння з аналогічними структурами ред.

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

Дослідження, проведені Жуковським, Хеманом і Бонзом , показали, що зозулине хешування істотно швидше методу ланцюжків для малих хеш-таблиць, що знаходяться в кеші сучасних процесорів. Кеннет Росс показав блочну версію зозулиного хешування (блок містить більше одного ключа), який працює швидше звичайних методів для великих хеш-таблиць в разі високого коефіцієнта завантаження. Швидкість роботи блокової версії зозулиної хеш-таблиці пізніше досліджував Аскітіс у порівнянні з іншими схемами хешування.

Див. також ред.

Примітки ред.

  1. ↑ Pagh, Rodler, 2001, с. 121–133.
  2. Kutzelnigg, 2006, с. 403–406.
  3. Mitzenmacher, 2009.
  4. Dietzfelbinger, Weidling, 2007, с. 47–68.
  5. Kirsch, Mitzenmacher, Wieder, 2010, с. 1543–1561.
  6. Aumüller, Dietzfelbinger, Woelfel, 2014, с. 428–456.
  7. «Micro-Architecture» [ 29 грудня 2019 у Wayback Machine.].
  8. Fan, Kaminsky, Andersen, 2013, с. 36–40.
  9. Zukowski, Heman, Boncz, 2006.
  10. Ross, 2006.
  11. Askitis, 2009, с. 113–122.

Література ред.

  • Martin Dietzfelbinger, Christoph Weidling.  // Theoret. Comput. Sci.. — 2007. — Вип. 1-2. — С. 47–68.
  • Adam Kirsch, Michael D. Mitzenmacher, Udi Wieder.  // SIAM J. Comput.. — 2010. — Вип. 4. — С. 1543–1561.
  • Martin Aumüller, Martin Dietzfelbinger, Philipp Woelfel.  // Algorithmica. — 2014. — Вип. 3. — С. 428–456.
  • Bin Fan, Michael Kaminsky, David Andersen. Архівована копія // ;login:. — USENIX, 2013. — Вип. 4. — С. 36–40. з джерела 1 серпня 2014. Процитовано 12 червня 2014.
  • Marcin Zukowski, Sandor Heman, Peter Boncz. Архівована копія. — Proceedings of the International Workshop on Data Management on New Hardware (DaMoN), 2006. з джерела 15 травня 2019. Процитовано 2008-10-16.
  • Kenneth Ross. Архівована копія. — IBM Research Report RC24100, 2006. з джерела 28 листопада 2019. Процитовано 2008-10-16.

Посилання ред.

Приклади ред.

На цю статтю не посилаються інші статті Вікіпедії.
Будь ласка, скористайтеся підказкою та розставте посилання відповідно до прийнятих рекомендацій.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Zozuline heshuvannya ce shema v programuvanni dlya virishennya kolizij znachen hesh funkcij v gesh tablici z postijnim chasom vibirki v girshomu vipadku Nazva pohodit vid povedinki deyakih vidiv zozul koli ptashenya zozuli vishtovhuye yajcya abo inshih ptashenyat z gnizda vidrazu pislya togo yak vilupitsya Analogichne vidbuvayetsya v zozulinomu heshi koli vstavka novogo klyucha v tablicyu mozhe vishtovhnuti starij klyuch v inshe misce v tablici Priklad zozulinogo heshuvannya Strilki pokazuyut alternativne polozhennya klyucha Nove znachennya yake vstavlyayetsya v klitinku A vishtovhuyuchi A v alternativnu klitinku zajmanu klyuchem B znachennya B perenositsya v inshe misce yake v danij chas vilne Vstavka novogo znachennya v klitinku H zavershuyetsya nevdacheyu H vhodit u cikl razom z W tak sho tilki sho vstavlenij element povinen buti vishtovhnutij Zmist 1 Istoriya 2 Operaciyi 3 Teoriya 4 Priklad 4 1 Cikli 5 Variaciyi 6 Porivnyannya z analogichnimi strukturami 7 Div takozh 8 Primitki 9 Literatura 10 Posilannya 10 1 PrikladiIstoriya red Zozuline heshuvannya bulo vpershe opisane Rasmusom Pazhom i Flemmingom Frishem Rodlerom u 2001 Operaciyi red Zozuline heshuvannya ye vidom vidkritoyi adresaciyi de kozhna nepusta komirka gesh tablici mistit klyuch abo paru klyuch znachennya Hesh funkciya vikoristovuyetsya dlya viznachennya miscya kozhnogo klyucha jogo nayavnosti v tablici abo znachennya asocijovanogo z nim i mozhe buti znajdene za dopomogoyu perevirki ciyeyi komirki v tablici Odnak vidkrita adresaciya poterpaye vid kolizij yaki traplyayutsya koli bilshe odnogo klyucha potraplyayut v odnu klitinku Osnovna ideya zozulinogo heshuvannya polyagaye u rozv yazanni kolizij za dopomogoyu vikoristannya dvoh hesh funkcij zamist odniyeyi Ce zabezpechuye dva mozhlivi polozhennya u hesh tablici dlya kozhnogo klyucha U odnomu z zvichajnih variantiv algoritmu hesh tablicya rozbivayetsya na dvi menshi tablici menshogo rozmiru i kozhna hesh funkciya daye indeks u odnu z cih dvoh tablic Mozhna zabezpechiti takozh dlya oboh hesh funkcij indeksuvannya vseredini odniyeyi tablici Vibirka vimagaye pereglyadu vsogo dvoh misc v hesh tablici sho vimagaye postijnogo chasu v girshomu vipadku div O velike i o male Ce kontrastuye z bagatma inshimi algoritmami hesh tablic yaki ne zabezpechuyut postijnij chas vibirki v girshomu vipadku Vidalennya takozh mozhe buti zdijsneno ochishennyam komirki sho mistit klyuch za postijnij chas v girshomu vipadku sho zdijsnyuyetsya prostishe nizh v inshih shemah takih yak linijne zonduvannya Koli vstavlyayetsya novij klyuch i odna z dvoh komirok porozhnya klyuch mozhe buti pomishenij v cyu komirku U razi zh koli obidvi komirki zajnyati neobhidno peremistiti inshi klyuchi v inshi miscya abo navpaki na yih kolishni miscya shob zvilniti misce dlya novogo klyucha Vikoristovuyetsya zhadibnij algoritm klyuch pomishayetsya v odnu z mozhlivih pozicij vishtovhuyuchi bud yakij klyuch yakij buv v cij poziciyi Vishtovhnutij klyuch potim pomishayetsya v jogo alternativnu poziciyu znovu vishtovhuyuchi bud yakij klyuch yakij mozhe tam opinitisya Proces trivaye poki ne znajdetsya porozhnya poziciya Prote mozhlivij vipadok koli proces vstavki zakinchuyetsya nevdacheyu potraplyayuchi v neskinchennij cikl abo koli utvoryuyetsya nadto dovgij lancyuzhok dovshe nizh zazdalegid zadanij porig zalezhit logarifmichno vid dovzhini tablici V comu vipadku hesh tablicya perebudovuyetsya na misci z novimi hesh funkciyami nbsp Nemaye neobhidnosti rozmishennya novoyi tablici dlya povtornogo heshuvannya mi mozhemo prosto pereglyadati tablicyu dlya vidalennya i povtornoyi vstavki vsih klyuchiv yaki znahodyatsya ne v tij poziciyi v yakij povinni buli b stoyati 1 nbsp Pagh amp Rodler Cuckoo Hashing Teoriya red Ochikuvanij chas vstavki postijnij 1 navit yaksho brati do uvagi mozhlivu neobhidnist perebudovi tablici poki chislo klyuchiv menshe polovini yemnosti hesh tablici tobto koeficiyent navantazhennya menshe 50 Shob zabezpechiti ce vikoristovuyetsya teoriya vipadkovih grafiv mozhna utvoriti neoriyentovanij graf zvanij zozulinim grafom v yakomu vershinami ye komirki hesh tablici a rebra dlya kozhnogo heshovanogo z yednuyut dva mozhlivih polozhennya komirki hesh tablici Todi zhadibnij algoritm vstavki mnozhini znachen v zozulinu hesh tablicyu uspishno zavershuyetsya todi i tilki todi koli zozulin graf dlya ciyeyi mnozhini znachen ye psevdolisom grafom maksimum z odnim ciklom v kozhnij komponenti zv yaznosti Bud yakij porodzhenij vershinami pidgraf z chislom reber bilshim chisla vershin vidpovidaye bezlichi klyuchiv dlya yakih chislo slotiv v hesh tablici nedostatnye Yaksho hesh funkciya vibirayetsya vipadkovo zozulinij graf bude vipadkovim grafom v modeli Erdosha Renyi en Z visokim stupenem jmovirnosti dlya vipadkovogo grafu v yakomu vidnoshennya chisla reber do chisla vershin obmezhena zverhu 1 2 graf ye psevdolisom i algoritm zozulinogo heshuvannya uspishno rozpodilyaye vsi klyuchi Bilshe togo ta zh teoriya dovodit sho ochikuvanij rozmir komponent zv yaznosti zozulinogo grafu malij sho zabezpechuye postijnij ochikuvanij chas vstavki 2 Priklad red Nehaj dano taki dvi hesh funkciyi h k k mod 11 displaystyle h left k right k mod 11 nbsp h k k 11 mod 11 displaystyle h left k right left lfloor frac k 11 right rfloor mod 11 nbsp k h k h k 20 9 150 6 453 9 475 9 6100 1 967 1 6105 6 93 3 036 3 339 6 3Stovpci v nastupnih dvoh tablicyah pokazuyut stan hesh tablici pislya vstavki elementiv 1 table for h k 20 50 53 75 100 67 105 3 36 3901 100 67 67 67 67 10023 3 36 36456 50 50 50 50 50 105 105 105 50789 20 20 53 75 75 75 53 53 53 75102 table for h k 20 50 53 75 100 67 105 3 36 390 3 31 20 20 20 20 20 20 20 2023 394 53 53 53 50 50 50 5356 75 75 75 67789 100 100 100 100 10510Cikli red Yaksho vi hochete vstaviti element 6 vi otrimayete neskinchennij cikl V ostannomu ryadku tablici mi znahodimo tu zh pochatkovu situaciyu sho i na pochatku h 6 6 mod 11 6 displaystyle h left 6 right 6 mod 11 6 nbsp h 6 6 11 mod 11 0 displaystyle h left 6 right left lfloor frac 6 11 right rfloor mod 11 0 nbsp klyuch table 1 table 2stari znachennya novi znachennya stari znachennya novi znachennya6 50 6 53 5053 75 53 67 7567 100 67 105 100105 6 105 3 63 36 3 39 3639 105 39 100 105100 67 100 75 6775 53 75 50 5350 39 50 36 3936 3 36 6 36 50 6 53 50Variaciyi red Vivchalisya deyaki variaciyi zozulinogo heshuvannya v osnovnomu z metoyu polipshiti vikoristannya prostoru shlyahom zbilshennya koeficiyenta zavantazhennya U cih variantah mozhe dosyagatisya porig navantazhennya bilshe 50 Deyaki z cih metodiv mozhut buti vikoristani dlya istotnogo zmenshennya chisla neobhidnih perebudov strukturi danih Vid uzagalnennya zozulinogo heshuvannya sho vikoristovuye ponad dvi hesh funkcij mozhna ochikuvati krashogo vikoristannya hesh tablici zhertvuyuchi deyakoyu shvidkistyu vibirki i vstavki Vikoristannya troh hesh funkcij pidvishuye koeficiyent zavantazhennya do 91 3 Inshe uzagalnennya zozulinogo heshuvannya zvane blokovim zozulinim heshuvannyam mistit bilshe odnogo klyucha na komirku Vikoristannya dvoh klyuchiv na komirku dozvolyaye pidvishiti zavantazhennya vishe 80 4 She odin variant zozuline heshuvannya z zapasom Zapas ce masiv klyuchiv postijnoyi dovzhini yakij vikoristovuyetsya dlya zberigannya klyuchiv yaki ne mozhut buti uspishno vstavleni v golovnu hesh tablicyu Cya modifikaciya zmenshuye chislo nevdach do nazad polinomialnoyi funkciyi zi stupenem yaka mozhe buti dovilno velikoyu shlyahom zbilshennya rozmiru zapasu Odnak velikij zapas oznachaye bilsh povilnij poshuk klyucha yakogo nemaye v osnovnij tablici abo yaksho vin znahoditsya v zapasi Zapas mozhna vikoristovuvati v kombinaciyi z bilsh nizh dvoma hesh funkciyami abo z blokovim zozulinim heshuvannyam dlya otrimannya yak visokogo stupenya zavantazhennya tak i malogo chisla nevdach vstavki 5 Analiz zozulinogo heshuvannya z zapasom poshirivsya i na praktichni hesh funkciyi ne tilki vipadkovi modeli hesh funkcij yaki vikoristovuyutsya v teoretichnomu analizi heshuvannya 6 Deyaki doslidniki proponuyut vikoristovuvati v deyakih keshah procesora sproshene uzagalnennya zozulinogo heshuvannya zvanogo nesimetrichnim asociativnim keshem 7 Porivnyannya z analogichnimi strukturami red Ye inshi algoritmi yaki vikoristovuyut kilka hesh funkcij zokrema filtr Bluma efektivna po pam yati struktura danih dlya nechitkih mnozhin Alternativna struktura danih dlya zadach z timi zh nechitkimi mnozhinami zasnovana na zozulinomu heshuvanni zvana zozulinim filtrom vikoristovuye menshu kilkist pam yati i na vidminu vid klasichnih filtriv Bluma dozvolyaye ne tilki vstavku i perevirku isnuvannya ale i vidalennya elementa Odnak teoretichnij analiz cih metodiv provedeno znachno slabshe nizh analiz filtriv Bluma 8 Doslidzhennya provedeni Zhukovskim Hemanom i Bonzom 9 pokazali sho zozuline heshuvannya istotno shvidshe metodu lancyuzhkiv dlya malih hesh tablic sho znahodyatsya v keshi suchasnih procesoriv Kennet Ross 10 pokazav blochnu versiyu zozulinogo heshuvannya blok mistit bilshe odnogo klyucha yakij pracyuye shvidshe zvichajnih metodiv dlya velikih hesh tablic v razi visokogo koeficiyenta zavantazhennya Shvidkist roboti blokovoyi versiyi zozulinoyi hesh tablici piznishe doslidzhuvav Askitis 11 u porivnyanni z inshimi shemami heshuvannya Div takozh red Koliziya gesh funkciyi Hesh funkciyaPrimitki red a b Pagh Rodler 2001 s 121 133 Kutzelnigg 2006 s 403 406 Mitzenmacher 2009 Dietzfelbinger Weidling 2007 s 47 68 Kirsch Mitzenmacher Wieder 2010 s 1543 1561 Aumuller Dietzfelbinger Woelfel 2014 s 428 456 Micro Architecture Arhivovano 29 grudnya 2019 u Wayback Machine Fan Kaminsky Andersen 2013 s 36 40 Zukowski Heman Boncz 2006 Ross 2006 Askitis 2009 s 113 122 Literatura red Martin Dietzfelbinger Christoph Weidling Theoret Comput Sci 2007 Vip 1 2 S 47 68 Adam Kirsch Michael D Mitzenmacher Udi Wieder SIAM J Comput 2010 Vip 4 S 1543 1561 Martin Aumuller Martin Dietzfelbinger Philipp Woelfel Algorithmica 2014 Vip 3 S 428 456 Bin Fan Michael Kaminsky David Andersen Arhivovana kopiya login USENIX 2013 Vip 4 S 36 40 Arhivovano z dzherela 1 serpnya 2014 Procitovano 12 chervnya 2014 Marcin Zukowski Sandor Heman Peter Boncz Arhivovana kopiya Proceedings of the International Workshop on Data Management on New Hardware DaMoN 2006 Arhivovano z dzherela 15 travnya 2019 Procitovano 2008 10 16 Kenneth Ross Arhivovana kopiya IBM Research Report RC24100 2006 Arhivovano z dzherela 28 listopada 2019 Procitovano 2008 10 16 Posilannya red A cool and practical alternative to traditional hash Arhivovano 7 kvitnya 2019 u Wayback Machine tables U Erlingsson M Manasse F Mcsherry 2006 Cuckoo Hashing for Undergraduates 2006 Arhivovano 15 chervnya 2011 u Wayback Machine R Pagh 2006 Cuckoo Hashing Theory and Practice Arhivovano 28 listopada 2019 u Wayback Machine Part 1 Part 2 Arhivovano 28 listopada 2019 u Wayback Machine and Part 3 Arhivovano 28 listopada 2019 u Wayback Machine Michael Mitzenmacher 2007 Algorithmic Improvements for Fast Concurrent Cuckoo Hashing Arhivovano 21 bereznya 2020 u Wayback Machine X Li D Andersen M Kaminsky M Freedman EuroSys 2014 Prikladi red Concurrent high performance Cuckoo hashtable written in C Arhivovano 2 kvitnya 2019 u Wayback Machine Cuckoo hash map written in C Arhivovano 28 listopada 2019 u Wayback Machine Static cuckoo hashtable generator for C C Arhivovano 18 grudnya 2019 u Wayback Machine Cuckoo hash table written in Haskell Cuckoo hashing for Go Arhivovano 16 veresnya 2020 u Wayback Machine Na cyu stattyu ne posilayutsya inshi statti Vikipediyi Bud laska skoristajtesya pidkazkoyu ta rozstavte posilannya vidpovidno do prijnyatih rekomendacij Otrimano z https uk wikipedia org w index php title Zozuline heshuvannya amp oldid 36252254