Что такое индексация? Почему мы не используем хеширование для всего?

Question

Просматривая некоторую информацию об интервью о структурах данных и т. Д.

Итак, как я понимаю, массивы - это O (1) для индексации, что, как я считаю, означает поиск конкретного элемента, содержащегося в пространстве x в массиве.Просто хочу подтвердить это, так как я сам второй догадываюсь.

Кроме того, хэш-карты являются O (1) для индексации, поиска, вставки и удаления.Разве это не делает вопрос структуры данных бессмысленным, поскольку хеш-карта всегда будет лучшим решением?

Спасибо

Answer 1

Ну, индексация - это не только массивы,

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

Для вашего второго вопроса хеш-карты не являются абсолютными или лучшими структурами данных по разным причинам, в основном:

• Коллизия
• Время вычисления хеш-функции
• используется дополнительная память

Также есть много вопросов о структуре данных, где хеш-карты не превосходят:

• Структура данных для нахождения k-го минимального элемента и поддержки обновлений (Hashmap будет похож на bruteforce, потому что он не поддерживает сортировку элементов, поэтому нам нужно что-то вроде сбалансированного бинарного дерева поиска)

• Структура данных для нахождения слова в словаре (конечно, хэш-карта работает, но Trie намного быстрее и меньше памяти)

• Структура данных для поиска минимального элемента в любом диапазоне массива с обновлениями (еще раз hashmap слишком медленный для этого, нам нужно что-то вроде дерева сегментов)

• ...