@albertalexandrov

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

Привет!

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

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

Войти через центр авторизации
Похожие вопросы
SpectrumData Екатеринбург
от 150 000 до 200 000 ₽
Гринатом Москва
от 150 000 ₽
Greenway Global Новосибирск
от 150 000 ₽
15 июн. 2024, в 23:20
50000 руб./за проект
15 июн. 2024, в 23:15
4000 руб./за проект
15 июн. 2024, в 23:01
4400 руб./за проект