HashDoS: как сложность Hashtable в худшем случае может быть O (n ^ 2)?

Таким образом, это утверждение просто подчеркивает важность использования хорошей хеш-функции. У хорошей хэш-функции больше шансов достичь амортизированного времени O(1), чем у более слабой хеш-функции; для первого только для очень небольшого числа входных данных хеш-таблица достигнет наихудшего случая O (n). - person Peter O.; 30.12.2011

@ПитерО. На самом деле здесь это не поможет. Злоумышленник заранее знает, какие данные отправлять для создания коллизий, поскольку у него есть доступ к указанным хеш-функциям/библиотекам, и отправляет данные, которые создают такие коллизии (в данном случае ключи для параметров POST). Реализация рандомизированного хэша не позволяет злоумышленнику предварительно вычислить этот список конфликтующих ключей, а ограничение количества разрешенных ключей смягчает крайние n^2. - person ; 30.12.2011

@MikeNakis: В этом случае это проблема, которую не может решить никакая хеш-функция: хэш-коллизии неизбежны для любого хэш-кода конечной длины. - person Peter O.; 30.12.2011

@ПитерО. Проблема может быть решена путем введения магического числа, которое хешируемые объекты включают в свои вычисления хэш-кода, так что каждый веб-сайт будет иметь другое секретное магическое число, что не позволит постороннему придумать строки, чьи хеш-коды идентичны. - person Mike Nakis; 30.12.2011

@MikeNakis Мне жаль, что мой вопрос не имел никакого смысла, но в любом случае вы все равно получили мой вопрос, но я не мог понять вашего объяснения, извините, но, похоже, вы просто повторяете их утверждение. Позвольте мне объяснить это многословно. Я говорю о худшем случае, поэтому очевидно, что все ключи генерируют один и тот же хэш. Чтобы сократить время доступа, обычно элементы в корзине сортируются. Таким образом, хэш «наихудшего случая» на самом деле похож на отсортированный массив. Итак, вы имеете в виду, что в этом случае невозможно использовать алгоритм сортировки, который может сортировать в O(n log n)? - person AppleGrew; 30.12.2011

Элементы @AppleGrew I в ведрах не сортируются, потому что их нельзя сортировать. Вы не можете сортировать по хэш-коду, потому что все элементы в корзине по определению имеют один и тот же хэш-код, и вы не можете сортировать по значению, потому что хэш-карта не может требовать, чтобы значения, которые вы помещаете в нее, были сопоставимыми объектами. - person Mike Nakis; 30.12.2011

@AppleGrew также, я не сказал, что ваш вопрос не имеет никакого смысла, я только сказал, что предложение о том, что сложность Hashtables в наихудшем случае равна O (n ^ 2), не имеет смысла, потому что вычислительная сложность является особенностью операция, которая может быть выполнена со структурой данных, а не функция самой структуры данных. В любом случае, я признаю, что это было излишне резко с моей стороны; в конце концов, это правда, что ваша формулировка часто используется в разговорной речи и обычно относится к операции, которая может быть выведена из контекста. Итак, я перефразирую свой ответ. - person Mike Nakis; 30.12.2011

@MarkNakis Извините, я тоже был резок. Цепочки в ведре обычно реализуются связным списком, верно? Если это так, то вставка n элементов должна занимать постоянное время (добавление элементов в голову). Итак, это снова O(n). Я до сих пор не понимаю, как мы приходим к O(n^2). Не могли бы вы указать мне какой-нибудь реальный код для быстрой реализации? - person AppleGrew; 30.12.2011

@AppleGrew Ну, вставка - это не просто размещение элемента в ведре, потому что сначала вам нужно посмотреть, есть ли у вас уже этот элемент, и если да, заменить его запись. Итак, вам нужно пройти через ведро. Единственная реализация хэш-набора, которую я когда-либо видел, — это хэш-набор CLI (C#, VB и т. д.), который можно загрузить с сайта Microsoft (выполните поиск по SSCLI и/или Rotor), но он огромен. , поэтому разобраться в этом — не прогулка в парке. - person Mike Nakis; 30.12.2011

@MikeNakis Спасибо, я совсем забыл, что ключи уникальны. - person AppleGrew; 31.12.2011