Hash jadvallar
Xesh jadvali
Xesh jadvali - bu tez ishlash uchun mo‘ljallangan ma’lumotlar tuzilmasi.
Ba’zan massivlar yoki bog‘langan listlar o‘rniga Xesh jadvallarini afzal ko‘rishining sababi shundaki, ma’lumotlarni qidirish, qo‘shish va o‘chirish juda tez, hatto katta hajmdagi ma’lumotlar uchun ham amalga oshirilishi mumkin.
Bog‘langan ro‘yxatda "Bob" ismli shaxsni topish vaqt talab qiladi, chunki biz "Bob" topilgunga qadar bitta tugundan keyingisiga o‘tib, har bir tugunni tekshirib chiqishimiz kerak bo‘ladi.
List yoki massivda indeksni bilsak "Bob"ni tez topish mumkin, lekin biz faqat "Bob" ismini bilganimizda, har bir elementni solishtirishimiz kerak va bu vaqt oladi.
Xesh-jadval yordamida "Bob" ni topish juda tez amalga oshiriladi, chunki to‘g‘ridan-to‘g‘ri "Bob" saqlanadigan joyga borishning yo‘li bor, bunda xesh funksiyasi deb ataladi.
Xesh jadvalini noldan qurish
Xesh jadvali nima ekanligini tushunish uchun keling, uni noldan yaratishga harakat qilaylik va uning ichida noyob ismlarni saqlashga harakat qilaylik.
Biz hash jadvalini 5 bosqichda quramiz:
- Bo‘sh list yarating (u dictionary yoki set ham bo‘lishi mumkin).
- Xesh funksiyasini yarating.
- Xesh funksiyasi yordamida elementni kiritish.
- Xesh funksiyasi yordamida elementni qidirish.
- Handling collisions.
1-qadam: Bo‘sh list yarating
Oddiy bo‘lishi uchun keling, 10 ta bo‘sh elementdan iborat list tuzamiz.
my_list = [None, None, None, None, None, None, None, None, None, None]
Ushbu elementlarning har biri Xesh jadvalidagi chelak deb ataladi.
2-qadam: Xesh funksiyasini yarating
Endi Hash jadvallari bilan o‘zaro ishlashning maxsus usuli keladi.
Biz nomni to‘g‘ridan-to‘g‘ri massivdagi kerakli joyga saqlamoqchimiz va bu yerda xesh funksiyasi kiradi.
Xesh funksiyasi ko‘p jihatdan amalga oshirilishi mumkin, bu Xesh jadvalini yaratuvchisiga bog‘liq. Umumiy usul bu qiymatni Xesh jadvalining indeks raqamlaridan biriga, bu holda 0 dan 9 gacha bo‘lgan raqamga teng keladigan raqamga aylantirish usulini topishdir.
Bizning misolimizda biz har bir belgining Unicode raqamidan foydalanamiz, ularni umumlashtiramiz va 0-9 indeks raqamlarini olish uchun modul 10 operatsiyasini qilamiz.
Misol
Har bir belgining Unicode raqamlarini yig‘adigan va 0 dan 9 gacha bo‘lgan raqamni qaytaradigan xash funksiyasi yarating:
def hash_function(value):
sum_of_chars = 0
for char in value:
sum_of_chars += ord(char)
return sum_of_chars % 10
print("'Bob' has hash code:", hash_function('Bob'))
O‘zingiz sinab ko‘ring »
ode>B belgisi Unicode raqami66, o111 va b belgisi 98. Ularni qo'shib, biz 275ni olamiz.275 modulining 10 moduli 5 ga teng, shuning uchun "Bob"5 indeksida saqlanishi kerak.
Xesh funksiyasi tomonidan qaytarilgan raqam xesh kodi deb ataladi.
Unicode raqami: Bizning kompyuterlarimizdagi hamma narsa raqamlar sifatida saqlanadi va Unicode kod raqami har bir belgi uchun mavjud bo‘lgan noyob raqamdir. Masalan, A belgisi 65 Unicode raqamiga ega.
Belgilar qanday raqamlar sifatida ifodalanishi haqida ko‘proq ma’lumot olish uchun ushbu sahifaga qarang.
Modulo: Moduli operatsiya raqamni boshqa raqamga ajratadi va natijada qoldiqni beradi. Masalan,7 % 3 bizga qolgan 1 ni beradi. (7 ta olmani 3 kishiga bo‘lish, har bir kishiga 2 ta olma bo‘ladi, 1 ta olma qoladi.)
Python va ko‘pgina dasturlash tillarida modolo operatori % sifatida yoziladi.
3-qadam: Elementni kiritish
Bizning hash funksiyamizga ko‘ra, "Bob" indeks 5 da saqlanishi kerak.
Xesh-jadvalimizga elementlar qo‘shadigan funksiya yarataylik:
Misol
def add(name):
index = hash_function(name)
my_list[index] = name
add('Bob')
print(my_list)
Misolni ishga tushirish »
"Bob" ni 5-indeksda saqlagandan so‘ng, bizning massivimiz endi shunday ko‘rinadi:
my_list = [None, None, None, None, None, 'Bob', None, None, None, None]
Xuddi shu funksiyalardan "Pite", "Jones", "Lisa" va "Siri" ni saqlash uchun ham foydalanishimiz mumkin.
Ushbu nomlarni to‘g‘ri holatda saqlash uchun xesh funksiyasidan foydalangandan so‘ng, bizning massivimiz quyidagicha ko‘rinadi:
Misol
my_list = [None, 'Jones', None, 'Lisa', None, 'Bob', None, 'Siri', 'Pete', None]
4-qadam: Ismni qidirish
Endi bizda juda oddiy xash jadvali bor, keling, undan qanday nom topish mumkinligini ko‘rib chiqamiz.
Xesh jadvalida "Pite" ni topish uchun biz hash funksiyamizga "Pite" nomini beramiz. Xesh funksiyasi 8 ni qaytaradi, ya’ni "Pit" indeks 8da saqlanadi.
Misol
def contains(name):
index = hash_function(name)
return my_list[index] == name
print("'Pete' is in the Hash Table:", contains('Pete'))
Misolni ishga tushirish »
"Pite" bor yoki yo‘qligini aniqlash uchun elementni element bo‘yicha tekshirishimiz shart emasligi sababli, biz to‘g‘ridan-to‘g‘ri to‘g‘ri elementga o‘tish uchun xesh funksiyasidan foydalanishimiz mumkin!
5-qadam: to‘qnashuvlarni qayta ishlash
Xesh jadvalimizga "Styuart" ni ham qo‘shamiz.
Biz hash funksiyamizga "Styuart" ni beramiz, u 3 ni qaytaradi, ya’ni "Styuart" indeks 3 da saqlanishi kerak.
"Styuart" ni 3-indeksda saqlashga urinish to‘qnashuv deb ataladigan narsani yaratadi, chunki "Liza" allaqachon 3-indeksda saqlangan.
To‘qnashuvni tuzatish uchun biz bir xil chelakda ko‘proq elementlarga joy ajratishimiz mumkin. To‘qnashuv masalasini shu tarzda hal qilish zanjir deb ataladi va bir xil chelakda ko‘proq elementlarga joy berishni anglatadi.
Asl list bilan bir xil o‘lchamdagi, lekin bo‘sh chelaklar bilan yangi list yaratishdan boshlang:
my_list = [
[],
[],
[],
[],
[],
[],
[],
[],
[],
[]
]
add() funksiyasini qayta yozing va oldingi kabi nomlarni qo‘shing:
Misol
def add(name):
index = hash_function(name)
my_list[index].append(name)
add('Bob')
add('Pete')
add('Jones')
add('Lisa')
add('Siri')
add('Stuart')
print(my_list)
Misolni ishga tushirish »
Har bir chelakni list sifatida qo‘llaganingizdan so‘ng, "Styuart" 3-indeksda ham saqlanishi mumkin va bizning hash to‘plamimiz endi shunday ko‘rinadi:
Natija
my_list = [
[None],
['Jones'],
[None],
['Lisa', 'Stuart'],
[None],
['Bob'],
[None],
['Siri'],
['Pete'],
[None]
]
"Styuart" ni qidirish endi biroz ko‘proq vaqt talab etadi, chunki biz "Liza" ni ham xuddi shu chelakda topamiz, lekin baribir butun Xesh jadvalini qidirishdan ko‘ra tezroq.
Xesh jadvallaridan foydalanish
Xash jadvallari quyidagilar uchun juda mos keladi:
- To‘plamda biror narsa bor yoki yo‘qligini tekshirish (kutubxonada kitob topish kabi).
- Noyob narsalarni saqlash va ularni tezda topish (masalan, telefon raqamlarini saqlash).
- Qiymatlarni kalitlarga ulash (masalan, nomlarni telefon raqamlariga ulash).
Hash jadvallari bu narsalar uchun ajoyib bo‘lishining eng muhim sababi shundaki, Xesh jadvallari juda tez taqqoslanadigan massivlar va bog‘langan listlar, ayniqsa katta setlar uchun. Massivlar va bog‘langan listlar qidirish va o‘chirish uchun O(n) vaqt murakkabligiga ega, xesh jadvallari esa o‘rtacha O(1)ga ega.
Xesh jadvallari umumlashtirilgan
Xesh jadvali elementlari chelaklar deb ataladigan saqlash idishlarida saqlanadi.
Xesh funksiyasi xesh kodini yaratish uchun elementning kalitini oladi.
Xesh-kod element qaysi chelakka tegishli ekanligini aytadi, shuning uchun biz to‘g‘ridan-to‘g‘ri o‘sha Xesh jadvali elementiga o‘tishimiz mumkin: uni o‘zgartirish yoki o‘chirish yoki shunchaki mavjudligini tekshirish.
Ikkita Xesh-jadval elementi bir xil xesh-kodga ega bo‘lganda to‘qnashuv sodir bo‘ladi, chunki bu ular bir xil chelakka tegishli ekanligini anglatadi.
To‘qnashuvni bitta chelakda bir nechta elementga ruxsat berish uchun listlar yordamida zanjirlash orqali hal qilish mumkin.
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!