Хеш таблицасы кандай иштейт?

Хеш-таблица (же ассоциативдүү массив) "ключ-баа" парларын сактайт. Иштөө принциби хеш-функцияны колдонууга негизделген, ал ключту сандык индекске (хешке) айлантат, ал массивде (корзинада) сакталган бааны көрсөтөт.

Адамдар:

1. Хешти эсептөө: берилген ключ үчүн хеш эсептелет:

   <?php
   $key = "example";
   $hash = crc32($key); // Жөнөкөй хеш-функциянын мисалы
   

2. Индекстин аныктоо: Хеш массивдин өлчөмүнө карата модул операциясы аркылуу массивдин индексине айланат:

   <?php
   $arraySize = 10;
   $index = $hash % $arraySize;
   

3. Корзинага жетүү: Эсептелген индекс боюнча массивдеги тиешелүү корзинага жетүү.
4. Коллизияларды чечүү: Эки башка ключ бирдей хешке ээ болушу мүмкүн (коллизия), ошондуктан корзинада бир нече "ключ-баа" парлары болушу мүмкүн. Коллизияларды чечүү үчүн ар кандай ыкмалар колдонулат:
   • Жиптер ыкмасы (Separate Chaining): Ар бир корзинада "ключ-баа" парларынын тизмеги (мисалы, байланыштуу тизмек) сакталат, алардын хештери бирдей.
   • Ачык дарек ыкмасы (Open Addressing): Коллизия болсо, массивде бош орунду кайра издөөгө болот, белгилүү эрежеге ылайык (сызыктуу, квадратичное, эки жолу хештөө).

Операциялар:

• Кошуу: Ключтун хеши эсептелет, индекс аныкталат, жана "ключ-баа" пару тиешелүү корзинага коюлат. Коллизия болсо, ал тизмекке кошулат же бош орун изделет.
• Издөө: Ключтун хеши эсептелет, индекс аныкталат. Тиешелүү корзинада мааниде изделет. Жиптер ыкмасында элементтер тизмегин карап чыгат; ачык дарек ыкмасында тизмек аркылуу издөөнү жүргүзөт.
• Жок кылуу: Ключтун хеши эсептелет, индекс аныкталат. Тиешелүү корзинада табылып, ал пар жок кылынат.

Артыкчылыктары:

• Элементтерге тез жетүү (ортача O(1)).
• Эс тутумду эффективдүү колдонуу.

Кемчиликтери:

• Коллизиялар көп болсо, иштөө ылдамдыгы начарлайт.
• Таблица өлчөмү өзгөртүлүшү керек болушу мүмкүн (rehashing) эффективдүүлүктү сактоо үчүн.