Hash jadvali qanday ishlaydi?

Hash jadvali (hash table) — bu ma'lumotlar tuzilmasi bo'lib, assotsiativ massivni amalga oshiradi.

Ishlash prinsipi:

1. Hashlash. Har bir kalit (key) uchun hash-kod (hash code) hash funktsiyasi (hash function) yordamida hisoblanadi. Hash-kod butun son bo'lib,.
2. Indeksatsiya. Hash-kod yordamida hash jadvalining ichki strukturasi bo'lmish massivda (yoki vektor) indeks (index) aniqlanadi. Odatda, indeks hash_code % array_size formulasi bilan hisoblanadi, bu yerda array_size massivning o'lchami.
3. Saqlash. Topilgan indeksda, kalit bilan bog'langan qiymat (value) saqlanadi.

Muammolar va ularning yechimlari:

• Kolliziyalar. Turli kalitlar bir xil hash-kod berishi mumkin va, shuning uchun, bir xil indeksga ega bo'lishi mumkin. Bu kolliziya deb ataladi.
  • Kolliziya yechimlari:
    • Zanjir usuli (Separate Chaining): Har bir massiv hujayrasida "kalit-qiymat" juftlarining ro'yxati (ro'yxat, vektor va h.k.) saqlanadi. Kolliziya bo'lsa, yangi juft bu ro'yxatga qo'shiladi. Indeks bo'yicha qidirishda, mos ro'yxat tekshiriladi.
    • Ochiq manzil (Open Addressing): Kolliziya bo'lsa, ma'lum bir qoidaga (sondash) muvofiq, bo'sh hujayra qidiriladi.
      • Chiziqli sondash (Linear Probing): index + 1, index + 2, va h.k. hujayralar ketma-ket tekshiriladi, moduli bilan massiv o'lchamiga.
      • Kvadrat sondash (Quadratic Probing): index + 1^2, index + 2^2, va h.k. hujayralar tekshiriladi, moduli bilan massiv o'lchamiga.
      • Ikki marta hash (Double Hashing): Ikkinchi hash funktsiyasi yordamida qadam aniqlanadi.

Afzalliklari:

• O'rtacha holatda, joylashtirish, o'chirish va qidirish operatsiyalari O(1) murakkablik bilan amalga oshiriladi.

Kamchiliklari:

• Eng yomon holatda (masalan, ko'p kolliziya yoki yomon hash funktsiyasi bilan) operatsiyalar murakkabligi O(n) ga yetishi mumkin, bu yerda n elementlar soni.
• Qo'shimcha xotira talab qilinadi (masalan, zanjir usulida ro'yxatlar uchun yoki ochiq manzil usulida sondash uchun).

C++ da foydalanish misoli (std::unordered_map):

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

int main() {
    // Hash jadvalini yaratish (unordered_map)
    std::unordered_map<std::string, int> yosh;

    // Elementlar qo'shish
    yosh["Alice"] = 30;
    yosh["Bob"] = 25;
    yosh["Charlie"] = 35;

    // Kalit bo'yicha qiymatni olish
    std::cout << "Alice ning yoshi: " << yosh["Alice"] << std::endl;

    // Elementni qidirish
    if (yosh.count("Bob")) {
        std::cout << "Bob ro'yxatda." << std::endl;
    }

    // Elementni o'chirish
    yosh.erase("Charlie");

    return 0;
}