Большой O хеш-таблицы против двоичного дерева поиска

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

Однако обратите внимание, что в Java, например, есть LinkedHashSet и LinkedHashMap, которые дают вам некоторые преимущества Hash, но которые можно перемещать в том порядке, в котором они были добавлены, поэтому вы можете отсортировать его и иметь возможность перемещаться по нему в этом отсортированный порядок, а также извлечение элементов по хешу.

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

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

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

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

Правильно, печать отсортированных данных, хранящихся в хеш-таблице, будет медленнее, потому что хеш-таблица не является отсортированными данными. Это просто дает вам быстрый способ найти конкретный предмет. В "нотации Big O" сказано, что элемент можно найти за постоянное время, т. Е. O (1) раз.

С другой стороны, вы можете найти элемент в двоичном дереве поиска за «логарифмическое время» (O (log n)), потому что данные уже были отсортированы для вас.

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

Это поднимает пару интересных вопросов. Дерево поиска по-прежнему работает быстрее, учитывая следующее?

1. Включая время настройки как для хеш-таблицы, так и для BST?
2. Если алгоритм хеширования выдает отсортированный список слов. Технически вы можете создать хеш-таблицу, которая использует алгоритм, который это делает. В этом случае скорость BST по сравнению с хеш-таблицей должна быть уменьшена до количества времени, необходимого для заполнения хеш-таблицы в отсортированном порядке.

Также ознакомьтесь с соответствующими соображениями по поводу списка пропуска и двоичного дерева: Список пропуска и двоичное дерево