რა არის HashMap-ის ელემენტებზე ოპერაციების დროითი სირთულე, და უზრუნველყოფს კი HashMap მითითებულ სირთულეს ელემენტის არჩევისას?

HashMap ძირითადი ოპერაციების (get, put, remove, containsKey) დროის სირთულე საშუალოდ არის O(1).

ეს მიღწეულია ჰეშ-ტაბლოს გამოყენებით, სადაც ელემენტები ინახება უჯრებში (კასეტებში), რომლებიც განსაზღვრულია გასაღების ჰეშ-კოდით. იდეალურ შემთხვევაში, თითოეულ კასეტაში მხოლოდ ერთი ელემენტი იქნება.

თუმცა, ყველაზე უარესი შემთხვევა, როდესაც ყველა გასაღებს აქვს ერთნაირი ჰეშ-კოდი ან ხდება ბევრი კოლიზია, ელემენტები ერთსა და იმავე კასეტაში ხვდებიან. ამ შემთხვევაში, კასეტა შეიძლება გარდაიქმნას დაკავშირებულ სიად (Java 8-მდე) ან ხეად (Java 8 და ზევით, თუ კასეტაში ელემენტების რაოდენობა გადის გარკვეულ ზღვარს). ასეთ კასეტაზე ოპერაციები დროის სირთულით იქნება O(n), სადაც n არის ამ კასეტაში ელემენტების რაოდენობა.

HashMap არ გარანტირებს მუდმივ დროში სირთულეს O(1) ელემენტის მოძიებისას. მხოლოდ საშუალო O(1) სირთულეს გარანტირებს. ყველაზე უარესი შემთხვევა შეიძლება იყოს O(n).

დროის სირთულეზე გავლენას ახდენს:

• ჰეშ-ფუნქციის ხარისხი: კარგი ჰეშ-ფუნქცია თანაბრად განაწილებს გასაღებს კასეტებში, მინიმუმამდე ამცირებს კოლიზიებს.
• load factor (დაწოლა ფაქტორი): განსაზღვრავს, რამდენად შეიძლება იყოს სავსე ჰეშ-ტაბლო, სანამ მისი ზომა გაიზრდება (rehash). მაღალი load factor ზრდის კოლიზიების ალბათობას.
• საწყისი მოცულობა: ძალიან მცირე საწყისი მოცულობა, დიდი რაოდენობით ელემენტებით, გამოიწვევს ხშირ rehash-ებს, რაც რესურსების ხარჯია.