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

Hash jadvallar va ularning asosiy ishlash prinsipi haqida gapiring.

sobes.tech AI

AIdan javob

Hash jadvali (hash xaritasi) — bu kalitlarni qiymatlarga xaritlaydigan ma'lumotlar tuzilmasi bo'lib, assotsiativ massivni amalga oshiradi.

Ishlash prinsipi:

  1. Hashlash: Har bir kalit uchun, hash-kod hisoblanadi — hash funktsiyasi yordamida belgilangan o'lchamdagi raqamli qiymat. Yaxshi hash funktsiyasi hash-kodlarni chiqish diapazonida teng taqsimlaydi.
  2. Indeksatsiya: Hisoblangan hash-kod, mos keladigan qiymat saqlanadigan massivdagi indeksni (joyni) aniqlash uchun ishlatiladi. Ko'pincha, hash(key) % array_size yakuniy indeksni beradi.
  3. Saqlash: Massivda, hisoblangan indeksda, (kalit, qiymat) jufti saqlanadi.
  4. Qidiruv: Kalit bo'yicha qiymatni topish uchun, kalitning hash-kodi yana hisoblanadi, indeks aniqlanadi va shu indeksdan qiymat olinadi.
  5. Koliziyalar: Turli kalitlar bir xil hash-kodga ega bo'lsa, yuzaga keladi. Koliziyalarni hal qilish uchun turli usullar mavjud:
    • Kuchli usul (Separate Chaining): Har bir massiv indeksida, u indeksga keladigan barcha (kalit, qiymat) juftlarini o'z ichiga olgan ro'yxat (yoki boshqa ma'lumotlar tuzilmasi) saqlanadi.
    • Ochiq manzil (Open Addressing): Koliziya yuzaga kelganda, ma'lum bir qoidaga muvofiq, massivda boshqa bo'sh joy qidiriladi (chiziqli sondirish, kvadrat sondirish, ikki marta hash qilish).

Afzalliklari:

  • O'rtacha, qo'shish, o'chirish va qidiruv operatsiyalari O(1) murakkablikda bo'ladi, agar hash funktsiyasi yaxshi va koliziyalar kam bo'lsa.

Kamchiliklari:

  • Eng yomon holatda, ishlash tezligi O(n) bo'lishi mumkin, agar barcha kalitlar bir xil indeksga hashlangan bo'lsa (masalan, yomon hash funktsiyasi yoki ko'p koliziyalar bilan).
  • Qo'shimcha xotira talab qilinadi, massiv va ehtimol, koliziyalarni hal qilish uchun.

Swiftda, hash jadvallari Dictionary turi bilan amalga oshiriladi.

// Swiftda Dictionary misoli
var myDictionary: [String: Int] = ["apple": 1, "banana": 2, "orange": 3]

// Kalit bilan kirish
let value = myDictionary["banana"] // Optional(2) oladi

// Qo'shish/yangilash
myDictionary["grape"] = 4 // Yangi juft qo'shadi
myDictionary["apple"] = 10 // "apple" kaliti uchun qiymatni yangilaydi

// O'chirish
myDictionary["orange"] = nil // "orange" kalitli juftni o'chiradi
OldingiKeyingi