хеш-набор может найти самый маленький или самый большой элемент с O (1)?

Question

Мне нужно очень хорошо понимать архитектуру и функции хэш-набора.

В чем преимущество STL :: set по сравнению с STL :: set?Я думаю, что O (1) время, чтобы сделать поиск.Если это правда, почему бы не использовать хеш-таблицу?Их отличие это дублированный элемент?или другие?

Для STL :: set время поиска наименьшего / наибольшего также равно O (1), поскольку оно было упорядочено.

Набор хэшей не является бинарным деревом поиска, как найти самый маленький или самый большой элемент с O (1)?

После прочтения В чем разница между set и hashset в C ++ STL?

Не могу найти ответ.

Моя идея:

Когда следует использовать хэш-набор, а не хеш-таблицу?

STL :: set - упорядоченный набор.Таким образом, это O (1), чтобы получить самый маленький / самый большой элемент.

Что если для хеша установить?это заказано?

спасибо

Answer 1

Хэш-набор не является бинарным деревом поиска, как найти самый маленький или самый большой элемент с O (1)?

Это как раз одно из ключевых отличий: вы можетене найти самый маленький / самый большой элемент в хэше, установленном в постоянное время.Конечно, вы можете сделать это за O(n) раз, просканировав весь набор.

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

Answer 2

Хеш-набор - это, по сути, хеш-таблица без сохраненных значений (только ключи), а std::set в C ++ реализованы как сбалансированное двоичное дерево поиска.

Вы должны прочитать о различиях в некоторых книгах по алгоритмам / информатике, так как у вас, похоже, есть некоторые базовые заблуждения, например, в бинарном дереве поиска стоимость поиска наименьшего / наибольшего элемента логарифмическая O(log N), а не постоянная O(1).

В зависимости от операций, которые вам нужно выполнять чаще всего, любая структура данных будет более подходящей. Если вам нужно найти самый маленький элемент довольно часто, то std::set выполнит операцию в O(log N), но с хэш-таблицей вам нужно будет проверить все элементы, а это означает линейное время O(N). Если, с другой стороны, эта операция не является обычной и регулярные поиски (является ли элемент a в наборе?) Более распространенными, поиск в хэш-памяти с постоянным временем будет лучше, чем O(log N) поиск в наборе.