Хеш-коллизияларды чечүүнүн кандай жолдору бар?

Өзүнчө чынжыр (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):

Белгилүү жүктөө коэффициентине жеткенде, жаңы, чоңураак хеш таблица түзүлөт.
Бардык элементтер эски таблицадан кайра хештелип, жаңысына киргизилет.

// Resize логикасынын мисалы
if (current_size / (double)table_size > max_load_factor) {
    // Ичке эки эселүү өлчөмдүү жаңы таблица түзүү
    // Бардык элементтер кайра хештелип, жаңы таблицага киргизилет
    // Эски таблица өчүрүлөт
}

Тандоо ыкмасы иштөө ылдамдыгына, эс тутумга, ишке ашыруу татаалдыгына жана күтүлгөн жүктөө коэффициентине көз каранды. Өзүнчө чынжыр ыкмасы адатта жөнөкөй жана жогорку жүктөө коэффициенти менен жакшы иштейт, бирок кошумча иштөө эс тутуму талап кылынат. Ачык дарек ыкмалары эс тутумду натыйжалуу колдонуп, бирок хеш функциянын тандоосуна жана "жыйналуу" көйгөйүнө сезимтал. Resize эффективдүүлүктү сактоо үчүн зарыл, эгерде элементтердин саны өссө.