Cuckoo hashing, или о чём не написал Д.Кнут

Мой любимый раздел в «искусстве..» (http://en.wikipedia.org/wiki/The_Art_of_Computer_Programming)- сортировка и поиск; если точнее, то хеши. C 1973 года пор прошло ужасно много лет, но книга до сих пор остаётся актуальной. Речь впрочем не про неё, а про хеши.

У хешей масса замечательных свойств; больше всего радует практически гарантированный O(1) при поиске. Но есть и недостатки. Например типичный поиск это цикл, да и O(1) гарантирован только в случае идеальной хеш функции,а при 50-70% наполнении таблицы начинает тормозить.

С 1973 года много чего изменилось. В 2001 умные люди придумали Cuckoo hashing (оно же splash tables). Попробую на пальцах перепеть Бетховена

Каждому элементу соответствуют две хеш-функции, по которым выбираются две разных позиции. При добавлении, если хотя бы одна из позиций пустая, то добваляем по этой позиции. Если обе позиции заняты, то выбираем одну из них случайным образом, старое значение «выкидываем», и вместо него добавляем новое; старое значение после этого добавляем заново.

Зачем всё это надо?
1. Поиск при этом перестаёт быть циклом.
2. В поиске нет условий, только сравнения.
3. Поиск гарантирован за O(1).
4. Качество хеш-функции больше не влияет на поиск, только на добавление.
5. Добавление сходится как O(1 + 1/ackerman(N)), т-е на практике тоже очень быстро.
6. SSE. Считать две хеш-функции можно параллельно.
7. Можно осмысленно префетчить.

Дальше чтиво

http://en.wikipedia.org/wiki/Cuckoo_hashing

Мораль: пора переписывать шаблоны в движках.

  • IronPeter

    Хм… Ну если смотреть поверхностно, то эта технология ниппель может иметь бесконечные циклы, которые зависят от ортогональности данных и хеш-функций. Аккерман – это прекрасно конечно. Но наверняка при условии слабой заполненности таблицы. Асимпотика у тебя по чему? Есть два параметра – размер хеш таблицы и число данных. Данные случайно и независимо распределены относительно хеш функций?

    Впрочем конечно крутая техника. Не знал. То что индирекций в поиске нету – тоже хорошо.

    Я знаю простой хеш без индирекции, когда мы кладем элемент в первую свободную ячейку после хеш-значения.

  • look4awhile

    “первая свободная ячейка после хеш значения” – это цикл. а тут нет цикла. внутрь SSE-loop-а можно пихать.

    про циклы видимо надо подробнее написать. напишу погодя

  • IronPeter

    Да не, ясно что очень круто… Это я со злобы, что не знал трюка.

    Для статических хешей очень может неплохо пойти. Всяких XML загрузок полей класса… Пейсня.

  • IronPeter

    Кста, сдается мне, что немного лукавишь.

    Берусь реализовать тот же поиск в “первой свободной ячейке после значения” на SPU. Широкими проходами такими – налево которых нашли, направо которых не нашли. А потом проход по правому буферку.

    Если есть желание зафигачить цикл – его таки можно зафигачить. Но теоретично, сферично и в вакууме.

    Прогоняю сейчас в памяти весь код, который писал за год – хуй там поиск в хешах в “SSE loop”ах. Самый крутой хеш от строки не спасет тебя от того, что в случае попадания в ячейку надо сравнить две строчки. Вот он, цикл.

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

  • look4awhile

    одинаковые можно ассертить

    а у меня этот хеш всплыл в коллизиях. т-е там регулярная сетка, и есть пустые и не пустые тайлы. остальное очевидно…

  • CEMEH

    Прикольно. Условия появятся при добавлении, ага?

    И про префетч можно подробнее?…

  • look4awhile

    про префетч всё вообщем-то очевидно
    можно считать вторую ф-цию и\или префетчить второе значение, пока префетчится первое значение

  • CEMEH

    А, я думал более далекий префетч как-то…
    Тут проверка скорее всего будет быстрая, префетч не успеется.

  • http://plakhov.livejournal.com Finder

    У меня бессодержательный комментарий.
    Просто хочу свой респект засвидетельствовать.
    Афтар пиши еще.

  • http://zeux.livejournal.com/ Zeux

    Саймон, насколько я понимаю, можно так:

    int hash1 = computeHash1(key);
    prefetch(table + hash1);

    int hash2 = computeHash2(key);
    if (table[hash2].key == key) { return table[hash2].value; }

    return (table[hash1].key == key) ? table[hash1].value : NULL;

  • Dmitry Tyurev

    Ни разу не сталкивался со случаем, чтобы тормозило и именно из-за хэша. :)

  • look4awhile

    вопрос не в тормозило. вопрос в использовании ресурса.
    т-е есть ресурс делать более мелкое дробление хешем.
    например использовать вместо kdtree в коллизиях – заменив регулярной сеткой, и прохешировав тайлы. итд итп.

  • CEMEH

    Zeux, ну один из пойнтов, что на SSE можно пару за раз вычислять.
    И вообще, цена загрузки памяти – 200 тактов. Чтобы эффективно префетчить, надо что-то на эти 200 тактов делать. Даже вычисление хеша и сравнение не тянет, на первый взгляд.
    Хотя лучше чем ничего конечно.