Почему JAVA HashSet использует HashMap внутренне? Разве это не потеряет память? [Дубликат]

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

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

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

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

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

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

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

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

Теперь Abd посмотрим на возвращаемое значение put

@ возвращает предыдущее значение, связанное с ключом, или 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, то да, я бы сказал, что они сделали это по причинам, о которых вы упомянули.

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

Создана только одна переменная объекта для всей структуры данных хэшета, и это будет

private static final Object PRESENT = new Object();

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

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

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

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