HashMap-də toqquşmalar mövcud olduqda açar ilə elementin axtarışının effektivliyi necə qiymətləndirilir?

HashMap içində, açar ilə element axtarışı orta hesabla O(1) vaxtda həyata keçirilir, lakin toqquşmalar mövcud olduqda, səmərəlilik onların idarə olunma üsulundan asılıdır.

Əvvəllər, toqquşmalar zəncirlər (bir-birinə bağlı siyahılar) vasitəsilə idarə olunurdu və ən pis halda (bütün açarların eyni səbətə düşməsi ilə) axtarış O(n) olurdu.

Java 8-dən başlayaraq, əgər bir səbətdəki elementlərin sayı müəyyən bir həddi aşarsa, bağlı siyahı balanslı ağaca (məsələn, qırmızı-qaranlıq ağac) çevrilir. Bu, həmin səbət üçün ən pis axtarış vaxtını O(log n) səviyyəsinə çatdırır.

Buna görə:

• Kiçik toqquşmalar ilə axtarış O(1)-ə yaxın qalır.
• Çox toqquşma olan səbətdə axtarış O(log n) olacaq.

Bu təkmilləşdirmə HashMap-in performansını əlverişsiz ssenarilərdə əhəmiyyətli dərəcədə artırır.