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

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

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

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

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

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

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

Моя идея:

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

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

Что, если для набора хэшей? это заказано?

Благодарность


c++ hashmap stl hashtable hashset
person user1002288    schedule 26.12.2011    source источник
comment
Что заставляет вас думать, что вы можете найти самый большой или самый маленький элемент в O(1)?   -  person Jon Skeet    schedule 26.12.2011
comment
не могу понять, вы хотите, чтобы только самые маленькие/самые большие элементы в O (1) или поиск в O (1) или оба были O (1)?   -  person jackdoe    schedule 26.12.2011
comment
Как работает набор хэшей? (По сути, это то же самое, что и хэш-таблица.) Вот и ответ. Первый ответ в связанном посте отвечает на вопросы здесь: по существу случайный, [не] упорядоченный.   -  person    schedule 26.12.2011

Ответы (2)


arrow_upward
3
arrow_downward

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

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

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

person NPE    schedule 26.12.2011

arrow_upward
0
arrow_downward

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

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

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

person David Rodríguez - dribeas    schedule 26.12.2011
comment
Почему бы не O(1) найти самый маленький/самый большой элемент в std::set? set.begin() и set.rbegin() — ваши друзья. - person Xeo; 27.12.2011
comment
@Xeo, если набор не содержит определенной оптимизации, дереву может потребоваться O (log n), чтобы найти первый или последний элемент. - person Mark Ransom; 27.12.2011
comment
@Xeo, возможно, вы правы - согласно этой ссылке set.begin и set.rbegin должны иметь постоянную сложность. Я не уверен, стоит ли доверять ссылке, хотя. cplusplus.com/reference/stl/set/begin - person Mark Ransom; 27.12.2011
comment
@Mark: по крайней мере один недавний черновик стандарта требует постоянной сложности для begin и end для всех контейнеров. - person Philipp; 27.12.2011
comment
@Mark: Стандарты C++03 и C++11 требуют постоянной сложности в c.begin() и c.rbegin() для требований контейнера и обратимого контейнера (см. C++03 §23.1 p5 & p9 и C++11 §23.2.1 p4 & p9 для требований, а также C++03 §23.3.3 p2 и C++11 §23.4.6.1 p2, для которых требования std::set удовлетворяются). - person Xeo; 27.12.2011
comment
@Xeo: я не смотрел подробно новый стандарт. Время O(log N) — это стандартное время для поиска первого/последнего элемента в сбалансированном двоичном дереве. Конечно, реализация может принять решение о кэшировании этих двух конкретных значений — и кажется, что стандарт предписывает это. - person David Rodríguez - dribeas; 27.12.2011