Почему реализация HashSet в Sun Java использует HashMap в качестве основы?
https://stackoverflow.com/questions/2235546
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Глядя на исходный код Java 6, HashSet<E> фактически реализуется с использованием HashMap<E,Object>, используя экземпляр фиктивного объекта для каждой записи набора.
Я думаю, что это тратит 4 байта (на 32-битных машинах) на размер самой записи.
Но почему его до сих пор используют?Есть ли какая-либо причина использовать его, кроме упрощения поддержки кодов?
Решение
На самом деле, это не просто HashSet. Все реализации Set интерфейс в Java 6 основан на базовом Map.Это не является обязательным требованием;это просто способ реализации.Вы можете убедиться в этом сами, просмотрев документацию по различным реализациям Set.
Ваши главные вопросы
Но почему его до сих пор используют?Есть ли причины использовать его, кроме того, чтобы облегчить поддержание кодов?
Я предполагаю, что поддержка кода является важным мотивирующим фактором.То же самое относится и к предотвращению дублирования и раздувания.
Set и Map являются схожими интерфейсами, в которых дублирование элементов не допускается.(Я думаю, что единственный Set нет при поддержке Map является CopyOnWriteArraySet, что является необычной коллекцией, поскольку она неизменна.)
Конкретно:
Из документация Set:
Коллекция, которая не содержит дублирующих элементов.Более формально, наборы не содержат пары элементов e1 и e2, таких как e1.equals (e2) и не более одного нулевого элемента.Как подразумевается его имя, этот интерфейс моделирует Абстракция математических множеств.
В интерфейсе Set размещаются дополнительные оговорки, выходящие за рамки унаследованных в интерфейсе Collection, в меню договоров всех строителей и на Контракты add, равно и Методы hashCode.Декларации для Другие унаследованные методы также включен сюда для удобства.(Метод Технические характеристики, сопровождающие их Декларации были адаптированы к Set interface, но они не содержат любые дополнительные условия.)
Дополнительные условия на конструкторах, неудивительно, что все конструкторы должны создавать набор, который не содержит дублирующих элементов (как определено выше).
И из Map:
Объект, который сопоставляет ключи со значениями.Карта не может содержать повторяющиеся ключи;каждый ключ может сопоставляться не более чем с одним значением.
Если вы сможете реализовать свой SetЕсли вы используете существующий код, любая выгода (например, скорость), которую вы можете получить от существующего кода, достается вашему Set также.
Если вы решите реализовать Set без Map Для поддержки вам придется дублировать код, предназначенный для предотвращения дублирования элементов.Ах, вкусная ирония.
Тем не менее, ничто не мешает вам реализовать свои Setэто по-другому.
Другие советы
Я предполагаю, что это никогда не представляло собой серьезную проблему для реальных приложений или важных тестов.Зачем усложнять код без реальной выгоды?
Также обратите внимание, что во многих реализациях JVM размеры объектов округляются в большую сторону, поэтому на самом деле увеличения размера может не быть (я не знаю для этого примера).Также код для HashMap скорее всего, будет скомпилирован и сохранен в кеше.При прочих равных условиях больше кода => больше промахов в кэше => меньшая производительность.
Я предполагаю, что HashSet изначально был реализован на основе HashMap, чтобы сделать это быстро и легко.С точки зрения строк кода HashSet является частью HashMap.
Я предполагаю, что причина, по которой он до сих пор не оптимизирован, — это страх перед переменами.
Однако отходы гораздо хуже, чем вы думаете.Как в 32-битной, так и в 64-битной версии HashSet в 4 раза больше, чем необходимо, а HashMap — в 2 раза больше, чем необходимо.HashMap можно реализовать с помощью массива с ключами и значениями (плюс цепочки для коллизий).Это означает два указателя на запись или 16 байт на 64-битной виртуальной машине.Фактически, HashMap содержит объект Entry для каждой записи, что добавляет 8 байтов для указателя на Entry и 8 байтов для заголовка объекта Entry.HashSet также использует 32 байта на элемент, но потери составляют 4x вместо 2x, поскольку для каждого элемента требуется всего 8 байт.
Да, вы правы, небольшие потери определенно есть.Небольшой, потому что для каждой записи используется один и тот же объект. PRESENT(который объявлен окончательным).Следовательно, единственная потеря — это значение каждой записи в HashMap.
Я думаю, что в основном они использовали этот подход для удобства обслуживания и возможности повторного использования.(Разработчики JCF могли подумать, что мы все равно протестировали HashMap, почему бы не использовать его повторно.)
Но если у вас огромные коллекции и вы помешаны на памяти, вы можете отказаться от лучших альтернатив, таких как Находка или Коллекции Google.
Я посмотрел на ваш вопрос, и мне потребовалось некоторое время, чтобы обдумать то, что вы сказали.Итак, вот мое мнение относительно HashSet выполнение.
Необходимо иметь фиктивный экземпляр, чтобы знать, присутствует ли значение в наборе или нет.
Взгляните на метод добавления
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
Абд, теперь давайте посмотрим на возвращаемое значение put.
@возвращает предыдущее значение, связанное с ключом, или значение null, если для ключа не было сопоставления.(Нулевой возврат также может указывать на то, что карта ранее ассоциировала с ключом значение 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, тогда да, я бы сказал, что они сделали это по упомянутым вами причинам.
Просматривая подобные страницы, задаваясь вопросом, почему слегка неэффективная стандартная реализация, нашел com.carrotsearch.hppc.IntOpenHashSet.
Ваш вопрос:Я думаю, что это тратит 4 байта (на 32-битных машинах) на размер самой записи.
Для всей структуры данных хеш-набора создается только одна переменная Object, и это избавит вас от повторного написания всего кода типа hashMap.
private static final Object PRESENT = new Object();
Все ключи имеют одно значение, то есть объект PRESENT.
