Ako je štruktúra bucket implementovaná v HashMap a ako ovplyvňuje ukladanie a vyhľadávanie údajov?

V Jave je dátová štruktúra HashMap organizovaná ako pole kôšov (bucket), kde každý kôš obsahuje spojený zoznam (alebo strom, ak je veľa prvkov) párov kľúč-hodnota, ktorých hash kód kľúča padá do tohto kôša.

Keď pridávate prvok, HashMap vypočíta hash kód kľúča a určí index kôša pomocou vzorca (zvyčajne hash kód modulo veľkosti poľa). Ak v kôši už sú prvky, vykoná sa vyhľadávanie v zozname alebo strome na aktualizáciu hodnoty alebo pridanie nového.

Pri hľadaní prvku podľa kľúča sa postupuje podobne: vypočíta sa index kôša a prehľadávajú sa prvky v kôši, aby sa našla zhoda kľúča.

Týmto spôsobom štruktúra kôšov umožňuje rýchle nájdenie prvkov v priemernom čase blízkom O(1), ale pri veľkom počte kolízií (keď veľa kľúčov padne do toho istého kôša) sa výkon môže zhoršiť.