Ma’lumotlarni xeshlash algoritmlari

Ma’lumotlarni xeshlash algoritmlari

Aytaylik, siz oziq-ovqat do'konida ishlaysiz. Qachon mijoz mahsulot sotib olsa, narxini kitobdan qidirish kerak bo’ladi. Agar kitob alifbosiz bo’lsa, bu sizga ko'p vaqt talab qilishi mumkin, olmani qidirish uchun har bir qatorni ko'rib chiqasiz. Birinchi bobdan har bir qatorni ko’rip chiqishingiz uchun szga O(n) vaqt kerak boladi. Agar kitob alifbo tartibida bo'lsa, siz tezroq qidirishingiz mumkin, olma narxini topish uchun ikkilik qidiruv. Bu ikkilik qidiruv uchun szga faqat O (log n) vaqtingizni talab qiladi.
Eslatib oʻtamiz, O(n) va O(log n) vaqtlari oʻrtasida katta farq bor!
Aytaylik, siz bir soniyada kitobning 10 qatorini ko'rishingiz mumkin. Bu yerga
oddiy qidiruv va ikkilik qidiruvni amalga oshirish uchun qancha vaqt kerak bo'ladi

Ikkilik qidiruv juda tez ekanligini allaqachon bilasiz. Ammo kassir sifatida, kitob saralangan bo'lsa ham, narsalarni kitobga qarab qidirish juda mushkul. Siz kitobdagi narsalarni qidirayotganingizda mijozning sabri tugab mijoz yoqotishingiz mumkin. Shuning uchun sizga haqiqatan ham barcha ismlar va narxlarni yod ololidgan do'st kerak bo’ladi.Keyin hech narsa qidirishingiz shart emas. Siz undan so'raysiz va u sizga javob darhol aytadi

Sizning do'stingiz Meggi sizga har qanday mahsulot uchun O(1) vaqt ichida narxni berishi mumkin, yo'q kitob qanchalik katta bo'lishidan qat'i nazar. U ikkilik qidiruvdan ham tezroq.
Massivdagi har bir element aslida ikkita elementdan iborat: biri bir turdagi nom ishlab chiqarish, ikkinchisi esa narx. Agar siz ushbu massivni nomi bo'yicha tartiblasangiz, siz
buyumning narxini topish uchun ikkilik qidiruvni amalga oshirishingiz kerak bo’ladi. Shunday qilib, siz O(log n) vaqtda elementlarni topishingiz mumkin . Lekin siz O (1) vaqtida narsalarni topmoqchisiz. Siz "Maggie“ni ishga olishni xohlaysiz. Bu erda xesh-funksiyalar kiradi
Xesh-funksiya - bu qayerda funksiyaga string jo’natib va ohiridan raqamlani olasiz.
Hash funksiya matnni takrorlanmas noyob songa o’tkazib beradi
Texnik terminologiyada biz xesh funktsiyasi "satrlarni raqamlarga xaritalaydi" deb aytardik.“
Xesh funksiyalarni turi ko’p
Yahshi Xesh funksiya belgilari:
Birxil matin uchun birxil son qaytaradi
Xar hil matin uchun xar hil son qaytaradi
Xesh funksiya sizga kerakli oraliqdagi soni qaytaradi
Misol uchun, siz "olma“ni qo'ysangiz va"4" ni qaytarib olasiz. Har safar "olma" ni qo'yganingizda "4" ni qaytarib olishingiz kerak.
U turli xil so'zlarni turli raqamlarga joylashtirishi kerak. Masalan, agar siz qo'ygan har qanday so'z uchun har doim "1" ni qaytarsa, xesh funktsiyasi yaxshi emas
Shunday qilib, xesh funktsiyasi satrlarni raqamlarga moslashtiradi. Bo’sh massiv bilan boshlimiz
Siz barcha narhlarni shu masivda saqlaymiz.APPLE narhidan boshlimiz.
‘APPLE’ xesh funksiyaga qo’ying
Xesh funktsiya “3”ni chiqaradi. Shunday qilib, keling, olma narxini massivdagi indeks 3 ga saqlaylik.
Kelila endi xesh funksiyaga “Milk” ni qo’shamiz.
Xesh funktsiya indeksni "0" qaytardi.
Keling, sut narxini 0 indeksida saqlaylik
Davom eting va oxir-oqibat butun massiv narxlarga to'la bo'ladi.
Endi bu arraydan qanday foydalanamiz.
Endi siz: "Hey, avakadoning narxi qancha?" Sizga kerak emas uni massivda qidiring. Faqat "avokado" ni hash funktsiyasiga kiriting.
u sizga narx indeksi 4 da saqlanganligini aytadi. Va, albatta,u erda.
u hash funktsiyasi narx saqlanadi aniq qaerda sizga aytadi, shuning uchun sizumuman izlashga hojat yo'q!
Xesh tables
Eng foydali va ko’p ishlatiladigan ma’lumotlar tuzilmasi
Aksar dasturlash tillarida tadbiq qilingan
Xsh maps
Maps
Dictinaries(Python)
Ehtimol, hech qachon xesh jadvallarini o'zingiz qo'llashingiz shart emas. Har qanday yaxshitil xesh jadvallari uchun dasturga ega bo'ladi. Siz yangi xesh jadvalini yaratishingiz mumkin.
Manabu ko’d python da yozilgan tayor xesh jadvali orqali biz malumotlarni shunday ko’rinishda kiritsak bas.
Xesh jadvalari qayerlarda ishlatiladi misol uchun rasmdagide Hardoyim foydalanadigan kontaktlarimizda ularda qanday foydalanilgan desangiz Kontakt sinxron tarzda nomer kiritilgan yani kontaktan ismini qidirsangiz nomerini osonlik bilan topishingiz mumkin. Bizga mashhur bo’lgan Facebook kabi sahifalarning user nik name qismida juda faol foydalaniladi Xesh funksiyani ichida faqat 1 malumot emas balki yana 1 xesh funksiya yozishimiz mumkin
Ishlatilishiga yana bir yahshi misollardan biri bu DNS serverlar. Kompyuterimizga biror havolani qidiruvga jo’natsak kompyutermiz uni chunmaydi shu sabab birinchi DNS serverga jonatib IP adresi olib
keyin kompyuterimizga qidiruvga beradi Shu ketma ketligni bajarib kompyuterimiz web serverdan ma’lumot ololadi.
Yana bir misolimiz yuqorida aytib
o’tganimizdek user namelar yani loginlari-miz noyob bo’lishi kerak.
Xesh jadvallar dasturlash sohasida keng foydalaniladi odata foydalanuvchilar va boshqa ma’lumotlar ham xesh jadvali orqali saqlanadi