Какова повышенная стоимость TreeSet по сравнению с LinkedHashSet и TreeMap по сравнению с LinkedHashMap?

Question

LinkedHashSet - Эта реализация избавляет своих клиентов от неопределенного, обычно хаотического порядка, предоставляемого HashSet, без увеличения стоимости , связанной с TreeSet .

То же самое сказано о LinkedHashMap против TreeMap

Какова эта повышенная стоимость (LinkedHashMap против TreeMap) в точности?

Означает ли это, что TreeSet требуется больше памяти на элемент?LinkedHashSet требуется больше памяти для двух дополнительных ссылок, но TreeSet требуется дополнительная память для хранения пары элементов Map.Entry (поскольку она неявно основана на TreeMap), кроме того, LinkedHashSet основан на HashMap, который также имеет накладные расходы на пару элементов Map.Entry ...

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

Какие другие существенные увеличения затрат?

Answer 1

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

Если вменяемое упорядочениеважно, что вам, как правило, нужно использовать TreeSet , который выполняет итерацию в отсортированном порядке, но по цене, поскольку поддержание отсортированного порядка увеличивает сложность процесса.

A LinkedHashSet можно использовать в качестве промежуточного решения для, казалось бы, безумного порядка HashSet, гарантируя, что порядок итераций по крайней мере согласован с использованием порядка вставки.

Answer 2

TreeSet / TreeMap имеют более высокую временную сложность для таких операций, как задница add(), contains() (для TreeSet), put(), containsKey() (для TreeMap) и т. Д.Так как им требуется логарифмическое время, чтобы найти элементы в дереве (или добавить элементы в дерево), тогда как LinkedHashSet / LinkedHashMap требует ожидаемого постоянного времени для этих операций.

С точки зрения требований к памяти, существуеточень небольшая разница:

• TreeMap записи содержат ключ, значение, 3 Entry ссылки (слева, справа, родитель) и boolean.

• LinkedHashMap записи содержат ключ, значение, 3 Entry ссылки (далее, до, после) и int.