Comments 31
Однако спасибо автору за подобный разбор реализации
Да, Вы абсолютно правы. Есть много хороших и полных объяснений и доказательств корректности, именно поэтому в моей статье не слишком много подробных разъяснений, что же именно там творится, нет доказательства корректности и асимптотики. Но сам я не нашел реализации, которую можно прочитать и понять, как же это реализовано. Либо приводится голый код — который читать не просто, либо только объяснения, как же это должно быть в теории. Данная статья была рассчитана, как что-то среднее, ближе к реализации, информации которую сложно найти.
(печальное следствие: статью можно было не публиковать, важен только процесс написания).
сначала элемент s, потом s + t, затем s + 2*t
И остаток от деления на размер массива. Я, наверно, туплю, но вот скажем размер массива 8 элементов, а шаг получился 4. Мы же так будем всего в 2 ячейки тыкаться…
Ко второму комментарию. Мы специально храним количество deleted-элементов, и тогда, когда их слишком много, происходит рехеш — смена ключа. Также при заполнении таблицы на 75 процентов у нас происходит resize — увеличение таблицы, что тоже не позволяет переполниться нашей таблице. Но если бы мы такое не делали, да, все было бы именно так, как Вы сказали.
Дальше, если я правильно понял ваш код, то размер буфера у вас изначально 8 и увеличивается в 2 раза. Т.е. определённо не простые числа. Т.е. вы половину данных (навскидку) не используете в своём массиве.
Идём дальше, заполнение таблицы на 75% — по асимптоике получается, что пустой будет только каждый 4-ый элемент, т.е. мы должны в среднем перебрать 4 элемента, прежде чем попадём в дырку и есть ощущение, что на реальных данных всё может быть хуже.
Так мы переходим к следующему важному пункту: почему мы должны проходить в среднем 4 элемента? Если это так, то, либо у нас на вход дается один и тот же элемент(это происходит редко), либо у нас очень плохая хеш-функция. В идеале, используя двойное хеширование, она должна раскидывать элементы по абсолютно различным местам. То есть при идеальном хешировании ключ ни для каких двух элементов не будет совпадать. Но это все теоретические предположения. На практике у нас довольно неплохая хеш-функция, и она раскидывает большинство элементов, тем не менее, конечно, коллизии есть, это бесспорно.
Также я не совсем уверен, что правильно понял Ваш первый абзац, так что на всякий случай уточняю: мы ставим не в соседний элемент, а в элемент + (результат второй хеш-функции). Так даже, если мы попали одной хеш-функцией в одну и ту же ячейку, вторая хеш-функция раскидает эти два элемента по разным ячейкам.
пришёл элемент, первый хеш код у него 3, вставили в третью ячейку
пришёл другой элемент, неудачно, хешкод опять 3, второй 2, вставили в 5-ую ячейку
пришлёт трейтий элемент с хешкодом 5 — должны были вставить в 5-ую ячейку, но занято. Надо подбирать другую.
Чем больше занято в массиве, тем может быть тяжелее подбор и поиск.
Откуда 4 элемента — массив заполнен на 75%. Проверяем на существование какой-либо несуществующий элемент. С вероятностью 0.75 попадём в занятую ячейку. Пойдём перебирать дальше — опять попадём в занятую с вероятностью 0.75. И так далее. И тут я уже забыл тервер, чтобы прикинуть мат.ожидание количества попыток :) Может я неправ насчёт 4-х. Возможно меньше.
X = 1/4 * 1 + 3/4 * (1 + X)
1/4 * X = 1
X = 4
Т.е. нужно проверять и вести еще один признак — элемент в ячейке тут лежит потому что он тут должен лежать, или потому что он попал сюда по цепочке?
Все это в результате приводит к тому, что с некоторой долей вероятности значение хеша это всего лишь отправная точка, а отнюдь не индекс элемента в таблице.
Это первый момент. Второй момент — вычисление «хорошей» хешфункции может быть достаточно ресурсозатратным делом. и само по себе снижать производительность.
Третий момент — периодический рехеш. Тоже снижает производительность.
По сумме всего сказанного — а не проще использовать некоторые динамические структуры типа индексированных списков? Например, алгоритм SkipList? Не будет он быстрее того, что Вы описываете?
Так что (если хэш достаточно «хороший» – т.е. можно считать, что элементам присвоены случайные значения) всё определяется вероятностями, и при занятости таблицы 50% (вполне разумное требование) в среднем будем находить место со второй попытки. Ну или с 4 при 75%, но это уже не резонно (всегда можно уменьшить таблицу, храня в ней не сами объекты, а указатели на них).
Вот если хэш «плохой» – то тут сломается любая реализация хэш-таблиц.
Так вот, на рандомных данных, среднее плохое, но жить можно, но есть очень длинный хвост мерзости. Т.е. некоторые несуществующие элементы никак не могут попать в свободную ячейку. Т.е. в хорошем, плотном сете из 1000 элементов можно получить 854 итерации на поиск.
Так что, очень аккуратно следует использовать данную схему.
С заполнением .5 — уже 15/1.8
Какое у вас заполнение по факту было? Сомневаюсь, что с таким заполнением вы со второй попытки всё угадываете. Всё-таки терверы говорят про 4.
Я немного поменял заполняемость — поставил 70% (на 1024 элемента). В результате и впрямь испортилось, но не так сильно. Но тем не менее у меня максимум — 12 итераций, среднее 3.24
Проверил на различных числах — вот тогда все отлично. Как только начинаются повторы — тогда все ухудшается. То есть как результат: хранение различных данных — великолепно, при схожих происходит ухудшение.
Но тем не менее асимптотика O(1)...
Бесспорно, тервер не врет :)
В общем, чуть поигрался — вариант с цепочками в худших случаях значительно опережает данный. Но памяти жрёт гораздо больше, т.е. можно компенсировать проблемы уменьшением FillFactor.
Если дойдут руки, попробую заюзать на реальной задаче, где огромное количество сетов используется, посмотрю на использование памяти и скорость.
Спасибо что подтолкнули меня заняться задачей, которую откладываю уже несколько месяцев :)
Как так – "проверить, что не 0"? Там же есть условие – хэш взаимно простой с размером таблицы. Т.е. если размер – степень двойки, то хэш должен быть нечётным. Считаете его любым методом, дальше *2+1.
Если не эта ошибка – значит, просто "плохой" хэш.
Т.е. явно добавляют единичку
Не "полагаться на", а "сделать так, чтобы".
Например, (hash*2+1)%size, если size – степень двойки. Или упомянутая вами формула – если size простое число.
Лучше не выпендриваться и брать size степень двойки, так проще (и удваивать размер при rehash удобно).
Говоря о производиетльности — имеет смысл поднять служебные поля на уровень основного массива, чтобы для обращения за ними не надо было бы разыменовывать указатель. Правда, при этом увеличится расход памяти. Мне было бы любопытно рассмотреть последствия в конкретных числах, а вам?
Здравствуйте! Приятно слышать. Безусловно, с Вашими доработками код бы выглядел "сжатее" и более по C++. Но как и написано в начале статьи, эта реализация была предназначена для понимания реализации того, что происходит в хеш-таблицах. Боюсь, написание через умные указатели, добавление вектора может немного уменьшить понимаемость кода для тех, кому эта статья может помочь. А знающие программисты могут прочитать статью и вспомнить молодость :).
Вчера вечером проверил таблицу на производительность, получил слишком уж хороший результат — но было занятно посмотреть, что теория сходится с практикой. Наверное, также попробую с Вашими улучшениями и посмотрю на время выполнения, а не на количество итераций. Думаю, будет очень занятно. Может, сделаю в этой статье PS, а не, как рассчитывал, еще одну статью, все-таки не хватит материала)
Подскажите, пожалуйста, что Вы можете порекомендовать для проверки использования памяти? Пытался найти, но никак не получалось.
При этом еще попытаться отследить как часто происходит рехеш и сколько времени он занимает.
В целом — оценить минимальное время добавления/удаления/поиска элемента на последних 100 000 операциях, максимальные времена и среднее. И сделать, скажем, 5 прогонов.
В функции HashFunctionHorner ошибка. В условии окончания цикла надо i != s.size()
, а не s[i] != s.size()
.
Хеш-таблицы