Кукавичје хеширање

Пример Кукавичјег хеширања. Стрелице показују алтернативне локације сваког кључа. Нови елемент ће биту убачен на локацију А померањем А на његову алтернативну локацију, тренутну заузету елементом В, и померањем В на његову алтернативну локацију, која је тренутно слободна. Убацивање новог елемента на локацију елемента Н не би успело јер је Н део циклуса (ѕаједно са W), нови елемент би био опет избачен

Кукавичје хеширање је шема у програмирању за решавање хеш судара вредности хеш функција у табели, са најгорим случајем константног проналажења времена. Назив потиче од понашања неких врста кукавице, где женка кукавице гура друга јаја или младе из гнезда када се излегну; аналогно, убацивање новог кључа у кукавичјој хеш табели може померити старији кључ на неко друго место у табели.

Историја

Кукавичји хешинг су први описали Расмуш Паг (Шаблон:Јез-ен) и Флемминг Фрих Родлер (Шаблон:Јез-ен) у 2001.

Теорија

Основна идеја је да користите две хеш функције, уместо само једне. Ово обезбеђује две могуће локације у хеш табели за сваки кључ. У једном од најчешће коришћених варијанти алгоритма, хеш табела је подељена на две мање табеле једнаке величине и свака хеш функција даје индекс у једној од ове две табеле. Када се убаци нови кључ, користи се похлепни алгоритам. Нови кључ се убацује у једну од своје две могуће локације, " избацивање " , то је, померање, било којег кључа који се већ можда налази на тој локацији. Овај померен кључ се онда убацује у своју алтернативну локацију, поново избацује било који кључ који се тамо налази, докле год се не нађе упражњено место, или ће поступак ући у бесконачну петљу. У другом случају, хеш табела је обновљена на месту помоћу нове хеш функције. Нема потребе да се алоцира нова табела за поновно хеширање. Једноставно можемо проћи кроз табеле бришући и извршити уобичајену процедуру убацивања на свим кључевима који нису нађени на својим намењеним местима у табели .

- Pagh & Rodler, "Cuckoo Hashing"

Претрага захтева преглед од само две локације у хеш табели, који у најгорем случају (погледати Велико О нотацију) временски траје константно. Ово је у супротности са многим другим алгоритмима хеш табела, који не могу да имају стални најгори случај везан за време да уради претрагу. Такође се показало да су уметања успела у очекиваном константном времену, чак разматрајући могућност обнављања табела, докле год се број кључева држи испод половине капацитета хеш табеле, тј, фактор оптерећења је испод 50%. Један метод доказивања овога користи теорију случајних графова: један може формирати неусмерене графове под називом „Кукавичји граф“ који има највишу тачку за сваку локацију хеш табеле и ивицу за сваку хеш вредност, са крајњим тачкама ивице које су две могуће локације вредности. Онда, похлепни алгоритам убацивања за додавање скупа вредности у кукавичкој хеш табели успева, ако и само ако кукавичји граф за овај скуп вредности је графикон са највише једним циклусом у сваким од његових повезаних компоненти; као сваки подграф индуковане највише тачке са више ивица него чворова одговара скупу кључева за које постоје недовољан број слотова у хеш табели. Ово својство је тачно са великом вероватноћом за случајан граф у коме је број ивица мањи од половине броја чворова.Шаблон:Чињеница

Пример

Задате хеш функције:

$h\left(k\right)=kmod11$
$h^{\prime }\left(k\right)=\lfloor \frac{k}{11}\rfloor mod11$

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. табела за h(k)
	20	50	53	75	100	67	105	3	36	39
0
1					100	67	67	67	67	100
2
3								3	3	36
4
5
6		50	50	50	50	50	105	105	105	50
7
8
9	20	20	20	20	20	20	53	53	53	75
10

2. табела за h'(k)
	20	50	53	75	100	67	105	3	36	39
0										3
1							20	20	20	20
2
3									36	39
4			53	53	53	53	50	50	50	53
5
6				75	75	75	75	75	75	67
7
8
9						100	100	100	100	105
10

Циклус

Уколико желите да убаците елемент 6, улазите у цилус. У последњем реду табеле налазимо исту иницијалну ситуацију, као што је била на почетку.

$h\left(6\right)=6mod11=6$
$h^{\prime }\left(6\right)=\lfloor \frac{6}{11}\rfloor mod11=0$

подразумевани кључ	табела 1		табела 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

Генерализација и примене

Генерализације о кукавичком хеширању које користе више од две алтернативне хеш функције може се очекивати да искористи ефективно већи део простора хеш табеле док жртвује неку брзину претраге и уметања. Коришћењем само три хеш функције повећава оптерећење на 91%. Друга генерализација кукавичког хешинга се састоји у коришћењу више од једног кључа по кофи. Користећи само два кључа по кофи дозвољава фактор оптерећења изнад 80%. Други алгоритми који користе вишеструке хеш функције укључују Блумов Филтер. Кукавичји хешинг може да се користи за имплементацију структуре података еквивалентно Блумовом Филтеру. Поједностављена генерализација кукавичког хеширања звани „искривљени - асоцијативног“ кеш се користи у некој процесорској меморији. Студија Зуковског и сарадника, показале је да је кукавичји хешинг је много бржи него ланчани хешинг за мале хеш табеле на модернисм процесорима смештеним у кешу. Кенет Рос(Шаблон:Јез-ен) је показао да буцкетизед верзије кукавичког хеширања (варијанте које користе кофе које садрже више од једног кључа) бржи од конвенционалних метода који важи исто и за велике хеш табеле, када је искоришћеност простора велика. Перформансе буцкетизед кукавичји хеш табеле је даље истраживао Аскитис, са својим перформансама у поређењу против алтернативних Хесинг шема. Истраживање по Миценмахеру представља отворене проблеме везане за Кукавичко хеширање од 2009 године.

Види још

• Савршена хеш функција
• Линеарно попуњабање
• Дупло хеширање
• Колизије
• Хеш функција
• Квадратно проверавање

Литература

• Шаблон:Cite book
• Шаблон:Cite book

Спољашње везе

• A cool and practical alternative to traditional hash tables Шаблон:Wayback, U. Erlingsson, M. Manasse, F. Mcsherry, 2006.
• Cuckoo Hashing for Undergraduates, 2006, R. Pagh, 2006.
• Cuckoo Hashing, Theory and Practice (Part 1, Part 2 and Part 3), Michael Mitzenmacher, 2007.
• Шаблон:Cite conference

Примери

• Concurrent high-performance Cuckoo hashtable written in C++
• Cuckoo hash map written in C++
• Static cuckoo hashtable generator for C/C++
• Cuckoo hash table written in Haskell