Hash map

Hashmap - bu malumot saqlanadigan data stucte

biz buni goda ishaltganmiz

hashMap := map[string]string{
    "name": "Otabek",
    "job":  "Developer",
}

mana shunday Hash map qanday ishlaydi hashmap value va keydan tashkil topgan data structe

keltirilgan misolda key = name yoki job value Otabek yoki Developer

hashmap malumot saqlayotganida keyni hashlaydi misol uchun name = 99586 boladi va uni 10 ga bolib qoldiqni oladi, nima uchun ?

uni qaysi orinda turishini bilish uchun unga bucket index berishi kerak shuning uchun 10 ga bolingandagi qoldiq uning osha saqlanayotgan malumotning indexi boladi

Shu orinda savol tugiladi. bir xil bucket index bob qolsa unda nima boladi masalan

name = 99586 % 10 = 6

job = 583856 % 10 =6

10 ga bolish soddaroq chunish uchun aslida

Hash function keydan hash qiymat hosil qiladi va shu hash orqali qaysi bucketga tushishi aniqlanadi.

yani ikkala qiy,matning ham bucket indexlari 6 bolib qoldi yani bir joyga togri kelib qoldi, bunday xolatda Linked List bizga yordamga keladi

Linked list haqida bilmasangiz buyerda

Xozirgi vaziyatda bizda name va job bir joyga togri keldi va endi unida biz oshayegra saqlashimiz kerak

unday bolsa

linked lsitda saqlaymiz yani har bir name va job nodelar boladi, bir biriga boglanadi

maslan 6 indexdagi jobni olish uchun dastlab index 6 ga kelinadi va uning ichidan linked listdan key orqali malumot izlanadi va olinadi

Hash mapning avfzalliklaridan undagi amaliyotlar insert, delete lar uchun O(1) vaqt ketadi yani time complesity 1 ga teng bu juda tez degani

Search → O(1) average

Insert → O(1) average

Delete → O(1) average

Lekin juda kop collision bolib qolsa O(n) bolbi qolish ehtimoli bor

Masalan oddiy capacity li biror arraydan masalan index 5 malumotni ochirish kerak bolsa

uni ochiradi va arryadagi tartibni saqlash uchun malumotlarni qayta joylashtiradi

yana bir farqlardan biri, tasavur qilaylik resize hodisasi, biror array tolib qoldi lekin unga yana malumot qoshish kerak

insert bolishi kerak lekin hajm yetmaydi shunda array resize boladi va nusxa olinib eski arraydan malumotlar kochiriladi manashuyerda muhim nuqta bor, eski malumotlar ozlarining eski indexlari boyicha kochadi

Otabek ning indexsi arrayda 6 bolgan bolsa 6 bolib kochadi

Hashmapda esa butunlay boshqacha unda har bir bucket index qaytadan beriladi, chunki capacity ozgaradi, yani hashlangan keylarni bolishimiz kerak bolgan son ozgaradi bu esa yangi bucket indexlarni hosil qiladi

shunday )