вопросы по проектированию структуры данных для векторов?

Question

Читая некоторые материалы по проектированию структуры данных для разреженных векторов, авторы делают следующие утверждения:

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

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

Далее авторы утверждают, что

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

Почему реализация на основе хеша работает плохо при переборе всех значений? Связано ли это с более медленной оценкой индекса?

Как древовидная структура может помочь в решении этой проблемы?

Answer 1

Доступ к индексу хеш-таблицы немного медленнее из-за затрат на вычисление.
В хеш-таблице, если вы запрашиваете элемент 452345435, это не означает, что он находится в ячейке 452345435 ... Хеш-таблица выполняет последовательностьрасчета, чтобы найти правильную ячейку.Это зависит от реализации.
Хеш-таблица Анализ производительности

Хеш-таблицы не хранят отсортированные данные.Поэтому, если вы хотите получить элементы в правильном порядке, необходимо вызвать алгоритм сортировки.

Чтобы решить эту проблему, вы можете использовать дерево или любую другую структуру отсортированных данных.
Но этоувеличит сложность вставки с O (1) (хеш-таблица) до O (logn) (вставка в дерево, отсортированная база данных).
Это потому, что каждый индекс будет добавлен к обеим структурам данных, и сложность будет O(1) + O (logn) = O (logn)

Потребуется только O (1) для извлечения данных, поскольку достаточно запросить их из хеш-таблицы.