Из ответов на (Когда) есть поиск в хэш-таблице 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) поиск, даже в худшем случае, включают:
Структуры данных / Хеш-таблицы
источник
источник
В прошлом, согласно документу Usenix Кросби и Уоллаха , обычные языки программирования не делали ничего подобного, оставляя множество веб-приложений (и других серверов) открытыми для DoS-атаки, основанной на производственных коллизиях. (Работа написана в 2003 году, но она предполагает, что Дэн Бернштейн открыл ту же идею немного раньше.)
Быстрый поиск в Google позволяет утверждать, что современное состояние с точки зрения реализации улучшилось, а не улучшилось .
Еще одним отличием является то, что в мире с высокой пропускной способностью атаки по времени делают поиск столкновений в сети не таким сложным (в отличие от оффлайн, как предполагает ссылка Кросби-Уоллаха). Кажется, я помню, что Даниэль Головин несколько лет назад имел результаты по структурам данных, которые не уязвимы для временных атак, но я не знаю, широко ли они используются.
источник
Анализ среднего случая для хеш-таблиц сделан при обычном допущении однородности входных данных, которое однажды происходит из-за бритвы occam.
Если у вас есть дополнительные знания о домене и распределении ключей, вы можете взять тот же самый анализ среднего случая и заменить равномерное распределение вашим распределением и пересчитать ожидания, по крайней мере, в теории.
Разумеется, трудность связана с тем, что неоднородный анализ среднего случая трудно сделать. И ваши «знания» не могут быть удобно выражены как распределение, которое можно легко использовать в таком анализе.
Очевидно, что проще всего делать симуляции. Реализуйте хеш-таблицы и наблюдайте, как они работают для вашего типичного набора входных данных.
источник
источник