Ile pamięci jest przydzielane w HashSet do przechowywania dwóch elementów, z których jeden ma hashCode 0, a drugi 1000000?

W Javie HashSet jest zaimplementowany na podstawie HashMap, gdzie elementy są przechowywane jako klucze. Wewnątrz HashMap używany jest tablica kubełków (table), której rozmiar jest zawsze potęgą dwójki, domyślnie 16.

Przy dodaniu pierwszego elementu, HashSet przydzieli tablicę z 16 kubełkami. Każdy kubełek to null lub powiązana lista (lub drzewo, jeśli jest dużo elementów).

Dla dwóch elementów z hashCode 0 i 1000000:

• Indeks kubełka jest obliczany jako hash & (table.length - 1).
• Dla hashCode 0, indeks będzie 0.
• Dla hashCode 1000000 (w postaci binarnej), indeks będzie 1000000 & 15.

Liczba 1000000 w postaci binarnej kończy się na 0, więc indeks będzie 0.

W związku z tym oba elementy trafią do tego samego kubełka (indeks 0), a wewnątrz tego kubełka będzie powiązana lista z dwoma elementami.

Zużycie pamięci:

• Tablica kubełków: 16 odwołań (każde 4 lub 8 bajtów w zależności od JVM).
• Dwa obiekty Node (wewnętrzne elementy HashMap), z których każdy zawiera klucz, wartość (dla HashSet, fikcyjną wartość), odwołanie do następnego elementu i hash.

Podsumowując, alokowana jest tablica z 16 elementami i dwa obiekty Node, połączone w łańcuch w jednym kubełku.

Przykład:

HashSet<Integer> set = new HashSet<>();
set.add(0);       // hashCode = 0
set.add(1000000); // hashCode = 1000000

Oba elementy będą w kubełku o indeksie 0, co może prowadzić do pogorszenia wydajności podczas wyszukiwania.