HashMap операцияларынын убакытттык татаалдыгы коллекциянын өлчөмүнө пропорционалдуу болгон шарттар кандай?

HashMapтогу операциялар (мисалы, get, put) адатта амортизирленген убакыт татаалдыгы O(1) болот. Бирок кээ бир учурларда, татаалдык O(n)га чейин өсүшү мүмкүн, анда n жыйымдын өлчөмү. Бул төмөнкүдөй болот:

• Бардык ачкычтар жаман хеш функциясы аркылуу бир кутуга (bucket) түшүп калса, бул узун тизме же даракка алып келет.
• Коллизиялар бирдей бөлүштүрүлбөйт жана маалымат структурасы ичиндеги деградацияга учурайт.

Java 8 жана андан кийинки версияларда, эгер бир кутуда өтө көп элементтер болсо, HashMap байланышкан тизмені тепкичтүү даракка (TreeNode) айлантат, бул эң жаман учурду O(log n)га азайтат, бирок O(1)га эмес.

Ошондуктан, операциялар жыйымдын өлчөмүнө пропорционалдуу болуп калат, күчтүү коллизиялар жана жаман хеш бөлүштүрүү учурларында.