Задать вопрос
@albertalexandrov
python

В чем заключается худший случай для хеш-таблиц?

Привет!

Пишут, что для хеш-таблиц худший случай для поиска, вставки и удаления - это О(n). В чем кроется этот худший случай? Перестройка индекса таблицы?
  • Вопрос задан
  • 538 просмотров
Комментировать
Подписаться 1 Простой Комментировать
Пригласить эксперта
Ответы на вопрос 2
GavriKos
@GavriKos
Вам пример? Это когда у всех элементов хеш совпадает - невозможно найти нужный элемент только по хешу и приходится искать вручную. Т.е. таблица грубо говоря становится обычным массивом.
Ответ написан
Комментировать
Комментировать
@Teslaman
При коллизиях (совпадении хэша) элементы обычно складывают в связный список. В поиске по этому связному списку и кроется O(n).
Ответ написан
Комментировать
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Вакансии с Хабр Карьеры
Team Lead (С++, Python)
TopAssistant • Москва
от 400 000 ₽
Python developer
Bell Integrator
До 350 000 ₽
Python developer
Greenway Global • Новосибирск
от 150 000 до 200 000 ₽
Ещё вакансии
Заказы с Хабр Фриланса
Поднять собственный сервер на Матриксе
16 апр. 2024, в 20:08
1000 руб./в час
Сверстать 2 транзакционных письма по макету figma
16 апр. 2024, в 20:05
3000 руб./за проект
Автоматизировать работу ноумен с Инстаграмом
16 апр. 2024, в 19:33
1000 руб./за проект
Ещё заказы