HashMap-də elementlər üzərində əməliyyatların vaxt mürəkkəbliyi nədir və HashMap element seçərkən göstərilən mürəkkəbliyi təmin edirmi?

HashMap içində əsas əməliyyatların (get, put, remove, containsKey) vaxt mürəkkəbliyi orta hesabla O(1)-dir.

Bu, açarın hash koduna görə müəyyən olunan hüceyrələrdə (kassalarda) elementlərin saxlanması ilə təmin edilir. İdeal halda, hər kassada yalnız bir element olur.

Lakin, ən pis halda, bütün açarların eyni hash kodu olması və ya çox sayda toqquşma baş verdikdə, elementlər eyni kassaya düşür. Bu halda, kassalar bağlı siyahıya (Java 8-ə qədər) və ya ağaca (Java 8 və yuxarı, əgər kassadakı elementlərin sayı müəyyən həddən çoxdursa) çevrilə bilər. Belə bir kassada əməliyyatların vaxt mürəkkəbliyi O(n) olur, burada n həmin kassadakı elementlərin sayıdır.

HashMap sabit vaxtlı O(1) əldə etmə zəmanəti vermir. Yalnız orta hesabla O(1) vaxt mürəkkəbliyi təmin edir. Ən pis halda, mürəkkəblik O(n) ola bilər.

Vaxt mürəkkəbliyinə təsir edən amillər:

• Hash funksiyasının keyfiyyəti: Yaxşı hash funksiyası açarları bərabər şəkildə paylayır və toqquşmaları minimuma endirir.
• load factor (yük dərəcəsi): Hash cədvəlinin nə qədər dolu ola biləcəyini və onun ölçüsünün artırılmasını (rehash) təyin edir. Yüksək load factor toqquşma ehtimalını artırır.
• İlkin tutum: Çox kiçik ilkin tutum çox sayda elementlə tez-tez rehash əməliyyatlarına səbəb olur ki, bu da resurslara ağır yüklənmədir.