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

Ҳаш таблицасига элемент қўшиш вақти одатда амортизирланган O(1) деб баҳоланади, яъни қўшиш ўртачада доимий вақт олади.

Бу қуйидагилар орқали амалга оширилади:

• Индексни аниқлаш учун тез ҳисобланган хеш-функция.
• Масив ҳужайрасига тез кириш.

Бироқ, энг ёмон ҳолда (масалан, коллизиялар бўлганда, бир неча калитлар бир хил қутига тушса) қўшиш O(n) га деградировать қилиши мумкин, агар коллизияларни сақлаш учун боғланган рўйхатдан фойдаланилса.

Замонавий амалга оширишлар (масалан, Java HashMap) кўп коллизиялар бўлганда мувозанатли дарахтларга ўтади, бу эса энг ёмон ҳолатни O(log n) га камайтиради.

Шунинг учун, вақт сарфи хеш-функциянинг самарадорлигига, коллизиялар сонига ва коллизияларни ҳал қилиш учун ишлатилган маълумотлар тузилмасига боғлиқ.