Care este complexitatea temporală a operațiunilor asupra elementelor în HashMap, și HashMap garantează complexitatea indicată la extragerea unui element?

Complexitatea temporară a operațiunilor principale (get, put, remove, containsKey) în HashMap este în medie O(1).

Aceasta se realizează prin utilizarea unui tabel de dispersie, unde elementele sunt stocate în celule (buckets), determinate de codul hash al cheii. În cazul ideal, fiecare bucket conține un singur element.

Totuși, în cel mai rău caz, când toate cheile au același cod hash sau apar multe coliziuni, elementele ajung în același bucket. În acest caz, bucket-ul poate deveni o listă legată (până la Java 8) sau un arbore (Java 8 și mai recent, dacă numărul de elemente din bucket depășește un anumit prag). Operațiile pe un astfel de bucket vor avea complexitatea temporară O(n), unde n este numărul de elemente din bucket.

HashMap nu garantează o complexitate temporară constantă O(1) la recuperarea unui element. Se garantează doar o medie de O(1). În cel mai rău caz, complexitatea poate fi O(n).

Factorii care influențează complexitatea temporară:

• Calitatea funcției hash: O funcție hash bună distribuie uniform cheile pe bucket-uri, minimizând coliziunile.
• load factor (coeficientul de încărcare): Determină cât de plină poate fi tabela de dispersie înainte de a se mări dimensiunea acesteia (rehash). Un load factor ridicat poate crește probabilitatea coliziunilor.
• Capacitatea inițială: O capacitate inițială prea mică, cu un număr mare de elemente, va cauza rehash-uri frecvente, ceea ce este o operație costisitoare.