Môžete vysvetliť, ako je implementovaná dátová štruktúra HashMap a ako zabezpečuje rýchly prístup k prvkom?

HashMap je dátová štruktúra, ktorá uchováva páry kľúč-hodnota a zabezpečuje rýchly prístup k hodnotám pomocou kľúča. Je založená na poli bucketov, do ktorého sú prvky umiestnené na základe hash kódu kľúča.

Pri pridávaní páru sa vypočíta hash kód kľúča a podľa neho sa určí index bucketu (zvyčajne pomocou operácie modulo s veľkosťou poľa). Ak je v bucketu už nejaké prvky (kolízia), sú uložené vo forme prepojenej zoznamu alebo stromu (v novších verziách Java).

Pri hľadaní prvku podľa kľúča sa vykonávajú:

• Výpočet hash kódu kľúča
• Určenie bucketu
• Vyhľadávanie v bucketu pomocou metódy equals medzi prvkami so zhodným hash kódom

Toto zabezpečuje priemernú zložitosť prístupu O(1), ale v najhoršom prípade (veľa kolízií) sa môže degradovať na O(n). Aby sa tomu predišlo, veľkosť poľa sa zväčšuje pri dosiahnutí určitého faktora zaťaženia (load factor).