В каноничной хеш-таблице в случае возниконовения коллизий элементы с равным хешем помещаются в связный список. Это приводит к тому, что поиск по контейнеру стоит O(n). Почему для контейнера не использовать другую структуру данных? Например, красно-черное дерево. Или другую хеш-таблицу с другим хешем. Поиск и удаление в таком случае удешевляется. Правда, вставка становится заметно дороже. Цена вставки новых элементов перевешивает цену поиска? Есть ли какие-нибудь библиотеки в любом из современных языков, что позволяют выбирать контейнер для коллизий? Например, можно было бы придумать такой случай: сначала я заполняю хеш-таблицу, а после точно знаю, что мне очень сильно понадобится быстрый поиск - так я возьму и преобразую контейнеры в более подходящие. Или я заранее осознаю стоимость вставки, но поиск все равно гораздо важней.
Ответ
Поиск будет давать O(n) в случае крайне плохого хэша, когда все элементы будут иметь один и тот же хэш. При нормально подобранной хэш-функции получается O(1)
Однако в случае алгоритмов стандарт не написан :), так что да, вполне можно использовать и иные методы разрешения коллизий. Список можно заменять деревом, массивом или даже иной хэш-таблицей с другой хэш-функцией - в конце-концов, идеальное хеширование (см., например, Кормен и др. Алгоритмы. Построение и анализ) именно так и поступает.
Вопрос в заложенных в O() константах. При небольших размерах цепочек поиск (и особенно вставка, когда она играет роль) в них может проводиться быстрее за счет малой константы, чем в более быстрой, но более сложной структуре.
Более того, тут уже начинают играть свою роль и другие факторы, такие как использование кэша процессора и т.п. не совсем алгоритмические мелочи.
Так что для достижения максимального быстродействия, пожалуй, есть только один путь - практически-экспериментальный, и давать он может для каждой связки задача+машина свое решение...
Комментариев нет:
Отправить комментарий