Xeshing-ma'lum bir xususiyatga EGA bo'lmagan pastki to'plamlarda (elementlarning to'plamlari) bir nechta kalitlarni (odatda saqlash elementlarini va odatda matn satrlari yoki raqamlar shaklida taqdim etilgan) ajratish



Download 62,22 Kb.
bet1/9
Sana15.11.2022
Hajmi62,22 Kb.
#866865
  1   2   3   4   5   6   7   8   9
Bog'liq
Mavzu Xesh jadvallari va funktsiyalari




Kirish

Xeshing bilan biz deyarli har bir qadamda duch kelamiz: brauzer bilan ishlashda (veb-havolalar ro'yxati), matn muharriri va tarjimon (lug'at), skript tillari (Perl, Python, PHP va boshqalar), kompilyator (belgilar jadvali). Brian Kerniganning fikriga ko'ra, bu "kompyuter fanining eng katta kashfiyotlaridan biri". Manzil kitobiga, ensiklopediyaga, alfavit ko'rsatkichiga qarab, biz alifbo tartibida buyurtma berish xeshingdan boshqa narsa emas deb o'ylamaymiz.


Xeshing-ma'lum bir xususiyatga ega bo'lmagan pastki to'plamlarda (elementlarning to'plamlari) bir nechta kalitlarni (odatda saqlash elementlarini va odatda matn satrlari yoki raqamlar shaklida taqdim etilgan) ajratish. Bu xususiyat xeshing funktsiyasi yoki xesh funktsiyasi bilan tavsiflanadi va xesh manzili deb ataladi. Teskari muammoni hal qilish Xesh-tuzilmaga (Xesh-jadval) beriladi: Xesh-manzilda ular kerakli elementga tezkor kirish imkonini beradi. Ideal holda, qidirish vazifalari uchun xesh manzili yagona kalit (ideal xesh funktsiyasi) bilan tavsiflangan elementga kirish uchun yagona manzil bo'lishi kerak. Biroq, amalda, ideal kelishuv bilan almashtirilishi va bir xil Xesh manziliga ega bo'lgan to'plamlar bir nechta elementni o'z ichiga olishi kerak.
Muddatli" xeshing " (xeshing) chop etilgan dasturlash ishlari mexanizmi o'zi ilgari ma'lum bo'lsa-da, nisbatan yaqinda (1967, [1]) paydo bo'ldi. Ingliz tilidagi "xesh" fe'li "kesish, kesish"degan ma'noni anglatadi. Rus tili uchun akademik AP Ershov [2] juda muvaffaqiyatli ekvivalent taklif etildi — "joylashtirish", bunday "almashtirish" va "permütasyon"deb kombinatorik tegishli tushunchalar bilan hamohang. Biroq, u ildiz otmadi.
Donald Knut [3] ta'kidlaganidek, xeshing g'oyasi birinchi marta GP Lan tomonidan 1953 da yanvar oyida IBMning ichki memorandumini yaratishda, zanjirlarning aralashgan usullarini hal qilish uchun foydalanish taklifi bilan ifodalangan. Shu bilan birga, IBMning yana bir xodimi – Zhini Amdal - ochiq chiziqli manzildan foydalanish g'oyasini ilgari surdi. Ochiq matbuotda xeshing birinchi marta Arnold dumi (1956) tomonidan tasvirlangan bo'lib, u aralashgan manzil sifatida bo'linishning qolgan qismini oddiy raqamga ishlatish uchun qulay ekanligini ko'rsatdi. A. dumi to'qnashuvlarni bartaraf etish uchun zanjirlar usulini tasvirlab berdi, lekin ochiq manzil haqida gapirmadi. Zanjir usulidan farqli aralashgan yondashuv AP Ershov (1957, [2]) tomonidan taklif qilingan bo'lib, u chiziqli ochiq manzillash usulini ishlab chiqdi va ta'rifladi. Boshqa tadqiqotlar orasida Petersonning ishi (1957, [4]) qayd etilgan. Katta fayllar bilan ishlashda ochiq manzilli usullar sinfini amalga oshirdi. Peterson umumiy holatda ochiq manzilni aniqladi, bir xil xeshing xususiyatlarini tahlil qildi, turli vazifalarda lineer manzildan foydalanish statistikasini chuqur o'rganib chiqdi. 1963 da Verner Bukholtz [6] Xesh funktsiyalarining eng chuqur tadqiqotini nashr etdi.
O'tgan asrning 60-yillari oxiriga kelib, adabiyotlarda tasvirlangan ochiq manzil sxemasining yagona turi edi, biroq bir nechta tadqiqotchilar mustaqil ravishda mustaqil Xesh funktsiyasining takroriy tasodifiy qo'llanilishiga asoslangan boshqa sxemani ishlab chiqdilar ([3], p.585). Keyingi bir necha yil mobaynida xeshing keng qo'llanila boshlandi, garchi yangi ishlar chop etilmagan bo'lsa-da. Keyinchalik Robert Morris [5] xeshing bo'yicha keng qamrovli tekshiruv va "tarqalgan xotira" (scatter storage) atamasini kiritdi. Bu ish er-xotin xeshing bilan ochiq manzilni yaratishga olib keldi.

Keyinchalik, Xesh funktsiyalarining asosiy turlari va ularning ayrim modifikatsiyalari, to'qnashuvlarni hal qilish usullari, Xesh jadvalidagi elementlarni olib tashlash muammolari, shuningdek, xeshingni qo'llash uchun ba'zi variantlar ko'rib chiqiladi.





Download 62,22 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4   5   6   7   8   9




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish