#data_structure #c

Hash table

Dasturlashda ayrim hollarda ma'lumotlarni kalit (key) va qiymat (value) ko'rinishida o'zgaruvchan holatda saqlashga to'g'ri keladi. C'da static ko'rinishda va kaliti butun son ko'rishida saqlash imkoniyati mavjud:
typedef enum {
CAT = 0,
DOG,
ANIMALS_COUNT,
} Animals;

const char* animals[ANIMALS_COUNT] = {
[CAT] = "cat",
[DOG] = "dog",
};
Lekin bizga o'zgaruvchan hamda kalit uchun butun son emas string ishlatilishi kerak. C'da static holatda quyidagicha ifodalasa bo'ladi:
const char* animals[][2] = {
{ "cat", "ui ua ui ua" },
{ "dog", "what a dog doing?" },
};
Kalit orqali qiymatini topish uchun array'ni loop qilib va har bir kalitni berilgan kalit orqali solishtirib chiqishga to'g'ri keladi:
for (int i = 0; i < animals_count; i++) {
if (strcmp(animals[i][0], key) == 0) {
return animals[i][1];
}
}
Bu holatdan ko'rishingiz mumkinki funksiyanal O(n) tarzda ishlayapti. Biz uchun 1-misolda ko'rsatilganidek to'g'ridan-to'g'ri murojaat qiladigan hamda butun sondan emas string'dan foydalangan holda qiymat oladigan, funksiyanali O(1) ga teng bo'lgan data struktura kerak. Buning uchun bizga hash table data strukturasi yordam beradi.

Berilgan keyini hash funksiyasi orqali butun songa aylantirib, shu sonni array index'i sifatida foydalaniladi. Hash funksiyasi 1-rasmda berilgan.
- a ga harflar
- n harflar soni
- b to'qnashuvni oldini oladigan son (tub son)
- p hash table hajmi (tub son)
Bu formula orqali string harflaridan butun songa o'girishimiz mumkin.

To'qnashuv

Formula har doim ham har xil son qaytarmadi. Misol uchun "cat" so'zi bu formulaga asoslanib:
p = 53
b = 31
"cat" = (99, 97, 116)

(31**2 * 99 + 31**1 * 97 + 31**0 * 116) % 53 = 0
Xuddi shu formulani "ca\n" so'z bilan ishlatganda
"ca\n" = (99, 97, 10)

(31**2 * 99 + 31**1 * 97 + 31**0 * 10) % 53 = 0
Ko'rishingiz mumkinki ikkala holatda ham 0 qaytdi. Bu muamoni yechish uchun ikki marta hash qilish (Double hashing) orqali qilish mukin. Bundan tashqari chiziqli qidiruv (Linear probing) va kvadratli qidiruv (Quadratic probing) yo'llari mavjud.
Chiziqli qidiruvda urinishlarni qo'shish orqali:
h(k, i) = (h'(k) + i) mod m
Kvadratli qidiruvda:
h(k, i) = (h'(k) + c_1*i + c_2*i^2) mod m
Ikki marta hash qilish:
h(k, i) = (h_1(k) + i*h_2(k)) mod m
orqali qilinadi.

Bundan tashqari to'qnashuv bo'lganda list ko'rishda saqlash usuli ham mavjud. Tarkibi o'rnatilgan ma'lumot yoki NULL qiymatdan iborat bo'lgan o'zgaruvchan array bilan tuzilganga, ochiq murojaat qilish (Open addressing) deb ataladi.

Muamolar

Hash table har doim ham Hash table O(1) ishlamaydi. Eng yomon holatda O(n) ishlaydi. Lekin hash table qancha katta bo'lsa, shuncha to'qnashuvlar kam bo'ladi. To'qnashuvlar kamligi Hash table tezligiga ijobiy tasir qiladi.

Manba

github source code link

Qo'shimcha

Bu ma'lumotlarni izlash uchun "Introduction to Algorithms 3e" kitobidagi "Chapter 11" mavzusidan foydalanildi.