Төрдүү шарттарда элементти хеш таблицасына кошуу операциясынын эффективдүүлүгүн кантип баалоо кылуу керек?

Hash таблицасына элемент кошуу операциясынын натыйжалуулугу бир нече факторго көз каранды:

1. Жүктөө коэффициенти (load factor) — элементтердин саны менен массивдин өлчөмүнүн катышы. Төмөн жүктөөдө, кошуу адатта амортизирленген O(1) убакытта ишке ашат.

2. Hash функциясынын сапаты — ачкычтардын бирдей бөлүштүрүлүшү кагылыштарды минималдаштырат.

3. Кагылыштарды иштетүү:

   • Занжирлөө (chaining) менен кошуу — байланышкан тизме же башка контейнерге элемент кошуу. Орточо O(1), бирок эң начар учур O(n), эгер бардык элементтер бир эле занжирге түшсө.
   • Ачык дарекке жайгаштыруу (linear probing, quadratic probing) менен кошуу — бош орунду издөө талап кылынат, бул жогорку жүктөөдө убакытты көбөйтөт.

4. Rehashing — жүктөө чекитине жеткенде, таблица кеңейтилет, бул элементтерди кайра бөлүштүрүүнү талап кылат жана убактылуу кошуу убактысын көбөйтөт.

Кыскасы: жакшы hash функциясы жана орточо жүктөө менен, кошуу амортизирленген O(1). Жогорку жүктөө же жаман hash функциясы учурда убакыт O(n) чейин төмөндөйт.