Big O of Hash Table против бинарного дерева поиска

Question

Что займет больше времени?

печать всех элементов, хранящихся в двоичном дереве поиска, в отсортированном порядке или печать всех элементов, хранящихся в хеш-таблице, в отсортированном порядке.

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

Answer 1

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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

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

Наслаждайтесь

Роберт К. Картейно

Answer 5

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

Answer 6

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

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