Sobes.tech
Intervyu yordami
Resurslar
Intervyuga tayyorgarlik
Resurslar
Ish qidirish
Resurslar
Huquqiy
Savollarga qaytish
Middle

unordered_map konteynerida hash jadvali qanday tuzilgan?

sobes.tech AI

AIdan javob

C++ da unordered_map sifatida hash jadvali sifatida amalga oshiriladi.

Ishlash prinsipi:

  1. Hashlash: Kalit butun son — hash kodi — hash funktsiyasi yordamida o'zgartiriladi.
  2. Indeksatsiya: Hash kodi indeksni (kova yoki bucket) aniqlash uchun ishlatiladi, bu indeks pointerlar yoki ro'yxatlardan iborat massivda joylashgan.
  3. Saqlash: Har bir kovada kalit-qiymat juftliklari saqlanadi.

Xususiyatlar:

  • Kovalar: Hash jadvali kovalar massividan iborat. Kovalar soni dinamik ravishda o'zgarishi mumkin (rehashing) belgilangan yuklama koeffitsienti oshganda.
  • Kollisionlar: Turli kalitlar bir xil hash kodini berishi mumkin. Bu kollision deb ataladi. Kollisionlarni hal qilish uchun unordered_map zanjirlash usulidan foydalanadi: bir xil hashga ega elementlar mos keladigan kovada bog'langan ro'yxatga (yoki boshqa ma'lumotlar tuzilmasiga) qo'shiladi.
  • Hash funktsiyasi va taqqoslash funktsiyasi: To'g'ri ishlashi uchun ikki narsa kerak:
    • Kalitlarni kovalar bo'ylab teng ravishda taqsimlaydigan yaxshi hash funktsiyasi, kollisionlarni minimallashtirish uchun.
    • == operatori yordamida kalitlarni ajratib turadigan tenglik funktsiyasi.
  • Performans: O'rtacha, qo'shish, o'chirish va qidirish operatsiyalari O(1) vaqt murakkabligiga ega. Eng yomon holatda (masalan, ko'p kollisionlar yoki yomon hash funktsiyasi tanlangan bo'lsa) performans O(n) ga pasayishi mumkin, bu yerda n elementlar soni.

Element qo'shish jarayoni:

  1. Kalitning hash kodi hisoblanadi.
  2. Kovadagi indeks aniqlanadi: bucket_index = hash(key) % num_buckets.
  3. Kalit-qiymat juftligi shu kovadagi ro'yxatga qo'shiladi. Agar kalit oldindan mavjud bo'lsa, qiymat yangilanadi.

Element qidirish jarayoni:

  1. Kalitning hash kodi hisoblanadi.
  2. Kovadagi indeks aniqlanadi.
  3. Bu kovadagi ro'yxat bo'ylab o'tiladi, kalitlar == operatori yordamida solishtiriladi.

Rehashing, elementlar soni kovalar soniga nisbatan belgilangan chegarani (yuklama koeffitsienti) oshganda amalga oshiriladi. Rehash qilish jarayonida, yangi, kattaroq kovalar massivini yaratish va eski kovalardagi barcha elementlarni qayta hash qilish va yangi joylarga ko'chirish amalga oshiriladi.

OldingiKeyingi