რა არის დროის სირთულე HashMap-დან ელემენტის მიღებისას, თუ მისი შიგნით გამოიყენება წითელი-შავი ხე?

Java-да, ვერსია 8-დან იწყება, თუ HashMap-ის ბაკეტში ძალიან ბევრი კოლიზია (მეტი 8 ელემენტი), ბაკეტის შიგნით სია გარდაიქმნება წითელი-შავი ხე-სთვის უკეთესობისთვის.

ამ შემთხვევაში, HashMap-დან ელემენტის მიღების დროის სირთულე იცვლება ამორტიზებული O(1)-დან (რიგის გამოყენებით) O(log n)-მდე, სადაც n არის კონკრეტული ბაკეტის ელემენტების რაოდენობა (ანუ ხის სიღრმე).

ამიტომ, ბაკეტის შიგნით წითელი-შავი ხის გამოყენებით, ელემენტის ძიება ხორციელდება O(log n) დროში.