Hash jadvali qanday ishlash prinsipi?

Hash jadvali (yoki assotsiativ massiv) "kalit-qiymat" juftlarini saqlaydi. Ishlash prinsipi hash funktsiyasidan foydalanishga asoslangan bo'lib, u kalitni raqamli indeksga (hash) aylantiradi va bu indeks qiymatning saqlash joyini ko'rsatadi.

Qadamlar:

Hash hisoblash: Berilgan kalit uchun hash hisoblanadi.

<?php
$key = "example";
$hash = crc32($key); // Oddiy hash funktsiyasi misoli

Indeks aniqlash: Hash odatda massivning o'lchamiga bo'linadi (modul operatsiyasi yordamida).
```
<?php
$arraySize = 10;
$index = $hash % $arraySize;
```
Kosaga kirish: Hisoblangan indeks yordamida massivdagi mos keladigan kosaga kirish.
Kolliziyalarni hal qilish: Turli kalitlar bir xil hashga ega bo'lishi mumkin (kolliziya), shuning uchun kosalar bir nechta "kalit-qiymat" juftlarini saqlashi mumkin. Kolliziyalarni hal qilish uchun turli usullar qo'llaniladi:
- Chaining (zanjirlash): Har bir kosada "kalit-qiymat" juftlarining ro'yxati saqlanadi.
- Ochiq manzil (Open Addressing): Kolliziya bo'lsa, bo'sh hujayrani qidirish uchun takroriy qidiruv amalga oshiriladi (lineer, kvadrat, ikki marta hash qilish).

Amallar:

Qo'shish: Kalitning hash qiymati hisoblanadi, indeks aniqlanadi va "kalit-qiymat" jufti mos kosaga joylashtiriladi. Kolliziya bo'lsa, ro'yxatga qo'shiladi yoki bo'sh joy qidiriladi.
Qidirish: Kalitning hash qiymati hisoblanadi, indeks aniqlanadi. Mos kosada kalit bo'yicha qiymat qidiriladi. Chaining usulida ro'yxat elementlari tekshiriladi; ochiq manzil usulida ketma-ket qidiruv amalga oshiriladi.
O'chirish: Kalitning hash qiymati hisoblanadi, indeks aniqlanadi. Mos kosada, kalit bo'yicha juftlik topiladi va o'chiriladi.

Afzalliklari:

Elementlarga tez kirish (o'rtacha O(1)).
Xotira samarali ishlatiladi.

Kamchiliklari:

Kolliziyalar ko'p bo'lsa, ishlash tezligi pasayishi mumkin.
Jadval o'lchami optimallashtirishni talab qilishi mumkin (rehashing).