#indexing #data-structures #hashmap
#индексирование #структуры данных #hashmap
Вопрос:
Просматриваем некоторую информацию из интервью о структурах данных и т. Д.
Итак, как я понимаю, массивы имеют значение O (1) для индексации, что, я полагаю, означает поиск определенного элемента, содержащегося в пространстве x в массиве. Просто хочу подтвердить это, поскольку я сам сомневаюсь.
Кроме того, хэш-карты имеют значение O (1) для индексации, поиска, вставки и удаления. Разве это не делает бессмысленным любой вопрос о структуре данных, поскольку хэш-карта всегда будет лучшим решением?
Спасибо
Комментарии:
1. Не удается выполнять запросы диапазона с помощью хэш-карт (эффективно)
2. Потому что slooooooooow. Подсказка: какие шаги требуются для индексации в массив; и те, которые требуются для поиска элемента в хеш-таблице? (Обратите внимание, я только отвечаю на вопрос, почему мы вообще используем массивы, а не хэш-таблицы для всего. Это даже не касается почти бесконечных других вариантов использования, когда один — или оба — совершенно непригодны)
Ответ №1:
Ну, индексирование касается не только массивов,
согласно этому — индексирование — это создание таблиц (индексов), которые указывают на расположение папок, файлов и записей. В зависимости от цели, индексирование определяет местоположение ресурсов на основе имен файлов, ключевых полей данных в записи базы данных, текста в файле или уникальных атрибутов в графическом или видеофайле.
На ваш второй вопрос хэш-карты не являются абсолютными или лучшими структурами данных по разным причинам, в основном:
- Столкновения
- Время вычисления хэш-функции
- Используется дополнительная память
Также есть много вопросов о структуре данных, в которых хэш-карты не превосходят:
-
Структура данных для поиска k-го минимального элемента и поддержки обновлений (Hashmap будет похож на грубую силу, потому что он не сортирует элементы, поэтому нам нужно что-то вроде сбалансированного двоичного дерева поиска)
-
Структура данных для поиска, есть ли слово в словаре (конечно, hashmap работает, но Trie намного быстрее и меньше памяти)
-
Структура данных для поиска минимального элемента в любом диапазоне массива с обновлениями (опять же, hashmap слишком медленный для этого, нам нужно что-то вроде дерева сегментов)
-
…