Հեշ-թերթի աշխատանքի արագությունը ինչ է?

Հեշ-տախտակի աշխատանքի արագությունը կամ տվյալների մուտքի ժամանակը (փնտռում, ավելացում, հեռացում), իդեալային դեպքում, հանդիսանում է O(1) — հաստատուն։

Սա հասնում է հեշ-ֆունկցիայի օգտագործմամբ, որը արագ փոխում է բանալիին զանգվածի ինդեքս։

Իրական արագությունը կախված է հետևյալից՝

• Հեշ-ֆունկցիայի որակից: Լավ ֆունկցիան հավասարաչափ տարածում է բանալիները, նվազեցնելով բախումները։
• Բախումների լուծման ռազմավարություններից՝
  • Արժեքների առանձին շղթա (separate chaining): Բախումի դեպքում, նույն հեշով տարրերը պահվում են կապված ցանկում կամ այլ դինամիկ զանգվածում։ Հասանելիության ժամանակը կարող է լինել O(N) ամենավատ դեպքում (բոլոր տարրերը մեկ «խցիկում»), որտեղ N տարրերի քանակն է։
  • Բաց հասցեագրման (open addressing): Բախումի դեպքում, որոնվում է հաջորդ ազատ բջիջը զանգվածում։ Հասանելիության ժամանակը կարող է վատթարանալ շատ բախումների դեպքում։
• Բեռնման գործակիցը (load factor): Տարրերի քանակի և հեշ-տախտակի չափի հարաբերակցությունը։ Բարձր բեռնման գործակիցը մեծացնում է բախումների հավանականությունը և դանդաղեցնում աշխատանքը։ Երբ հասնում է որոշակի շեմի, անհրաժեշտ է վերահաշվարկ (rehashing), ինչը բավականին թանկ գործառնություն է (O(N))։

Արդյունքում, թեև տեսականորեն արագությունը O(1) լավագույն դեպքն է, գործնականում այն կարող է մի փոքր բարձր լինել բախումների և վերահաշվարկի անհրաժեշտության պատճառով, հատկապես մեծ տվյալների քանակի կամ ոչ օպտիմալ հեշ-ֆունկցիաների դեպքում։