Hash jadvali nima?

Hash-jadval (yoki assotsiativ massiv, lug‘at) — bu ma’lumotlar tuzilmasi bo‘lib, assotsiativ massiv interfeysini amalga oshiradi, ya’ni u "kalit-qiymat" juftlarini saqlash va kalit bo‘yicha qiymatni tez topish imkonini beradi.

Ishlash prinsipi hash-funksiyadan foydalanishga asoslangan bo‘lib, u kalitni indeks (hash) ga aylantiradi, bu indeks massiv (yoki bucket) ichida joylashgan.

Asosiy operatsiyalar:

1. Qo‘shish: Kalitning hash qiymati hisoblanadi va "kalit-qiymat" jufti mos bucketga joylashtiriladi.
2. O‘chirish: Kalitning hash qiymati hisoblanadi, mos bucket topiladi va juft o‘chiriladi.
3. Qidirish: Kalitning hash qiymati hisoblanadi, mos bucket topiladi va qidirilayotgan kalitga ega juft qidiriladi.

Hash-jadvalar o‘rtacha yuqori ishlash ko‘rsatkichlarini ta’minlaydi; qo‘shish, o‘chirish va qidirish operatsiyalari uchun ($O(1)$) ideal holatda. Biroq, eng yomon holatda (ko‘p koliziyalar bo‘lsa, ya’ni turli kalitlar bir xil indeksga aylansa), ishlash ko‘rsatkichi $O(n)$ ga tushishi mumkin.

Koliziyalarni hal qilish uchun turli strategiyalar mavjud:

• Zanjir usuli (Separate Chaining): Har bir bucketda, bir xil hashga ega elementlar ro‘yxati (masalan, bog‘langan ro‘yxat) saqlanadi.
• Ochiq manzilga olish (Open Addressing): Koliziya yuzaga kelganda, bo‘sh joy qidirish uchun oldindan belgilangan algoritm (chiziqli, kvadratli sondirish va boshqalar) qo‘llanadi.

Konseptual misol (soddalashtirilgan):

// Soddalashtirilgan hash-funksiyaning misoli
function simpleHash(key, size) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = (hash << 5) + hash + key.charCodeAt(i);
    hash = hash & hash; // 32-bitga aylantirish
  }
  return Math.abs(hash) % size;
}

class HashTable {
  constructor(size = 100) {
    this.size = size;
    this.buckets = new Array(size).fill(null).map(() => []); // Zanjir usuli
  }

  insert(key, value) {
    const index = simpleHash(key, this.size);
    // Kalit mavjudligini tekshirish va qiymatni yangilash
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index][i][1] = value;
        return;
      }
    }
    this.buckets[index].push([key, value]);
  }

  get(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        return this.buckets[index][i][1];
      }
    }
    return undefined; // Kalit topilmadi
  }

  delete(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index].splice(i, 1);
        return true; // Muvaffaqiyatli o‘chirildi
      }
    }
    return false; // Kalit topilmadi
  }
}

// Foydalanish
const myHashTable = new HashTable(50);
myHashTable.insert("apple", 10);
myHashTable.insert("banana", 20);
console.log(myHashTable.get("apple")); // 10
myHashTable.delete("banana");
console.log(myHashTable.get("banana")); // undefined

JavaScriptda obyektlar ({}) va xaritalar (Map) hash jadvalining misollari hisoblanadi. Map ko‘pincha afzalroq, chunki u har qanday turdagi kalitlarni qo‘llab-quvvatlaydi va kiritish tartibini saqlaydi.

Yaxshi hash-funksiyaning xususiyatlari:

• Tez hisoblash.
• Turli kalitlar uchun teng taqsimot.
• Koliziyalarni minimallashtirish.