რა არის ჰეშ სია?

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

ძირითადი კომპონენტები:

• გასაღები: უნიკალური იდენტიფიკატორი ელემენტისთვის.
• მნიშვნელობა: მონაცემები, რომლებიც დაკავშირებულია გასაღებთან.
• ჰეშ-ფუნქცია: გარდაქმნის გასაღებს რიცხვობრივ მნიშვნელობას (ჰეშს), რომელიც გამოიყენება ინდექსის განსაზღვრაში.
• კორიზები (Buckets): მასივი, სადაც ინახება გასაღები-მნიშვნელობის წყვილები.
• კოლიზიების დამუშავება (Collision Handling): მექანიზმი სიტუაციების გადასაჭრელად, როდესაც სხვადასხვა გასაღებები იძლევა ერთსა და იმავე ჰეშს (და შესაბამისად, მიუთითებს ერთ კორიზზე). გავრცელებული მეთოდები:
  • ზოლების მეთოდი (Chaining): თითოეულ კორიზში ინახება სია (მაგალითად, დაკავშირებული სია) ელემენტების, ჰეშები რომ მიუთითებს ამ კორიზზე.
  • გახსნილი მისამართის მეთოდი (Open Addressing): კოლიზიის დროს ეძებს შემდეგ თავისუფალ კორიზს, იყენებს ალგორითმებს, როგორიცაა ლინეურქა, კვადრატული ან დუპლექს ჰეშირება.

სამუშაო პრინციპი:

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

   // ელემენტის ჩასმის მაგალითი ჰეშ-ცხრილში (ზოლების მეთოდი)
   function insert(key, value) {
     const hash = hashFunction(key); // ჰეშის გამოთვლა
     const bucketIndex = hash % tableSize; // კორიზის ინდექსის განსაზღვრა
   
     if (!buckets[bucketIndex]) {
       buckets[bucketIndex] = []; // სიის შექმნა, თუ ჯერ არ არსებობს
     }
     buckets[bucketIndex].push({ key, value }); // წყვილის დამატება სიისთვის
   }
   

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

   // ელემენტის ძიების მაგალითი ჰეშ-ცხრილში (ზოლების მეთოდი)
   function searchAndDelete(key) {
     const hash = hashFunction(key); // ჰეშის გამოთვლა
     const bucketIndex = hash % tableSize; // კორიზის ინდექსის განსაზღვრა
   
     if (buckets[bucketIndex]) {
       // ელემენტის ძიება კორიზის სიაში
       for (let i = 0; i < buckets[bucketIndex].length; i++) {
         if (buckets[bucketIndex][i].key === key) {
           const value = buckets[bucketIndex][i].value;
           // buckets[bucketIndex].splice(i, 1); // თუ საჭიროებს წაშლას
           return value; // მნიშვნელობის დაბრუნება
         }
       }
     }
     return undefined; // ელემენტი არ მოიძებნა
   }
   

უპირატესობები:

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

მოხერხებულობა:

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

JavaScript-ში ჰეშ-ცხრილები რეალიზებულია ინტეგრირებულ ობიექტ Map-ით და ისტორიულად Object-ით. Map არის სასურველი, რადგან საშუალებას აძლევს გამოიყენოს ნებისმიერი ტიპის მონაცემები გასაღებად და ინახავს დამატების წესს. Object გარდაქმნის ყველა გასაღებს სტრიქონებად.