Aký objem pamäte je pridelený v HashSet pre uloženie dvoch prvkov, z ktorých jeden má hashCode 0 a druhý 1000000?

V Jave je HashSet implementovaný na základe HashMap, kde sú prvky uložené ako kľúče. Vo vnútri HashMap sa používa pole košov (tabuľka), ktorého veľkosť je vždy mocnina dvojky, predvolene 16.

Pri pridávaní prvého prvku HashSet alokuje pole s 16 košmi. Každý kôš je buď null alebo prepojený zoznam (alebo strom, ak je veľa prvkov).

Pre dva prvky s hashCode 0 a 1000000:

• Index koša sa vypočíta ako hash & (table.length - 1).
• Pre hashCode 0 bude index 0.
• Pre hashCode 1000000 (v binárnom tvare) bude index 1000000 & 15.

Číslo 1000000 v binárnom tvare končí na 0, takže index bude 0.

Oba prvky tak padnú do rovnakého koša (index 0), a vo vnútri tohto koša bude prepojený zoznam s dvoma prvkami.

Pamäťové požiadavky:

• Pole košov: 16 odkazov (každý 4 alebo 8 bajtov v závislosti od JVM).
• Dva objekty Node (vnútorné prvky HashMap), každý obsahuje kľúč, hodnotu (pre HashSet, fiktívnu hodnotu), odkaz na ďalší prvok a hash.

Celkovo je alokované pole s 16 prvkami a dva objekty Node, prepojené v reťazci v jednom koši.

Príklad:

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

Oba prvky budú v koši s indexom 0, čo môže viesť k zhoršeniu výkonu pri vyhľadávaní.