რა გზები არსებობს ჰეშ-კოლიზიების გადაჭრისთვის?

საკავშირო ჯაჭვების მეთოდი (Separate Chaining):
- თითოეული ჰეშ-ცხრილის ელემენტი (ბაკეტი) წარმოადგენს კავშირით დაკავშირებული სიის (ან სხვა მონაცემთა სტრუქტურის, მაგალითად, ხის) მაჩვენებელს.
- ყველა ელემენტი, რომელიც ჰეშდება ერთ ბაკეტზე, ემატება ამ სიას.
```
// მაგალითი: კავშირით დაკავშირებული სიის ნული ჯაჭვებისათვის
struct Node {
    int key;
    int value;
    Node* next;
};

// ბაკეტში ინახება მაჩვენებელი სიის სათავეზე
Node* buckets[TABLE_SIZE];
```
გახსნილი მისამართების მეთოდები (Open Addressing):
- ყველა ელემენტი ინახება პირდაპირ ჰეშ-ცხრილში.
- კოლიზიის დროს ხდება შემდეგი თავისუფალი ადგილის ძიება მასივში.
- განასხვავებენ შემდეგი ადგილის განსაზღვრის მეთოდით:
  - გრძივი გამეორება (Linear Probing): იჩეკება უჯრედები თანმიმდევრობით ფიქსირებული ნაბიჯით i, i+1, i+2, ... mod TABLE_SIZE.
```
// გრძივი გამეორების მაგალითი
int hash(int key) { return key % TABLE_SIZE; }

int i = hash(key);
while (table[i] != EMPTY && table[i].key != key) {
    i = (i + 1) % TABLE_SIZE;
}
// ახლა table[i] ან ცარიელია, ან შეიცავს მოძებნულ ელემენტს
```
  - კვადრატული გამეორება (Quadratic Probing): იჩეკება უჯრედები ნაბიჯით, რომელიც დამოკიდებულია მცდელობის კვადრატზე i, i+1², i+2², ... mod TABLE_SIZE.
```
// კვადრატული გამეორების მაგალითი
int hash(int key) { return key % TABLE_SIZE; }

int i = hash(key);
int attempt = 0;
while (table[i] != EMPTY && table[i].key != key && attempt < TABLE_SIZE) {
    attempt++;
    i = (hash(key) + attempt * attempt) % TABLE_SIZE;
}
// ახლა table[i] ან ცარიელია, ან შეიცავს მოძებნულ ელემენტს (ან ცხრილი გადატვირთულია)
```
  - მეორე ჰეშირება (Double Hashing): გამოიყენება მეორე ჰეშ-ფუნქცია გამეორების ნაბიჯის განსაზღვრისთვის i, i + step, i + 2*step, ... mod TABLE_SIZE, სადაც step გამოითვლება მეორე ჰეშ-ფუნქციით კივისათვის.
```
// მეორე ჰეშირების მაგალითი
int hash1(int key) { return key % TABLE_SIZE; }
int hash2(int key) { return 1 + (key % (TABLE_SIZE - 1)); } // მეორე ჰეშ-ფუნქცია

int i = hash1(key);
int step = hash2(key);
while (table[i] != EMPTY && table[i].key != key) {
    i = (i + step) % TABLE_SIZE;
}
// ახლა table[i] ან ცარიელია, ან შეიცავს მოძებნულ ელემენტს
```

ზომის შეცვლის დინამიური მეთოდი (Resizing):

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

// მაგალითი ლოგიკის როდესაც საჭიროა რეზაიზი
if (current_size / (double)table_size > max_load_factor) {
    // შექმენით ახალი ორჯერ დიდი ზომის ცხრილი
    // გადახეშეთ და ჩასვით ყველა ელემენტი ძველ ცხრილში
    // წაშალეთ ძველი ცხრილი
}

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