HashMap-ə element əlavə etmə əməliyyatının vaxt mürəkkəbliyi necə müəyyən edilir?

Java-da HashMap-ə element əlavə etmənin vaxt mürəkkəbliyi orta hesabla O(1) — sabit vaxtdır. Bu, yeri sürətlə müəyyən etmək üçün hash funksiyasından istifadə etməklə əldə edilir.

Ancaq ən pis halda, əgər toqquşma baş verərsə və bütün elementlər eyni səbətdə (bucket) toplanarsa, əlavə etmə O(n) qədər pisləşə bilər, burada n həmin səbətdəki elementlərin sayıdır.

Java 8-dən başlayaraq, çox sayda toqquşma olduqda, səbət əlaqəli siyahıdan balanslı ağaca (TreeMap) çevrilir, bu da ən pis halda O(log n) səviyyəsinə yaxşılaşdırır.

Nümunə:

HashMap<String, Integer> map = new HashMap<>();
map.put("key", 42); // orta hesabla O(1) əlavə