До сих пор я знал только два принципиально различных способа разрешения коллизий, оба описаны в кормене. Разумеется это разрешающие цепочки и двойное хеширование.
Читал немного про perfect hashing, но то что следует ниже придумал час назад.
Итак, мы хотим положить в хеш таблицу n заранее известных объектов. А потом спрашивать её, содержит ли она такой объект. Предлагается завести массив размера n значениями которого могут быть объекты или null. И второй массив, где i-тый элемент равен true, если в этой ячейке есть коллизия, либо false в противном случае. Без особого матана, я численно прикинул, что порядка 1 / exp(1.0) (1/2.71828…) объектов должны с кем-то образовать коллизию. Для этой части объектов заведем подобную хеш-таблицу рекурсивно. Когда у нас осталось n < K объектов, для построения хеш-таблицы, мы просто применяем линейный поиск по списку. Ну или бинарный поиск, значение K фиксированное, и может быть выбрано оптимально исходя из практики тестирования.
Понятно, что если в первом массиве мы нашли null по хешу, то такого объекта нет, если там какой-то объект есть, то смотрим совпали ли мы с ним, если нет, продолжаем искать в хеш-таблице следующего уровня, которая в 1 / exp(1.0) раз меньше исходной.
Хеш-функции на разных уровнях могут отличаться.
Худшая оценка сложности Ln(n), где Ln – это натуральный логарифм, логарифм по основанию числа e = exp(1.0) ~ 2.71828…, число эйлера. Средняя оценка сложности 1 / (1 – 1 / e) = 1.5819
Прерасход памяти, составит те же 1.5819 (указателей), если мы считаем что в первом массиве хранятся указатели, плюс битовый массив для второго массива, но это проценты. В обычной хеш-таблице с разрешающими цепочками мы используем по одному указателю для самой таблицы, плюс по одному указателю для каждого находящегося в ней объекта (для поля next) т.е в общей сложности примерно 2 указателя на объект.
Вопрос: известен ли вам этот велосипед или ему подобный?
Знаете ли вы принципиально иные способы разрешения коллизий, чем два предложенные в кормене?
PS: Я мог где-то напортачить с оценками, если вам интересно и вы сами посчитаете, буду рад поправкам, замечаниям.
Приведенная оценка для худшего случая является матожиданием максимального количества шагов поиска для наперед выбранного элемента. В маловероятном худшем случае процесс построения таблицы зациклится, если на каком-то шаге с n >= K элементами все элементы будут иметь одно хеш-значение. Проблему можно решить выбором другой хеш-функции и попыткой построения хеш-таблицы снова. Стоит отметить, что вероятность данного события стремительно убывает с ростом K, так что на скорость работы это слабо повлияет. Но при этом повлияет на сложность реализации. Поэтому предлагаю: - точно посчитать матожидание количества шагов для поиска случайно выбранного элемента. - сравнить скорость работы на практике с методами, приведенными в Кормене.
Немного потестировал для поиска 64-х битных чисел. Получилось процентов на 10 медленнее чем обычный хеш сет. Хеш сет применяет операцию взятия остатка от деления — %, вариант с
hash_pos = val & 0xFFFбыстрее обоих по понятным причинам. Это кстати особый случай, здесь нам не нужны указатели. Вместо null используем любое не встречающееся число. По памяти получаетсяn * sizeof(ui64) * 1.5819 + O(log(n)), а для обычной хеш таблицы выходитn * (sizeof(ui64) + 2 * sizeof(int*))UPD: тестировал только время поиска, без времени построения таблицы.
По поводу иных способов разрешения коллизий — есть любопытное Хеширование кукушки (Cuckoo hashing).
Что касается эффективности, то по-видимому самый известный и простой способ — связывание конфликтующих элементов в список — оказывается на практике лучшим. Можно уменьшить затраты по памяти, заменив списки на какие-нибудь хитрые массивчики. Если хочется сравнивать различные методы по скорости, то лучше подогнать параметры так, чтобы структуры занимали примерно одинаковую память — так будет честнее. Параметром является, например, число ячеек в таблице, которое может быть не равно числу элементов.
Еще пара замечаний по поводу сравнения структур. 1) Для честности надо подставлять быстрый аллокатор. Количество выделений памяти в обычном unordered_set скорее всего большое, а у тебя выделяются лишь несколько раз большие куски. 2) Лучше сравнивать мапы, а не сеты. Они значительно чаще встречаются на практике. В шарпе, например, сеты появились лишь недавно. Впрочем, замена сета на мапу скажется лишь на размере ключа. Предлагаю считать ее равной двум указателям.
Так вроде способ с "open address" как раз и есть "хитрые массивчики" — точнее один массив ведь на всё получается, и на таблицу и на цепочки. Да только при высокой загрузке скорость у них удручающей в сравнении оказывается — а значит таблицу желательно держать достаточно разреженной... в то время как со списками можно хоть каждую ячейку забить почти без изменений в скорости... вот тебе и сэкономили память.
Гм... зря я синюшный в разговоры мудрых сунулся, звиняйте :)
Наверное имелось в виду списки заменить на массивчики. Например есть такой подход, хранить в элементе списка несколько объектов, их количество, указатель на следующий. т.е. вместо
struct TListNode {TKey key; TListNode* next};завести что-то вродеstruct TListNode {int keysCount; TKey keys[8]; TListNode* next};Но при низкой заполненности таблицы этот подход малоэффективен и жрёт непомерно много памяти.Имелось в виду примерно такое. 0 элементов — просто храним пустой указатель. 1 элемент — храним указатель на массив ровно из одного элемента. 2 элемента — храним указетель на массив ровно из двух элеменов. ..... Много элементов — храним указатель на обычный вектор или на еще что-нибудь. Распределение Пуассона говорит, что много элементов бывает редко :)
Еще надо где-то хранить количество элементов, конечно. Можно в отдельном массивчике, лучше битово. Ведь это количество невелико.
При каждом добавлении элемента придется копировать в новую память все ранее добавленные. Но так как количество элементов невелико, это не займет много времени. Выделять память надо быстро, конечно. Это нетрудно сделать, ибо есть небольшой набор возможных размеров для выделения.
Ну так если мы юзаем саму таблицу и для таблицы и для цепочек, то нам и выделять ничего не надо, и с количеством элементов в цепочке возиться не нужно... и вообще сплошная пруха. а в таблице с массивчиками вместо нормальных списков всё равно пустые ячейки хранить придётся и до нуля избыточность не снизить.
Избыточность по памяти никак не получится снизить, не потеряв O(1) во времени. Хотя строго сформулировать это утверждение довольно сложно.
Если вы пытаетесь прорекламировать открытую адресацию, то напрасно :) Она хорошо работает лишь на искусственных примерах. Например, надо обязательно требовать, чтобы размер ключа был малым. Не понимаю, зачем этому алгоритму столько места в учебниках уделяют.
Не, не пытаюсь рекламировать. Просто вспомнил. А почему размер ключа должен быть малым? Я туплю что-то?
Недостаток у неё основной один вроде в отличие от остальных — loadFactor больше единицы не сделать, да и с близким к единице уныло работает :)
Размер пустой ячейки в случае цепочек — sizeof(void*), в случае открытой адресации — sizeof(Key). Если ключи большие, это печально.
Еще требуется вводить понятие "пустой ключ" для произвольного типа. Хотя наверное это проблема только для C++ — во многих других языках все объекты являются указателями.
Не очень согласен что sizeOf(key) — нам же key не нужно хранить. можно хранить указатели и при поиске просто бежать по ячейкам и проверять ключи висящих на указателях элементов. Как только хэш очередного ключа сменился — цепочка кончилась. пустая ячейка — Null...
UPD: Туплю конечно, мы же в объекте сам ключ не храним обычно. Это я с сетом уже путаю. Очень извиняюсь. Впрочем указатели на врапперы типа Map.Entry можно хранить без проблем. А... с врапперами тогда уж и обычные списки можно было сделать.
Хеширование кукушки асимптотически быстрее всех, потому что удаление и поиск работают за O(1) гарантированно, в то время как вставка за O(1) в среднем. Но если посмотреть на результаты тестов, проведенных авторами этого метода, то видно, что на практике оно все-таки проигрывает цепочкам. Вообще же, фильтр Блума очень хорошо ускоряет любую структуру данных для поиска, и пишется просто. В принципе с ним и стандартный map вполне быстро работает.