Для каких типов данных используются операции хэш-таблицы O (1)?

18

Из ответов на (Когда) есть поиск в хэш-таблице O (1)? Я понимаю, что хеш-таблицы имеют О(1) наихудшее поведение, по крайней мере амортизированное, когда данные удовлетворяют определенным статистическим условиям, и существуют методы, которые помогут сделать эти условия широкими.

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

Итак, сделаем шаг: учитывая некоторые знания об источнике данных, как я могу определить, есть ли вероятность того, что хеш-таблица будет иметь О(1) операций, и, возможно, какие методы использовать в моей хэш-функции?

Жиль "ТАК - перестань быть злым"
источник
О, и хеш-таблицы в сравнении с бинарными деревьями связаны, но здесь я сосредоточусь на хеш-таблицах и когда они (или нет) в лучшем виде.
Жиль "ТАК - перестань быть злым"
Лучший случай для любой хэш-функции - это когда данные распределены равномерно.
0x0
@ Сунил: Не правда. Вы можете настроить хэш-функции.
Рафаэль
Я думаю, что этот вопрос слишком широк. В частности, можете ли вы конкретизировать, как будут выглядеть знания об источниках данных?
Рафаэль
@Raphael Например, если ключи являются строками: имена людей, имена файлов в каталоге, теги XML, хэши файлов,…
Жиль «ТАК - перестать быть злым»

Ответы:

4

Есть несколько методов, которые гарантируют, что для поиска всегда потребуются операции O (1), даже в худшем случае.

Как я могу определить, есть ли вероятность того, что хеш-таблица будет иметь операции O (1), и, возможно, какие методы использовать в моей хеш-функции?

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

После того, как вы выбрали какую-то конкретную хеш-функцию, вероятно, чрезмерно оптимистично предположить, что Мэллори никогда не узнает, какую хеш-функцию вы выбрали. Как только Мэллори обнаружит, какую хеш-функцию вы выбрали, если вы позволите Мэллори дать вам много данных для вставки в вашу хеш-таблицу с помощью этой хеш-функции, то вы обречены: Мэллори может внутренне быстро генерировать миллиарды элементов данных, хешировать их с помощью ваших хэш-функция, позволяющая определить, какие элементы данных могут столкнуться, а затем предоставить вам миллионы элементов данных «один на тысячу», которые могут столкнуться, что приводит к поискам, которые работают намного медленнее, чем O (1).

Все методы, которые гарантируют «O (1) поиск даже в худшем случае», позволяют избежать этой проблемы, выполняя небольшую дополнительную работу над каждой вставкой, чтобы гарантировать, что в будущем каждый возможный поиск может быть успешным за O (1) время. , В частности, мы предполагаем (в худшем случае), что Мэллори рано или поздно обнаружит, какую хеш-функцию мы используем; но он получает возможность вставить только несколько элементов данных, прежде чем мы выберем другую хеш-функцию - хеширование таблиц или какое-либо другое универсальное хеширование - которое мы специально выбираем таким образом, чтобы все данные, которые у нас есть, можно было найти в 2 или 3 зонда - т. е. O (1). Поскольку мы выбираем эту функцию случайным образом, мы можем быть уверены, что Мэллори не будет знать, какую функцию мы выбрали какое-то время. Даже если Мэллоринемедленно дает нам данные, которые, даже если эта новая хеш-функция сталкивается с предыдущими данными, затем мы можем выбрать еще одну свежую новую хеш-функцию, так что после перепрошивки все предыдущие данные, которые он и все остальные передали нам, теперь можно просматривать в 2 или 3 пробах в наихудшем случае - т.е. O (1) поисков в наихудшем случае.

Довольно просто случайным образом выбрать новую хеш-функцию и перефразировать всю таблицу достаточно часто, чтобы гарантировать, что каждый поиск всегда равен O (1). Хотя это гарантирует, что каждый поиск всегда равен O (1), эти методы при вставке N-го элемента в хеш-таблицу, которая уже содержит N-1 элементов, могут иногда требовать O (N) времени для этой вставки. Тем не менее, можно спроектировать систему так, чтобы, даже когда Мэллори преднамеренно предоставлял вам новые данные, которые с помощью новой хеш-функции сталкивались с предыдущими данными, система может принимать множество элементов от Мэллори и других, прежде чем ей потребуется выполнить полная O (N) перестройка. Методы хэширования, которые выбирают новую функцию и перефразируют, чтобы гарантировать O (1) поиск, даже в худшем случае, включают:

  • Хеширование кукушки гарантирует, что каждый поиск ключа завершится максимум с двумя вычислениями хеш-функции и двумя поисками таблиц.
  • Хеширование в классиках гарантирует, что каждый поиск ключа будет успешным после проверки небольшого числа последовательных записей в таблице (возможно, H = 32).
  • динамическое идеальное хеширование - статья Дитцфельбингера 1994 года - первая, которую я прочитал, в которой указывалось, что, хотя она и перефразирует «часто», чтобы гарантировать, что каждый поиск ключа всегда завершается успешно с 2 вычислениями хешей и 2 поисками, это возможно чтобы выполнить полную перефразировку настолько редко, что, хотя каждая полная перефразировка использует время O (n), ожидаемая средняя стоимость вставок и удалений амортизируется за O (1).

Структуры данных / Хеш-таблицы

Дэвид Кэри
источник
5

О(1)

Во-первых, мы даем первый детерминированный полиномиальный (по n) алгоритм построения линейного пространственного статического словаря с О(1)О(N2W)

О(журналN/журналжурналN)О(1)

В
источник
5

часa,б(Икс)знак равноaИкс+бмодификацияп ) и затем рассматривает поведение на входе в худшем случае для случайно выбранного члена семьи, когда противник не знает случайного выбора заранее. Это похоже на то, как анализируются рандомизированные алгоритмы: ожидание принимается по выбору алгоритма, а не по входному распределению.

В прошлом, согласно документу Usenix Кросби и Уоллаха , обычные языки программирования не делали ничего подобного, оставляя множество веб-приложений (и других серверов) открытыми для DoS-атаки, основанной на производственных коллизиях. (Работа написана в 2003 году, но она предполагает, что Дэн Бернштейн открыл ту же идею немного раньше.)

Быстрый поиск в Google позволяет утверждать, что современное состояние с точки зрения реализации улучшилось, а не улучшилось .

Еще одним отличием является то, что в мире с высокой пропускной способностью атаки по времени делают поиск столкновений в сети не таким сложным (в отличие от оффлайн, как предполагает ссылка Кросби-Уоллаха). Кажется, я помню, что Даниэль Головин несколько лет назад имел результаты по структурам данных, которые не уязвимы для временных атак, но я не знаю, широко ли они используются.

Луис
источник
0

Анализ среднего случая для хеш-таблиц сделан при обычном допущении однородности входных данных, которое однажды происходит из-за бритвы occam.

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

Разумеется, трудность связана с тем, что неоднородный анализ среднего случая трудно сделать. И ваши «знания» не могут быть удобно выражены как распределение, которое можно легко использовать в таком анализе.

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

улы
источник
8
Я должен не согласиться с первым предложением. Стандартное предположение состоит в том, что хеш-функция является случайной, а не входными данными. Предполагая, что равномерно распределенные данные толкают анализ в область фантастики, реальные данные никогда не бывают единообразными! Но есть методики учебника для того, чтобы сделать хеш-функции достаточно однородными. См. Универсальное хеширование и, в частности, табулирование хеширования .
Джефф
@JeffE Посмотрите на анализ среднего случая в ответе Рафаэля, который он формулирует это предположение об однородности. Вы не можете сделать анализ среднего случая без распределения. Вы должны выбрать один, и если не дано, бритва оккама предложит единый.
Uli
6
Конечно, у вас есть распределение; это распределение, которое вы используете для выбора хеш-функции. Выбор распределения для входных данных подобен поиску потерянных ключей под фонарным столбом; конечно, свет лучше, но это, вероятно, не там, где вы их уронили.
Джефф
@JeffE Вот как выполняется анализ среднего случая, выберите распределение и начните вычислять. Как всегда выбор дистрибутива является дискуссионным. Вы можете сделать неоднородный анализ среднего случая.
Uli
4
Да, я знаю, как это делается. (Проверьте мой профиль.) Если вы хотите, чтобы ваш анализ был прогнозирующим (а это весь смысл анализа), вы должны рандомизировать хеш-функцию. Тогда вы знаете точное распределение, потому что вы выбрали его.
Джефф