Hash таблицасына элемент кошуу операциясынын убакыттык татаалдыгын кантип баалоо кылса болот?

Хеш таблицасына элемент кошуу убакыттык татаалдыгы орто эсеп менен O(1) — туруктуу убакыт. Бул ачкыч үчүн хеш функциясын эсептеп жана элементти тиешелүү кутуга (бакетке) салуу аркылуу жетишилет.

Бирок, эң жаман учурда, көптөгөн кагылышуулар болуп, бардык элементтер бир кутуга түшүп калганда (мисалы, жаман хеш функциясы же жогорку жүктөө коэффициенти себептүү), татаалдык O(n) чейин төмөндөйт, анда n — таблицадагы элементтердин саны.

Ийкемдүүлүктү сактоо үчүн, адатта, кагылышууларды чечүү ыкмалары (зинденүү, ачык дарегдөө) жана таблицаны динамикалык кеңейтүү колдонулат, белгилүү бир жүктөө коэффициентине жеткенде.