HashMap-dən element əldə etməyin vaxt mürəkkəbliyi nədir, əgər içərisində qırmızı-qara ağac istifadə olunursa?

Java-da, versiya 8-dən başlayaraq, HashMap-də çox sayda to‘qnashuv (8 dan ortiq element) bo‘lsa, bucket ichidagi ro‘yxat qizil-oq daraxtga aylantiriladi va unumdorlik yaxshilanadi.

Bu holatda, HashMap-dan element olish vaqt murakkabligi, bog‘langan ro‘yxat ishlatilganda amortizatsiyalangan O(1) dan, daraxt chuqurligi bo‘yicha n ga teng bo‘lgan O(log n) ga o‘zgaradi.

Shuning uchun, bucket ichida qizil-oq daraxt ishlatilganda, elementni qidirish O(log n) da amalga oshiriladi.