Почему делает реализацию HashSet в использовании Java Sun HashMap как его поддержка?
Рассмотрение источника Java 6, HashSet<E> на самом деле реализован с помощью HashMap<E,Object>, использование фиктивного экземпляра объекта на каждой записи Набора.
Я думаю что отходы 4 байта (на 32-разрядных машинах) для размера самой записи.
Но, почему это все еще используется? Там какая-либо причина состоит в том, чтобы использовать его помимо помощи поддержать коды?
4 ответа
На самом деле, это не просто HashSet . Все реализации интерфейса Set в Java 6 основаны на лежащей в основе карте . Это не требование; это просто способ реализации. Вы можете убедиться в этом сами, просмотрев документацию по различным реализациям Set .
Ваши основные вопросы:
Но почему он все еще используется? Есть ли какая-либо причина для его использования, кроме упрощения обслуживания кодов?
Я полагаю, что обслуживание кода является большим мотивирующим фактором. Так предотвращается дублирование и раздувание.
Набор и Карта являются аналогичными интерфейсами, в которых дублирование элементов не допускается.(Я думаю, что единственный Set не , поддерживаемый Map , - это CopyOnWriteArraySet , который является необычным набором, потому что он неизменяемый.)
В частности, :
Из документации для Set :
Коллекция, не содержащая повторяющихся элементов. Более формально, наборы не содержат пары элементов e1 и e2 таких, что e1.equals (e2), и не более одного нулевого элемента. Как следует из названия , этот интерфейс моделирует абстракцию математического множества .
Интерфейс Set помещает дополнительные условия, помимо тех, которые унаследованы от интерфейса Collection, в контрактах всех конструкторов и в контрактах методы add, equals и hashCode. Объявления для других унаследованных методов также включены сюда для удобства. (Спецификации , сопровождающие эти объявления , адаптированы к интерфейсу Set, но не содержат каких-либо дополнительных условий.)
Дополнительное условие on конструкторах, что неудивительно, все конструкторы должны создавать набор , не содержащий повторяющихся элементов (как определено выше).
И из Карта :
Объект, который отображает ключи в значения. Карта не может содержать повторяющиеся ключи; каждый ключ может соответствовать не более чем одному значению.
Если вы можете реализовать свои Наборы с использованием существующего кода, любое преимущество (например, скорость), которое вы можете получить из существующего кода, также получит ваш Набор .
Если вы решите реализовать набор Set без поддержки Map , вам придется дублировать код, предназначенный для предотвращения дублирования элементов. Ах, какая восхитительная ирония.
Тем не менее, ничто не мешает вам реализовать свой Set по-другому.
Я предполагаю, что это никогда не было серьезной проблемой для реальных приложений или важных тестов. Зачем усложнять код без реальной пользы?
Также обратите внимание, что размеры объектов округляются во многих реализациях JVM, поэтому на самом деле может не быть увеличения размера (я не знаю для этого примера). Также код для HashMap , вероятно, будет скомпилирован и находится в кеше. При прочих равных условиях больше кода => больше промахов в кеш => снижается производительность.
Да, вы правы, там небольшое количество отходов - дефинетли. Небольшой, потому что для каждой записи используется один и тот же объект PRESENT (который объявлен окончательным). Следовательно, единственная потеря - это значение каждой записи в HashMap.
В основном я думаю, что они использовали этот подход для удобства обслуживания и повторного использования. (Разработчики JCF подумали бы, что мы все равно протестировали HashMap, почему бы не использовать его повторно)
Но если у вас огромные коллекции, и вы любитель памяти, то вы можете выбрать лучшие альтернативы, такие как Trove или Google Collections.
Я посмотрел на ваш вопрос, и мне потребовалось время, чтобы обдумать то, что вы сказали. Итак, вот мое мнение о реализации HashSet .
Необходимо иметь фиктивный экземпляр, чтобы знать, присутствует ли значение в наборе или нет.
Взглянем на метод add.
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
Теперь давайте посмотрим на возвращаемое значение put
@ возвращает предыдущее значение, связанное с ключом, или null, если для ключа не было сопоставления. (Возврат 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, тогда да, я бы сказал, что они сделали это по указанным вами причинам.