HashMap-ში ელემენტის ძიების სირთულე რა არის?

საშუალო სირთულე — O(1), ყველაზე უარესი შემთხვევა — O(n).

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

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