ჰეშ-ცხრილის მუშაობის სიჩქარე რა არის?

ჰეშ-ცხრილის მუშაობის სიჩქარე, ან მონაცემებზე წვდომის დრო (ძებნა, დამატება, წაშლა), იდეალურ შემთხვევაში არის O(1) — კონსტანტული.

ეს მიღწეულია გამოყენებით ჰეშ-ფუნქციის, რომელიც სწრაფად გარდაქმნის გასაღებს მასივის ინდექსად.

რეალური სიჩქარე დამოკიდებულია:

• ჰეშ-ფუნქციის ხარისხზე: კარგი ფუნქცია თანაბრად განაწილებს გასაღებს, მინიმუმამდე დაიყვანს კოლიზიებს.
• კოლიზიების გადაჭრის სტრატეგიებზე:
  • საყოფაცხოვრებო ჯაჭვი (separate chaining): კოლიზიის შემთხვევაში, ერთსა და იმავე ჰეშის მქონე ელემენტები ინახება დაკავშირებულ სიაში ან სხვა დინამიკურ მასივში. წვდომის დრო შეიძლება იყოს ყველაზე უარესი შემთხვევა O(N) (ყველა ელემენტი ერთ "კასრში"), სადაც N ელემენტების რაოდენობაა.
  • ღია მისამართი (open addressing): კოლიზიის დროს, ეძებს შემდეგ თავისუფალ უჯრას მასივში. წვდომის დრო შეიძლება გაუარესდეს ბევრი კოლიზიის დროს.
• ჩატვირთვის ფაქტორი (load factor): ელემენტების რაოდენობის და ჰეშ-ცხრილის ზომის შეფარდება. მაღალი ჩატვირთვის ფაქტორი ზრდის კოლიზიების ალბათობას და აჩერებს მუშაობას. როდესაც მიაღწევს გარკვეულ ზღვარს, საჭიროა რეჰეშინგი (rehashing), რაც შედარებით ძვირი ოპერაციაა (O(N)).

ამიტომ, თეორიულად, O(1) სიჩქარე საუკეთესო შემთხვევაა, პრაქტიკაში კი შეიძლება იყოს ცოტა მაღალი, კოლიზიებისა და რეჰეშინგის საჭიროების გამო, განსაკუთრებით დიდი მონაცემთა მასივთან ან არასრულყოფილ ჰეშ-ფუნქციებთან მუშაობისას.