#algorithm #hashtable
Вопрос:
В моей хэш-таблице каждый список отсортирован (метод цепочки). 1.Как это повлияет на время выполнения поиска существующего ключа 2.Как это повлияет на время выполнения поиска отсутствующего ключа? 3.Как это повлияет на время поиска для добавления и удаления ключа?
Ответ №1:
1.Как это повлияет на время выполнения поиска существующего ключа.
Не так уж и много, потому что столкновения случаются редко.
Где N-размер вашей хэш-таблицы, M-количество столкновений.
М часто слишком мал ( от 0 до 50 ), поэтому скорость меняется не так сильно.
В случае, если M слишком велико и близко к N, в этой ситуации у нас плохой алгоритм хеширования, и его следует улучшить.
Наихудший случай M=N, если у вас ужасный алгоритм хеширования, поэтому у вас двоичный поиск со сложностью O(Log N).
Преимущества хэш-таблицы уничтожены. Деградация O(1) -> O(Log N)
Так что нам все равно следует избегать этого.
2.Как это повлияет на время выполнения поиска отсутствующего ключа.
Тот же ответ с 1. M часто настолько мал, что если нет, перепишите свой алгоритм хеширования.
Комментарии:
1. Ладно, я понял. Что вы думаете о номере 3? Добавление / удаление ключа — как это повлияет на время выполнения? (Если списки отсортированы)
2. Тем не менее, поскольку это связано с ядром хэш-таблицы, столкновение является редким случаем, поэтому вам не следует слишком зацикливаться на нем, вам лучше сосредоточиться на алгоритме хеширования и попытаться сохранить преимущества хэш-таблицы. O(1) — идеальный случай …