LINUX.ORG.RU
Форум — Development  

Реализация HashSet в OpenJDK

 , ,


0

3

Я конечно не силен в реализации классических структур, но ради интереса заглянул в реализацию HashSet и увидел там внутри HashMap с константой для value.

Это вообще нормально? Java и так добавляет оверхеда, а тут еще вкатили сверху... Или может я чего-то не понимаю и в рантайме это отображается на более оптимальную структуру? Или может убирается оверхед с константным value?

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

UPD1: Видимо это как связано с легаси, когда указатели были по 4 байта? И в итоге без value HashMap.Node всё равно выравнивался на 16 байтов? Но теперь же указатели по 8 байт и без value выравнивание было бы на 24 байта, а с value на 32 байта? Или то, что кеш-линия на 64 байта и всё нормалёк, всё равно больше 2 нод не запихать?

★★★★★

Последнее исправление: foror (всего исправлений: 4)

Поясни подробнее для тупых

KivApple ★★★★★
()

Это, как раз, разумно - позволяет избежать копирования огромнейшего куска кода, а джава это не то место, где будут задрачивать байты до такой степени.

GblGbl ★★★★★
()
Последнее исправление: GblGbl (всего исправлений: 1)

указатели все еще по 4 обычно, из-за Compressed Oops. Есть довольно много реализаций HashSet'ов которые более оптимальны по памяти, см. HPPC, Trove, FastUtil и тп.

maxcom ★★★★★
()

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

orm-i-auga ★★★★★
()

Я задавался вопросом и вразумительного ответа у меня нет.

migesok ★
() 
# Running 64-bit HotSpot VM.
# Using compressed oop with 0-bit shift.
# Using compressed klass with 3-bit shift.
# Objects are 8 bytes aligned.
# Field sizes by type: 4, 1, 1, 2, 2, 4, 4, 8, 8 [bytes]
# Array element sizes: 4, 1, 1, 2, 2, 4, 4, 8, 8 [bytes]

***** 32-bit VM: **********************************************************
java.util.HashMap$Node object internals:
 OFFSET  SIZE   TYPE DESCRIPTION                    VALUE
      0     8        (object header)                N/A
      8     4    int Node.hash                      N/A
     12     4 Object Node.key                       N/A
     16     4 Object Node.value                     N/A
     20     4   Node Node.next                      N/A
Instance size: 24 bytes
Space losses: 0 bytes internal + 0 bytes external = 0 bytes total

***** 64-bit VM: **********************************************************
java.util.HashMap$Node object internals:
 OFFSET  SIZE   TYPE DESCRIPTION                    VALUE
      0    16        (object header)                N/A
     16     4    int Node.hash                      N/A
     20     4        (alignment/padding gap)        N/A
     24     8 Object Node.key                       N/A
     32     8 Object Node.value                     N/A
     40     8   Node Node.next                      N/A
Instance size: 48 bytes
Space losses: 4 bytes internal + 0 bytes external = 4 bytes total

***** 64-bit VM, compressed references enabled: ***************************
java.util.HashMap$Node object internals:
 OFFSET  SIZE   TYPE DESCRIPTION                    VALUE
      0    12        (object header)                N/A
     12     4    int Node.hash                      N/A
     16     4 Object Node.key                       N/A
     20     4 Object Node.value                     N/A
     24     4   Node Node.next                      N/A
     28     4        (loss due to the next object alignment)
Instance size: 32 bytes
Space losses: 0 bytes internal + 4 bytes external = 4 bytes total

***** 64-bit VM, compressed references enabled, 16-byte align: ************
java.util.HashMap$Node object internals:
 OFFSET  SIZE   TYPE DESCRIPTION                    VALUE
      0    12        (object header)                N/A
     12     4    int Node.hash                      N/A
     16     4 Object Node.key                       N/A
     20     4 Object Node.value                     N/A
     24     4   Node Node.next                      N/A
     28     4        (loss due to the next object alignment)
Instance size: 32 bytes
Space losses: 0 bytes internal + 4 bytes external = 4 bytes total
Deleted
()
Последнее исправление: Deleted (всего исправлений: 1)
Ответ на: комментарий от Deleted

Опять же зачем там поле hash? 

if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
Есть надежда, на то, что ключ будет часто совпадать по адресу? В моём случае такого не припомню. Для сервер-сайда данные приходят извне.

foror ★★★★★
() автор топика
Последнее исправление: foror (всего исправлений: 2)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development