Hash-таблица кантип иштейт?

Хеш-таблица (hash table) — бул маалымат структурасы, ал ассоциативдүү массивди ишке ашырат.

Ишке ашыруу принциби:

1. Хештөө. Ар бир ачкыч (key) үчүн хеш-код (hash code) хеш-функция (hash function) аркылуу эсептелет. Хеш-код — бул бүтүн сан.
2. Индекстеүү. Хеш-код массивдин (же вектордун) ички структурасындагы индексти (index) аныктоо үчүн колдонулат. Адатта, индекс hash_code % array_size түрүндө эсептелет, анда array_size — массивдин өлчөмү.
3. Сактоо. Табылган индекс боюнча массивде ачкычка байланышкан мааниси (value) сакталат.

Маселелер жана алардын чечимдери:

• Коллизиялар. Төртүнчү ачкычтар бирдей хеш-кодду жана, демек, бирдей индексин массивде бере алат. Бул коллизия деп аталат.
  • Коллизияларды чечүү ыкмалары:
    • Өзүнчө чынжырлоо (Separate Chaining): Ар бир массив клеткасында "ачкыч-маани" парларынын тизмеги (же вектору жана башка) сакталат. Коллизия болсо, жаңы пар ошол тизмекке кошулат. Идеалдуу издөөдө, тиешелүү тизмек каралат жана керектүү ачкыч табылат.
    • Ачык дарбазалоо (Open Addressing): Коллизия болсо, башка бош клетка белгиленген эрежеге ылайык изделет (пробирүү).
      • Линейдүү пробирүү (Linear Probing): index + 1, index + 2 жана башка клеткелер текшерилет, массивдин өлчөмү боюнча модул менен.
      • Квадраттык пробирүү (Quadratic Probing): index + 1^2, index + 2^2 жана башка клеткелер текшерилет, массивдин өлчөмү боюнча модул менен.
      • Двойной хештөө (Double Hashing): Экинчи хеш-функция колдонулат, пробирүү кадамын аныктоо үчүн.

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

• Орточо учурда, кошуу, өчүрүү жана издөө операциялары O(1) убакытта ишке ашат.

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

• Эң начар учурларда (мисалы, көп коллизиялар же начар хеш-функция) операциялардын убактысы O(n) жетиши мүмкүн, анда n — элементтер саны.
• Кошумча эс тутуму талап кылынат (мисалы, чынжырлар үчүн же ачык дарбазалоо үчүн пробирүү).

C++ колдонуу мисалы (std::unordered_map):

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    // Хеш-таблица түзүү (unordered_map)
    std::unordered_map<std::string, int> курак;

    // Элементтерди кошуу
    курак["Alice"] = 30;
    курак["Bob"] = 25;
    курак["Charlie"] = 35;

    // Ключ боюнча маанини алуу
    std::cout << "Aliceдин курагы: " << курак["Alice"] << std::endl;

    // Элементти издөө
    if (курак.count("Bob")) {
        std::cout << "Bob картта бар." << std::endl;
    }

    // Элементти өчүрүү
    курак.erase("Charlie");

    return 0;
}