Чӣ гуна вақт барои амалиётҳо дар унсурҳои HashMap, ва оё HashMap кафолат медиҳад, ки вақт дар интихоби унсур муайян шудааст?

Вақтли мураккаблик асосий амалиятлар (get, put, remove, containsKey) HashMapда ўртача O(1) бўлиб, бу хеш-таблицадан фойдаланиш орқали амалга оширилади, у ерда элементлар калитнинг хеш-коди билан белгиланган ўринларда (бақаларда) сақланади. Идеал ҳолда, ҳар бир бақада биргина элемент бўлади.

Лекин, энг ёмон ҳолда, барча калитлар бир хил хеш-кодга эга бўлса ёки кўп коллизиялар юз берса, элементлар бир хил бақада жамланади. Бундай бақа узунроқ боғланган рўйхатга (Java 8 гача) ёки дарахтга (Java 8 ва ундан юқори, агар бақадаги элементлар сони белгиланган чегарадан ошса) айланиши мумкин. Бундай ҳолда амалиятлар вақт мураккаблиги O(n) бўлиб, бу ерда n — бақадаги элементлар сони.

HashMap ҳеч қандай барқарор вақт мураккаблиги O(1)ни кафолатламайди. У фақат ўртача O(1)ни кафолатлайди. Энг ёмон ҳолда, мураккаблик O(n) бўлиши мумкин.

Вақт мураккаблигини таъсир қилувчи омиллар:

• Хеш-функциянинг сифатлари: Яхши хеш-функция калитларни тенг равишда тарқатади, коллизияларни минималлаштиради.
• load factor (юкламаслик коэффициенти): Хеш-таблица қанчалик тўлса, шунчалик кўп rehash амалга оширилади. Юқори load factor коллизия эҳтимолини оширади.
• Бошланғич ҳажм: Жуда кичик бошланғич ҳажмда кўп элементлар бўлса, кўп қайтадан ҳажмни ошириш (rehash) талаб қилинади, бу ресурслардан кўп фойдаланишга олиб келади.