Mavzu: Xesh jadvallari va funktsiyalari

Mustaqil ish

Mavzu: Xesh jadvallari va funktsiyalari

Reja:

1. 
   Kirish
   
2. 
   Xesh vazifalari
   
3. 
   Bo'linish usuli
   
4. 
   Ko'paytirish usuli (multiplikativ)
   
5. 
   Dinamik xeshing
   
6. 
   Kengaytirilgan xeshing (extensible xeshing)
   
7. 
   Kalit tartibini saqlaydigan vazifalar (Xesh funktsiyalarini saqlash tartibi)
   
8. 
   Minimal mukammal xeshing
   
9. 
   To'qnashuvlarning ruxsatnomasi
   
10. 
    Zanjir usuli
    
11. 
    Ochiq manzil
    
12. 
    Chiziqli manzil
    
13. 
    Kvadrat va o'zboshimchalik bilan manzil
    
14. 
    Juft aralashgan manzil
    
15. 
    Xesh jadvalining elementlarini olib tashlash
    
16. 
    Xeshing dasturi
    
17. 
    Parollarni xeshing
    
18. 
    Xulosa
    
19. 
    Ilova (demo dasturi)
    
20. 
    Ishlatilgan manbalar
    

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.