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

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

საფეხურები:

ჰეშის გამოთვლა: მოცემული საკლავისთვის გამოთვლილია ჰეში:
```
<?php
$key = "example";
$hash = crc32($key); // მარტივი ჰეშ-ფუნქციის მაგალითი
```
ინდექსის განსაზღვრა: ჰეში გარდაიქმნება მასივის ინდექსად, ჩვეულებრივ მასივის ზომის მოდულო ოპერაციით:
```
<?php
$arraySize = 10;
$index = $hash % $arraySize;
```
კაფში წვდომა: გამოთვლილი ინდექსით ხდება შესაბამის კაფში წვდომა მასივში:
კოლიზიების გადაჭრა: რადგან სხვადასხვა საკლავი შეიძლება ჰქონდეს ერთნაირი ჰეში (კოლიზია), კაფში შეიძლება იყოს რამდენიმე "საკლავი-მნიშვნელობის" წყვილი. კოლიზიების გადაჭრის სხვადასხვა მეთოდებია:
- საკაბელო მეთოდი (Separate Chaining): თითოეულ კაფში ინახება სია (მაგ., დაკავშირებული სია) "საკლავი-მნიშვნელობის" წყვილებისა, რომელთა ჰეშები ემთხვევა.
- გახსნილი მისამართის მეთოდი (Open Addressing): კოლიზიის შემთხვევაში, ხდება თავისუფალი უჯრის ძებნა მასივში გარკვეული წესით (გრძივი, კვადრატული, ორჯერადი ჰეშირება).

ოპერაციები:

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

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

სწრაფი წვდომა ელემენტებზე (საშუალოდ O(1)).
ეფექტიანი მეხსიერების გამოყენება.

მკაცრებები:

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