Какое худшее время работы Hashing с цепочкой?

Предположим, что число хеш-таблиц (например, n) пропорционально количеству элементов в таблице (скажем, m). Мы имеем n = O (m), Коэффициент нагрузки l = O (m)/m = O (1) Итак, в предположении Простая равномерная хеширование, поиск занимает среднее время в среднем. Это означает, что при среднем поиске требуется время, пропорциональное длине связанного списка, который одинаковый для всех слотов и, следовательно, постоянное время. Но как насчет наихудшего времени работы в предположении Простая равномерная хеширование. Является ли он также постоянным или будет O (1 + l). Пожалуйста, объясните, я смущен. [Ссылка CLRS Page 260]Какое худшее время работы Hashing с цепочкой?

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

источник

2013-11-27 Sonali

Унифицированного хэширования недостаточно, чтобы дать вам хорошие оценки в худшем случае. Семейство хешей может быть однородным, а конкретная функция все еще хэширует каждую клавишу в том же ковше. Если вы можете получить универсальную хэш-функцию, вы можете с высокой вероятностью получить границы «O (logn)»: http://stackoverflow.com/questions/4553624/hashmap-get-put-complexity/23954819#23954819 –

В предположении простой равномерной Hashing (т.е. гипотетическая функция хеширования будет равномерно распределять предметы в слоты хэш-таблицы), я считаю, что производительность в худшем случае для операции поиска будет такой же, как в среднем -case (для безуспешного поиска) - Θ(n/m + 1) (средний случай согласно Wikipedia).

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

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

В общем случае, наихудшее время работы для поиска или удаления операции для хэш-таблицы с использованием цепочки составляет Θ(n).

В обоих случаях вставка все еще может быть выполнена как Θ(1), так как вы можете просто вставлять ее спереди. То есть, если мы разрешаем дубликаты (как упоминалось Jim), потому что, если нет, мы сначала должны проверить, есть ли он там (т. Е. Выполнить поиск).

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

|--------| 
|element1| -> element2 -> element3 -> element4 -> element5 
|--------| 
| null | 
|--------| 
| null | 
|--------| 
| null | 
|--------| 
| null | 
|--------|

источник

2013-11-27 19:11:27 Dukeling

Вставить могут быть реализованы как O (1)? Только если вы разрешаете дубликаты. –

@JimMischel О, право. Благодарю. Я забыл об этом. Добавлено примечание. – Dukeling

"в соответствии с вышеприведенным допущением, каждый слот в таблице будет иметь одинаковое количество элементов в своей цепочке" - совершенно неправильно. это не то, что означает Simple Uniform Hash. Просто потому, что хеш-функция равномерно распределяет * целое * множество элементов, это не значит, что он будет делать это для определенного подмножества. Худшее время, как вы сказали, - O (n). –

Какое худшее время работы Hashing с цепочкой?

ответ

Смежные вопросы