Хеш-таблица қалай жұмыс істейді?

Хеш-таблица (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> ages;

    // Элементтерді қосу
    ages["Alice"] = 30;
    ages["Bob"] = 25;
    ages["Charlie"] = 35;

    // Кілт бойынша мәнді алу
    std::cout << "Alice-дің жасы: " << ages["Alice"] << std::endl;

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

    // Элементті жою
    ages.erase("Charlie");

    return 0;
}