Почему реализация HashSet в Sun Java использует HashMap в качестве своей поддержки?

Question

Глядя на источник Java 6, HashSet<E> фактически реализован с использованием HashMap<E,Object>, с использованием экземпляра фиктивного объекта в каждой записи набора.

Я думаю, что тратит 4 байта (на 32-битных машинах) на размер самой записи.

Но почему он до сих пор используется? Есть ли какая-либо причина использовать его, кроме того, чтобы упростить поддержку кодов?

Answer 1

На самом деле, это не просто HashSet. Все реализации интерфейса Set в Java 6 основаны на базовом Map. Это не требование; это просто способ реализации. Вы можете убедиться сами, проверив документацию для различных реализаций Set.

Ваши основные вопросы

Но почему он до сих пор используется? Есть любая причина использовать это кроме того, чтобы сделать это проще поддерживать коды?

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

Set и Map - аналогичные интерфейсы, в которых дублирующиеся элементы не допускаются. (Я думаю, единственное Set , а не , подкрепленное Map, - это CopyOnWriteArraySet, что является необычной коллекцией, поскольку она неизменна.)

В частности:

Из документации Set:

Коллекция, которая не содержит дубликаты элементов. Более формально, наборы не содержат пары элементов e1 и е2 такие, что е1.equals (е2), и при самый один нулевой элемент. Как следует из его имя, этот интерфейс моделирует математический набор абстракций.

Интерфейс Set размещает дополнительные условия, помимо унаследованных из интерфейса коллекции, на контракты всех строителей и на контракты сложения, равны и методы hashCode. Объявления для другие унаследованные методы также включен сюда для удобства. (The спецификации, сопровождающие эти декларации были адаптированы к Установить интерфейс, но они не содержат любые дополнительные условия.)

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

А с Map:

Объект, который отображает ключи на значения. Карта не может содержать дубликаты ключей; каждый ключ может соответствовать максимум одному значению.

Если вы можете реализовать свои Set с использованием существующего кода, любая выгода (например, скорость), которую вы можете извлечь из существующего кода, будет накапливаться и у вашего Set.

Если вы решите внедрить Set без поддержки Map, вам придется дублировать код, разработанный для предотвращения дублирования элементов. Ах, восхитительная ирония.

Тем не менее, ничто не мешает вам реализовать ваши Set по-другому.

Answer 2

Я предполагаю, что HashSet изначально был реализован в терминах HashMap, чтобы сделать это быстро и легко. С точки зрения строк кода, HashSet является частью HashMap.

Я бы предположил, что причина, по которой он до сих пор не оптимизирован, это страх перемен.

Однако отходы намного хуже, чем вы думаете. Как в 32-разрядном, так и в 64-разрядном HashSet в 4 раза больше необходимого, а HashMap в 2 раза больше необходимого. HashMap может быть реализован с массивом с ключами и значениями в нем (плюс цепочки для коллизий). Это означает два указателя на запись или 16 байт на 64-битной виртуальной машине. Фактически, HashMap содержит объект Entry для каждой записи, который добавляет 8 байтов для указателя на Entry и 8 байтов для заголовка объекта Entry. HashSet также использует 32 байта на элемент, но трата составляет 4x вместо 2x, поскольку для него требуется всего 8 байтов на элемент.

Answer 3

Я предполагаю, что это никогда не превращалось в серьезную проблему для реальных приложений или важных тестов.Зачем усложнять код без реальной выгоды?

Также обратите внимание, что размеры объектов округляются во многих реализациях JVM, поэтому на самом деле увеличение размера может и не быть (я не знаю для этого примера).Также код для HashMap, вероятно, будет скомпилирован и помещен в кэш.При прочих равных условиях больше кода => больше пропусков кеша => более низкая производительность.

Answer 4

Я посмотрел на ваш вопрос, и мне потребовалось некоторое время, чтобы подумать о том, что вы сказали. Итак, вот мое мнение относительно реализации HashSet.

Необходимо иметь фиктивный экземпляр, чтобы знать, присутствует или нет значение в наборе.

Взгляните на метод добавления

public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

А теперь давайте посмотрим на возвращаемое значение пут

@ возвращает предыдущее значение, связанное с ключом, или ноль, если не было сопоставления для ключа. (Нулевой возврат также может указывать, что карта ранее ассоциировала нуль с ключом.)

Таким образом, объект PRESENT используется только для представления того, что набор содержит значение e. Я думаю, вы спросили, почему бы не использовать null вместо PRESENT. Но вы не сможете различить, если запись ранее была на карте, потому что map.put(key,value) всегда будет возвращать null, и вы не сможете узнать, существовал ли ключ.

---

При этом можно утверждать, что они могли использовать реализацию, подобную этой

   public boolean add(E e) {

        if( map.containsKey(e) ) {
            return false;
        }

        map.put(e, null);

        return true;

}

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

---

Если вы задали вопрос о том, почему они использовали HashMap, который бы тратил 8 байтов (из-за Map.Entry) вместо какой-либо другой структуры данных, использующей похожую запись только из 4, тогда да, я бы сказал, что они сделали это по причинам, которые вы упомянули.

Answer 5

Да, вы правы, определенное количество отходов определенно есть. Небольшой, потому что для каждой записи используется один и тот же объект PRESENT (который объявлен как final). Следовательно, единственная потеря относится к значению каждой записи в HashMap.

В основном, я думаю, они выбрали этот подход для удобства обслуживания и повторного использования. (Разработчики JCF подумали бы, мы все равно протестировали HashMap, почему бы не использовать его повторно.)

Но если у вас огромные коллекции и вы помешаны на памяти, вы можете выбрать лучшие альтернативы, такие как Trove или Google Collections .

Answer 6

После поиска по страницам, подобным этой, задаюсь вопросом, почему умеренно неэффективная стандартная реализация, обнаружила com.carrotsearch.hppc.IntOpenHashSet

Answer 7

Ваш вопрос: Я думаю, что тратит 4 байта (на 32-битных машинах) на размер самой записи.

Всего одна переменная Object создается для всей структуры данных hashset, и это спасет вас от повторной записи всего кода типа hashMap снова.

private static final Object PRESENT = new Object();

Все ключи имеют одно значение, т.е. объект PRESENT.