procedure insert(x)
if lookup(x) then return
loop MaxLoop times
if T1[h1(x)] = ⊥ then { T1[h1(x)] ← x; return }
x ↔ T1[h1(x)]
if T2[h2(x)] = ⊥ then { T2[h2(x)] ← x; return }
x ↔ T2[h2(x)]
end loop
rehash(); insert(x)
end
Cuckoo hashing
Некоторое время назад, ознакомился со статейкой Cuckoo hashing и сопутствующими ссылками. Заинтересовался настолько, что стал задумываться о рефакторинге своего memory manager'а (одного из...). Если кто сталкивался с реализацией подобного хеша, то есть такой вопрос: действительно ли, такой хеш существенно быстрее std::hash_map при сильной фрагментации памяти? Никто не сравнивал? А то писанины много (в моём случае), а целесообразность под вопросом.
Цитата: Lerkin
Если кто сталкивался с реализацией подобного хеша, то есть такой вопрос: действительно ли, такой хеш существенно быстрее std::hash_map при сильной фрагментации памяти?
Ну учитывая что стандартного такого контейненра нет, а бывают собственные реализации у разных компиляторов с совсем разными хэшами, то сравнивать с ним в общем случае как то странно. В смысле конкретику надо. )
На сколько я понял там поиск константный при довольно дорогой вставке. Как всегда все зависит от того где сие испоользуется. А по поводу фрагментации в std::hash_map это обычно массив списков для разрешения коллизий, а в Cuckoo это два массива, естественно при граничных условиях (множественные коллизии + разбросанные по памяти узлы списков + довольно частое вытягивание различных хешированных значений) списки будут проседать.
PS: Аналогично, хотелось бы увидеть оценку работы сего в реальном приложении.
PS: Аналогично, хотелось бы увидеть оценку работы сего в реальном приложении.
Цитата: Ramon
На сколько я понял там поиск константный при довольно дорогой вставке.
Ну насколько я понимаю, дороогая вставка - это плохой случай, когда костантная вставка - должна быть основным случаем. Смущает непредсказуемость заранее времени вставки (вплоть до бесконечности =) )
Цитата: Ramon
а в Cuckoo это два массива
Почему два то?
Цитата: aks
Смущает непредсказуемость заранее времени вставки (вплоть до бесконечности =) )
Вот это вызывает основные опасения.
Цитата: aks
Почему два то?
Дык блин, вот Росс говорит что - два. А примеры приводит с построением 3-х splash tables. Хз, короче.
P.S. Есть сомнение, что нормальной оптимизации поддаётся только на Cell Power'е.
Цитата:
Ну насколько я понимаю, дороогая вставка - это плохой случай, когда костантная вставка - должна быть основным случаем. Смущает непредсказуемость заранее времени вставки (вплоть до бесконечности =) )
Код:
Как минимум до MaxLoop'а зависящего от кол-ва захешированного, а там еще есть rehash и рекурсивный insert, и до них в конце концов обязательно дойдет от потому и "дорой":D
Цитата:
Почему два то?
"The dictionary uses two hash tables, T1 and T2, each of length r, and
two hash functions h1, h2 : U → {0, . . . , r − 1}. Every key x ∈ S is stored
in cell h1(x) of T1 or h2(x) of T2, but never in both. Our lookup function
is"
Код:
function lookup(x)
return T1[h1(x)] = x ∨ T2[h2(x)] = x
end
return T1[h1(x)] = x ∨ T2[h2(x)] = x
end
PS: Цитаты и псевдокод из Rasmus Pagh and Flemming Friche Rodler: Cuckoo Hashing.
PS2: Конечно, как всегда, все очень сильно будет зависить от ф-ций хэширования, а по сему хотелось бы видеть практический резулт и естественно не на захэшированных днях недели.