Kompyuter injinering fakulteti 961-19 gurux 3-kurs talabasi Nurmetov Ixlosbek Jamoliddin og’lining Ma’lumotlar tuzulmasi va algoritmlar fanidan Yozgan

5- bosqich. Natija. Ma’lumotning xesh qiymati A, B, C, D va E registrlardagi qiymatlarni birlashtirish natijasida hosil qilinadi.

Xash funktsiyasi kalit turiga bog'liq. Qattiq gapirish, alohida xesh funktsiyasi alohida kalitni talab qiladi. Samaradorlik samaradorligini oshirish uchun, odatda, arifmetik hisob-kitoblarda ishlatilishi mumkin bo'lgan butunlar sifatida klavish so'zidagi tugmachalarni ko'rib chiqish g'oyasi sifatida turlarini aniq o'zgartirishdan qochish maqsadga muvofiqdir. Yuqori darajadagi tillardan oldin paydo bo'lgan, erta kompyuterlar uchun odatiy moddalar satr kaliti sifatida, keyin butun son sifatida ko'rib chiqilishi mumkin edi. Ba'zi yuqori darajadagi tillarda ma'lum bir kompyuterdagi tugmachalarni taqdim etishga bog'liq bo'lgan dasturlarni yaratish qiyin, chunki bunday dasturlar asosan mashinaga bog'liq, shuning uchun ular boshqa kompyuterga topshirish qiyin. Odatda, xesh funktsiyalari asosiy konversiya jarayoni sonlar ichiga bog'liq, shuning uchun bir vaqtning o'zida mashinada amalga oshirishda yordam va samaradorlikni ta'minlash qiyin. Qoida tariqasida, oddiy butun sonli kalitlar yoki suzuvchi nuqta tipidagi kalitlar faqat bitta mashinadan foydalanish orqali o'zgartirilishi mumkin, ammo struktura tugmachalari va boshqa turdagi kalitlar samaradorlikka yuqori xarajat va ko'proq e'tibor talab etiladi.

Ehtimol, eng oddiy vaziyat, kalitlar suzuvchi nuqta bilan belgilangan nuqtadan iborat. Masalan, agar tugmachalar raqamlar bo'lsa, katta 0 va kichik 1 bo'lsa, uni m bilan ko'paytirishi mumkin, natijani kichik bir songa ko'paytirish va 0 va 1 oralig'ida manzilni olish; Ushbu misol rasmda ko'rsatilgan. 14.1. Agar tugmachalar s dan kattaroq bo'lsa va ular tarqalishi, ularni ajratish va tslarni ajratish va natijada ular 0 dan 1 gacha bo'lgan qiymatlar oralig'iga tushib, keyin m vani ko'paytiradilar jadvaldagi manzili.

Suzuvchi nuqta bilan 0 va 1 oralig'ida, ularning o'lchami 97 ga ko'paytiriladi. Ushbu misolda uchta mojarolar sodir bo'ldi: 17, 53 va 76 ga teng bo'lgan ko'rsatkichlar uchun. Xash qadriyatlari oqsoqollar kalitlari tomonidan aniqlanadi, yosh zarralari hech qanday rol o'ynaydi. Hash funktsiyasini ishlab chiqish maqsadlaridan biri bu nomutanosiblikni yo'q qilish uchun bunday nomutanosiblikni yo'q qilishdir.

Agar tugmachalar W-bit butun son bo'lsa, ular suzuvchi nuqta raqamlariga aylantirilishi va oldingi paragrafda bo'lgani kabi, m i ga ko'paytiring. Agar suzuvchi nuqta operatsiyalari ko'p vaqtni egallab olsa, raqamlar shunchalik baland emas, natijada raqamlar shunchalik baland emas, natijada bir xil natijaga ko'ra, simni m uchun ko'paytirish kerak, so'ngra m uchun ko'payishingiz kerak 2 Vt (yoki ko'paytirish tufayli ko'payish, siljish va keyin ko'payishiga olib keladigan bo'lsa) 2 Vtni ajratish uchun o'chirish uchun o'ngda. Bunday usullar, agar kalitlar diapazon bilan bir xil tarzda taqsimlanmagan bo'lsa, hash qiymati faqat kalitning etakchi raqamlari bilan belgilanmaydi.

Ko'proq oddiy I. samarali usul W-bit butun sonlar uchun - ehtimol ko'p ishlatiladigan HOZID MARKAZIDA MIS-ning o'lchamidagi M, I, I.00 ga bo'linishni hisoblash. h (k) \u003d k mod m har qanday butun sonli k harfi uchun. Ushbu funktsiya modulli hash funktsiyasi deb ataladi. Hisoblash juda oson, va Kichik M qiymatdagi k ++ tilida), kichik m qiymatlar o'rtasidagi yagona qiymatlarni taqsimlashiga erishish samarali bo'ladi. 14.2.

Uchta o'ng ustunlarda chap tomonda ko'rsatilgan 7 bitli kalitlarning natijasi quyidagi funktsiyalardan foydalangan holda ko'rsatilgan: