Pull to refresh

Comments 31

Слабо верится что в интернете не найдется хороших объяснений хеш-таблиц. Ради интереса погуглил и на первых же страницах нашлось множество блогов и статей на эту тему, в том числе с хорошими картинками, помогающими понять как все утроено внутри.
Однако спасибо автору за подобный разбор реализации

Да, Вы абсолютно правы. Есть много хороших и полных объяснений и доказательств корректности, именно поэтому в моей статье не слишком много подробных разъяснений, что же именно там творится, нет доказательства корректности и асимптотики. Но сам я не нашел реализации, которую можно прочитать и понять, как же это реализовано. Либо приводится голый код — который читать не просто, либо только объяснения, как же это должно быть в теории. Данная статья была рассчитана, как что-то среднее, ближе к реализации, информации которую сложно найти.

Э… Неоднократно попадались объяснения не хуже вашего. Думаю, вам тоже, так что можно предположить, что ваше объяснение вам более понятно именно потому, что его написали вы сами. Классический эффект – чтобы что-то как следует понять, надо это объяснить кому-то.
(печальное следствие: статью можно было не публиковать, важен только процесс написания).
Для начала надо было дать определение термину «хэш». Перечислить его свойства, особенности применения и недостатки.
Возможно, от этого статья стала бы полнее, но для понимания хеш-таблиц, или их реализации, это необязательно, мне не хотелось грузить читателей дополнительными терминами и темами, если без них можно обойтись.
сначала элемент s, потом s + t, затем s + 2*t

И остаток от деления на размер массива. Я, наверно, туплю, но вот скажем размер массива 8 элементов, а шаг получился 4. Мы же так будем всего в 2 ячейки тыкаться…

Да, все верно. Именно поэтому значение хеш-функции (обеих) должно быть взаимопросто с размером массива.

Почему обеих? Только второй же.

Ну да, достаточно требовать только для второй, правильно. Можно про запас требовать и для первой. Но Вы правы, достаточно только для второй

А можно подробнее про двойное хеширование? Стоит ли игра свеч? Если я правильно понял, то оно в целом ухудшает производительность. Т.е. группа нехороших элементов может загадить собой данные так, что нормальные элементы будут долго искать подходящую дырочку в массиве. Есть какие-то измерения?
И если я ещё правильно понял код, то при сильно заполненной таблице поиск несуществующего элемента вырождается в O(n) — т.к. будем перебирать почти все элементы, пока не переберём все или случайно попадём в null.
Что правда, то правда. Тут то же самое, что и с быстрой сортировкой и со многими другими алгоритмами. И, как и в quicksort может быть n*n, так и тут на специальных данных асимптотика может вырождаться в n. Но на обычных данных и со специально подогнанной хеш-функцией все будет хорошо. Что касается ухудшения, не совсем понял. Проблему коллизии надо как-то решать. В стандартной библиотеке используется метод цепочек, а значит, он, наверное, в среднем эффективнее. Но тем не менее метод двойного хеширования имеет вполне себе шанс на существование. Каких-то данных нет, но идея интересная, может, на днях опубликую продолжение данной статьи с исследованием времени работы.

Ко второму комментарию. Мы специально храним количество deleted-элементов, и тогда, когда их слишком много, происходит рехеш — смена ключа. Также при заполнении таблицы на 75 процентов у нас происходит resize — увеличение таблицы, что тоже не позволяет переполниться нашей таблице. Но если бы мы такое не делали, да, все было бы именно так, как Вы сказали.
Метод цепочек достаточно эффективный, ценой увеличения потребления памяти, да. Вопрос в том, насколько к реальности проблемный/беспроблемный метод двойного хеширования. Пока ощущения, что в идеальных случаях он очень хорош, но в случае проблем начинает быстро деградировать (попали в коллизию, закинули в сосденюю ячейку этот элемент, приходит нормальный элемент и попадает в эту же ячейку, получается вынужденная коллизия и ищется место уже для этого элемента). Также, рехеш не быстрая операция, и хотелось бы производить её пореже.

Дальше, если я правильно понял ваш код, то размер буфера у вас изначально 8 и увеличивается в 2 раза. Т.е. определённо не простые числа. Т.е. вы половину данных (навскидку) не используете в своём массиве.

Идём дальше, заполнение таблицы на 75% — по асимптоике получается, что пустой будет только каждый 4-ый элемент, т.е. мы должны в среднем перебрать 4 элемента, прежде чем попадём в дырку и есть ощущение, что на реальных данных всё может быть хуже.
В общем да, Вы абсолютно правы. Но в основном мы знаем, какие данные к нам приходят, ну или догадываемся. Тогда мы можем настроить наши хеш-функции, к примеру для строк мы можем использовать частоту использования разных букв в тексте и тд.

Так мы переходим к следующему важному пункту: почему мы должны проходить в среднем 4 элемента? Если это так, то, либо у нас на вход дается один и тот же элемент(это происходит редко), либо у нас очень плохая хеш-функция. В идеале, используя двойное хеширование, она должна раскидывать элементы по абсолютно различным местам. То есть при идеальном хешировании ключ ни для каких двух элементов не будет совпадать. Но это все теоретические предположения. На практике у нас довольно неплохая хеш-функция, и она раскидывает большинство элементов, тем не менее, конечно, коллизии есть, это бесспорно.

Также я не совсем уверен, что правильно понял Ваш первый абзац, так что на всякий случай уточняю: мы ставим не в соседний элемент, а в элемент + (результат второй хеш-функции). Так даже, если мы попали одной хеш-функцией в одну и ту же ячейку, вторая хеш-функция раскидает эти два элемента по разным ячейкам.
Проблема в том, что при наличии коллизий, мы начинаем расскидывать в разные ячейки. Но проблема в том, что эти «другие» ячейки уже «зарезервированы» под другие значения. Т.е. упрощённый пример, пусть будет массив из 7 элементов для простоты.
пришёл элемент, первый хеш код у него 3, вставили в третью ячейку
пришёл другой элемент, неудачно, хешкод опять 3, второй 2, вставили в 5-ую ячейку
пришлёт трейтий элемент с хешкодом 5 — должны были вставить в 5-ую ячейку, но занято. Надо подбирать другую.
Чем больше занято в массиве, тем может быть тяжелее подбор и поиск.

Откуда 4 элемента — массив заполнен на 75%. Проверяем на существование какой-либо несуществующий элемент. С вероятностью 0.75 попадём в занятую ячейку. Пойдём перебирать дальше — опять попадём в занятую с вероятностью 0.75. И так далее. И тут я уже забыл тервер, чтобы прикинуть мат.ожидание количества попыток :) Может я неправ насчёт 4-х. Возможно меньше.
Вы правы насчёт 4-х: в этой схеме испытаний частота события и среднее время ожидания события — величины взаимно обратные (1/4 и 4). Как это проверить? Можно повозиться с простой алгеброй (считать суммы арифметических прогрессий), но можно поступить проще. Давайте назовём искомую величину — среднее количество проверок, включая последнюю, успешную проверку — X. При первой проверке с вероятностью 1/4 мы имеем количество проверок 1 (удача при первой попытке!) и с оставшейся вероятностью 3/4 мы имеем количество проверок 1 (неудача при первой попытке) плюс X (ситуация после первой попытки ровно такая же!):

X = 1/4 * 1 + 3/4 * (1 + X)

1/4 * X = 1

X = 4
Кстати, да. В приведенном выше примере — два элемента с хешем 3 заняли ячейки 3 и 5. А затем нас спрашивают — а есть в таблице элемент с хешем 5? А его нет, хотя ячейка с хешем 5 занята элементом с хешем 3…

Т.е. нужно проверять и вести еще один признак — элемент в ячейке тут лежит потому что он тут должен лежать, или потому что он попал сюда по цепочке?

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

Это первый момент. Второй момент — вычисление «хорошей» хешфункции может быть достаточно ресурсозатратным делом. и само по себе снижать производительность.

Третий момент — периодический рехеш. Тоже снижает производительность.

По сумме всего сказанного — а не проще использовать некоторые динамические структуры типа индексированных списков? Например, алгоритм SkipList? Не будет он быстрее того, что Вы описываете?
Для «нормального» элемента несущественно, почему занята его ячейка – уже попался элемент с тем же значением хэша или там лежит вытесненный.
Так что (если хэш достаточно «хороший» – т.е. можно считать, что элементам присвоены случайные значения) всё определяется вероятностями, и при занятости таблицы 50% (вполне разумное требование) в среднем будем находить место со второй попытки. Ну или с 4 при 75%, но это уже не резонно (всегда можно уменьшить таблицу, храня в ней не сами объекты, а указатели на них).

Вот если хэш «плохой» – то тут сломается любая реализация хэш-таблиц.
В общем, написал свою реализацию на потестить. Может где-то наврал, да и в качестве второго хеша заюзал xor (чтобы сбить линейность, но может не сбивается). В общем, если что, то второй хеш надо бы проверить что не 0, иначе могут быть проблемы.
Так вот, на рандомных данных, среднее плохое, но жить можно, но есть очень длинный хвост мерзости. Т.е. некоторые несуществующие элементы никак не могут попать в свободную ячейку. Т.е. в хорошем, плотном сете из 1000 элементов можно получить 854 итерации на поиск.
Так что, очень аккуратно следует использовать данную схему.
Очень поразил Ваш результат. Решил сам проверить, посмотреть что получится. Для упрощения генерации тестов взял целые числа. Использовал я самое простое хеширование и ту же самую реализацию, приведенную в статье. У меня все операции выполнялись с первой итерации. В 13ти случаях из ста — за две итерации. Так что либо я что-то не понимаю, может на целых числах неправильно проверять, либо что-то не так в Вашей реализации, может что-то не чистите…
Чуть поигрался с хешами, результаты стали лучше. На 1000 с заполнением .75 худшее попадание за 25 попыток, в среднем — 3.2
С заполнением .5 — уже 15/1.8
Какое у вас заполнение по факту было? Сомневаюсь, что с таким заполнением вы со второй попытки всё угадываете. Всё-таки терверы говорят про 4.

Я немного поменял заполняемость — поставил 70% (на 1024 элемента). В результате и впрямь испортилось, но не так сильно. Но тем не менее у меня максимум — 12 итераций, среднее 3.24


Проверил на различных числах — вот тогда все отлично. Как только начинаются повторы — тогда все ухудшается. То есть как результат: хранение различных данных — великолепно, при схожих происходит ухудшение.
Но тем не менее асимптотика O(1)...


Бесспорно, тервер не врет :)

Асимптотика — да. Но математиков к программированию допускать всё-таки не стоит. Ибо асимптотически у них всё идеально, а в реальности…
В общем, чуть поигрался — вариант с цепочками в худших случаях значительно опережает данный. Но памяти жрёт гораздо больше, т.е. можно компенсировать проблемы уменьшением FillFactor.

Если дойдут руки, попробую заюзать на реальной задаче, где огромное количество сетов используется, посмотрю на использование памяти и скорость.
Спасибо что подтолкнули меня заняться задачей, которую откладываю уже несколько месяцев :)

Как так – "проверить, что не 0"? Там же есть условие – хэш взаимно простой с размером таблицы. Т.е. если размер – степень двойки, то хэш должен быть нечётным. Считаете его любым методом, дальше *2+1.


Если не эта ошибка – значит, просто "плохой" хэш.

А если размер не степень двойки? Мне сейчас тяжело продумывать пример, но это очень неправильное поведение полностью полагаться на значения хеша. Может тут и прокатит, но шаг влево, шаг вправо и хеш станет 0, и мы будем бегать по одному элементу. Обычно в статьях рекомендуют код вида 1 + (hash % (size — 1)).
Т.е. явно добавляют единичку

Не "полагаться на", а "сделать так, чтобы".
Например, (hash*2+1)%size, если size – степень двойки. Или упомянутая вами формула – если size простое число.


Лучше не выпендриваться и брать size степень двойки, так проще (и удваивать размер при rehash удобно).

Да понял условия. Степень двойки недолюбливаю, т.к. повышенный расход памяти. И если с простым числом можно порость хеш ужаться (типа мы добавили всё и сейчас будем только проверять, то со степенью двойки это не получится). Но в целом проще да, и, возможно, меньше коллизий.
Спасибо, было интересно почитать. Вам интересно было бы немного поитерировать над получившимся кодом? В первую очередь я бы предложил избавиться от C-style вызовов new и delete, используя, скажем, std::vector вместо C массивов и std::owning_ptr вместо C указателей на Node. Объём вашего кода сократится: например, вам не нужно будет кодировать HashTable::~HashTable, компилятор прекрасно справится сам с этой задачей (HashTable::HashTable тоже сократится благодаря дефолтовому конструктору std::owning_ptr, вызовы которого сгенерирует компилятор). Аналогично, сократятся Resize и Rehash, каждый на несколько строк в конце (автоматический вызов деструктора локального std::vector-а, свопнутого с основным, позаботится об освобождении памяти). Код будет не только короче, но и дешевле в долговременной поддержке. Производительность не должна измениться.

Говоря о производиетльности — имеет смысл поднять служебные поля на уровень основного массива, чтобы для обращения за ними не надо было бы разыменовывать указатель. Правда, при этом увеличится расход памяти. Мне было бы любопытно рассмотреть последствия в конкретных числах, а вам?

Здравствуйте! Приятно слышать. Безусловно, с Вашими доработками код бы выглядел "сжатее" и более по C++. Но как и написано в начале статьи, эта реализация была предназначена для понимания реализации того, что происходит в хеш-таблицах. Боюсь, написание через умные указатели, добавление вектора может немного уменьшить понимаемость кода для тех, кому эта статья может помочь. А знающие программисты могут прочитать статью и вспомнить молодость :).


Вчера вечером проверил таблицу на производительность, получил слишком уж хороший результат — но было занятно посмотреть, что теория сходится с практикой. Наверное, также попробую с Вашими улучшениями и посмотрю на время выполнения, а не на количество итераций. Думаю, будет очень занятно. Может, сделаю в этой статье PS, а не, как рассчитывал, еще одну статью, все-таки не хватит материала)


Подскажите, пожалуйста, что Вы можете порекомендовать для проверки использования памяти? Пытался найти, но никак не получалось.

Я бы рекомендовал оценивать производительность по набору от 1 000 000 элементов и выше. И элементы должны быть достаточно похожими. Ну, скажем, генератор неповторяющихся цифро-буквенных последовательностей длиной 10-20 байт.

При этом еще попытаться отследить как часто происходит рехеш и сколько времени он занимает.

В целом — оценить минимальное время добавления/удаления/поиска элемента на последних 100 000 операциях, максимальные времена и среднее. И сделать, скажем, 5 прогонов.
Sign up to leave a comment.

Articles