12-mavzu. Xeshlash va xesh jadvallar Reja

12-mavzu. Xeshlash va xesh jadvallar
Reja:

1. 
   To‘g‘ridan to‘g‘ri adreslash jadvallari.
   
2. 
   Xesh jadvallar.
   
3. 
   Xesh funksiyalar
   

Xeshlash

Yuqorida biz mijoz dasturiga ma'lumotlarni qidirish va olish imkonini beradigan bir qator ro'yxat tuzilmalarini qo'lga kiritdik. Har bir bunday strukturada Find uslubi ro'yxatni kesib o'tishni amalga oshiradi va kalitga mos keladigan ma'lumotlar elementini qidiradi. Shu bilan birga, qidiruv samaradorligi ro'yxat tuzilishiga bog'liq. Oddiy ro'yxatga kiritilganda, Find (Oddiy) metodi O (n) elementlariga qarash uchun kafolatlanadi, ikkilik qidiruv daraxti va ikkilik qidiruv sharoitida esa, O (log2n) samaradorligi yuqori bo'ladi.
Ideal holda biz O (1) vaqtida ma'lumotlarni tanlashni xohlaymiz. Bunday holda, zarur taqqoslashlar soni ma'lumotlar elementlarining soniga bog'liq emas. Bir element katalogda indeks sifatida foydalanilganda element (1) vaqtida namuna olinadi. Misol uchun, aktsiyadagi menyudan taomlar buxgalteriyani soddalashtirish uchun raqamlar bilan soddalashtiriladi. "Aralashtirilgan basturma" turidagi har qanday nozikligi ma'lumotlar bazasida faqat 2 raqami bilan ko'rsatilgan. Go'shtning egasi faqatgina 2-tugma bilan ro'yxatga kiritilishi mumkin (25-rasm).
Hashing yoki hashing (inglizcha hashing) - o'ziga xos algoritm bilan bajarilgan ma'lum uzunlikdagi tasodifiy uzunlikdagi boshlang'ich registrini (chiqish) bit majmuasiga aylantirish. Algoritmni bajaradigan va ishlashni amalga oshiradigan vazifaga "xash funktsiyasi" yoki "konvolution funktsiyasi" deb nomlanadi. Resurslar ma'lumotlariga kirish majmuasi, "kalit" yoki "xabar" deb ataladi. Konvertatsiya (chiqdi) natijalariga "xash", "xash kodi", "xash summasi", "xabar xulosasi" deb nomlanadi.
Misol uchun, biz 128-bitli hash funksiyasining kiritilishini o'n oltinchi sonda yoki 1 raqami bilan Leo Tolstoyning romaniga yuborishimiz mumkin. Natijada, har ikkala holatda ham biz "s4ca4238a0b923820dcc509a6f75849b" kabi pseudotasodifiy o'n olti raqamli qatorlarni olamiz.
Agar manba matnini bir karra o'zgartirsa, xash funktsiyasining natijasi butunlay o'zgartiriladi.
Hash funksiyalarining bu xususiyati ularni quyidagi hollarda qo'llashingizga imkon beradi:
assotsiativ majmualar qurishda; bir qator ma'lumotlar to'plamida takroriy matnlarni qidirishda; ma'lumotlar to'plamlari uchun noyob identifikatorlarni yaratishda;
ma'lumotlarni saqlash va / yoki uzatish jarayonida yuzaga keladigan xatolarni (tasodifiy yoki qasddan kelib chiqadigan) aniqlash uchun ma'lumotlar (signal) summalarini hisoblashda;
parollarni xavfsizlik tizimlarida xesh kodi shaklida saqlashda (xash kodi
yordamida parolni tiklash uchun foydalaniladigan xash funktsiyasiga teskari funksiya kerak); elektron imzo yaratishda (amalda, ko'pincha imzolangan xabarning o'zi emas,
balki uning "xash rasmi"); va boshq.
Umumiy holatda (Dirkichlet printsipiga ko'ra) manba (kirish) ma'lumotlari va xash kodi (chiqish ma'lumotlari) o'rtasida hech qanday bog'lovchilik yo'q. Xash funktsiyasi (chiqishi) tomonidan qaytarilgan qiymatlar kiritish qatoridan (kirish ma'lumotlari) kamroq farq qiladi. Xash funktsiyasi bir nechta turli xil xabarlarni bir xil xabarlarga aylantiradigan holatga "to'qnashuv" deb ataladi. Qarama-qarshiliklar ehtimolligi xash funktsiyalarining sifatini baholash uchun ishlatiladi.
Turli xil xususiyatlarga ega ko'plab xash algoritmlari mavjud. Xususiyatlar namunalari:
raqamli quvvat; hisoblash murakkabligi; kriptografik kuch.
Bir yoki bir nechta xash funktsiyasini tanlash muammoni hal etishning o'ziga xos xususiyati bilan belgilanadi. Xash funktsiyasining eng oddiy namunasi ma'lumotlarning "takrorlanishi" - takroriy takrorlash kodi (ingliz CRC, takroriy takrorlash kodi).
Tarix [tahrir | tahrirlash kodi]
Yanvar 1953da Hans Peter Lun (german: Hans Peter Luhn) (IBMning xodimi) "xash kodlash" ni taklif qildi. Donald Knut "Hashing" deb nomlangan sistematik g'oyani ilgari surgan birinchi Hans edi.
1956-yili Arnold Dumey "Kompyuterlar va avtomatlashtirish" asarida eng ko'p programmuvchilar buni bilganligi uchun "hashing" g'oyasini birinchi bo'lib tasvirlab bergandi. Dumi, "lug'at muammosiga" yechim sifatida "hashing" ni ko'rib chiqdi, qolgan raqamni "hash manzil" (1) sifatida ajratishni taklif qildi.
1957-yilda Wesley Peterson (W. Wesley Peterson) tomonidan yirik fayllardagi matnni qidirish bo'yicha "IBM Journal of Research and Development Journal" jurnalida chop etilgan maqola chop etildi. Ushbu ish "xashlash" bo'yicha birinchi "jiddiy" ish deb hisoblanadi. Maqolada, Wesley, "ochiq manzil" deb nomlangan bo'lib, uni o'chirish vaqtida ishlashning pasayishiga ishora qilmoqda. Olti yil o'tib, Verner Buchholz (Germaniya Verner Buchholz) asarining nashri chop etildi, unda "xash funktsiyalari" ni keng qamrovli o'rganish o'tkazildi. Keyingi bir necha yillar davomida "xashing" keng tarqalgan bo'lib ishlatilgan, biroq muhim ishlar chop etilmadi.
1967 yilda "Zamonaviy ma'noda" xirgoyi "kitobida Herbert Hellerman"
Raqamli hisoblash tizimlari tamoyillari "deb nomlangan [2]. 1968 yilda Robert Morris "ACM kommunikatsiyasi" jurnalida "xashlash" haqida keng ma'lumot tarqatdi. Ushbu asar ilmiy saralashga "xashing" tushunchasini kiritib, ilgari faqat mutaxassislar (jargon) tomonidan qo'llaniladigan "xash" atamasini kuchaytirishga qaratilgan "kalit" nashr.
1990-yillarning boshiga qadar rus tilidagi adabiyotda Andrey Petrovich Ershovning asarlari natijasida "tartibga solish" so'zi "xashing" atamasi bilan tenglashtirildi va "to'qnashuv" atamasi "to'qnashuvlar" uchun ishlatilgan (A.P. Ershov 1956 yildan beri "kelishuv" dan foydalangan) ). 1989 yilda Niklaus Wirthning algoritmlari va ma'lumotlar tuzilmalari rus tilidagi nashriga "to'siq" atamasi ham ishlatilgan. Shuningdek, bu usulni boshqa ruscha so'z bilan ham aytish mumkin: okroshka. Biroq, bu variantlarning hech biri ildiz otgan va rus adabiyotida "xashing" atamasi asosan ishlatiladi [3].
"Xash funktsiyalarining turlari" [tahrirlash tahrirlash kodi] "Yaxshi" xash funktsiyasi ikki xususiyatni qondirishi kerak: tezkor hisoblash; eng kam "to'qnashuv" soni. Biz quyidagilarni bildiramiz:
{\ displaystyle K} K - "tugmachalar" soni (kirish ma'lumotlari);
{\ displaystyle h (k)} h (k) - {\ displaystyle M} M boshqa qiymatlari (chiqish ma'lumotlari) ko'p bo'lmagan xash funktsiyasi.
Ya'ni:
{\ displaystyle \ forall k \ in (0; \, K): h (k) "Yomon" xash funktsiyasiga misol sifatida {\ displaystyle M = 1000} M = 1000 funktsiyasidan foydalanib, {\ displaystyle K} K raqamining yigirma xonali raqami ortidan tanlangan o'nta raqamli tabiiy raqam bilan {\ displaystyle K} K "Hash kodlari" qiymatlari "000" va "999" orasida bir xil taqsimlanishi kerak, lekin "haqiqiy" ma'lumot uchun bu "tugmachalar" chap yoki o'ngdagi "katta" sonli nolga ega bo'lmasa [ 3].
«Xash funktsiyalarini» bir necha oddiy va ishonchli amalga oshirishni ko'rib chiqing.
"Xash funktsiyalari" bo'limi [tahrirlash tahrirlash kodi]

1. 
   "Xesh kodi" - mumkin bo'lgan barcha "xesh" larning soniga bo'linadi tahrirlash kodi]
   

Xash funktsiyasi "xash" ni kirish ma'lumotlarini {\ displaystyle M} M:
h(k)=k\mod M}
{\ displaystyle M} M barcha mumkin xostlarning soni (chiqishi).
Ko'rinib turibdiki, {\ displaystyle M} M uchun funktsiyaning qiymati ham {\ displaystyle k} k va odd - odatdagi {\ displaystyle k} k uchun ham bo'ladi. Bundan tashqari, "xash kodi" o'ng tomonda joylashgan {\ displaystyle k} k sonining bir nechta raqamiga bog'liq bo'lgani uchun, siz {\ displaystyle M} M komponentining raqam tizimining darajasini ishlatmasligingiz kerak, bu juda ko'p to'qnashuvlarga olib keladi. Amalda odatda oddiy {\ displaystyle M} M ni tanlashadi; Aksariyat hollarda bu tanlov juda qoniqarli.

2. 
   "Xash kodi" - natijada olingan polinomning koeffitsientlari to'plami tahrirlash kodi]
   

Xash funktsiyasi kirish ma'lumotlarini polinom moduliga bo'linishi mumkin. Ushbu usulda {\ displaystyle M} M ikkitadan kuch bo'lishi kerak va ikkilik tugmalar ({\ displaystyle K=k_{n-1}k_{n-2}...k_{0}} K=k_{{n-1}}k_{{n2}}...k_{{0}}) polinomlar sifatida ifodalanadi, qolgan ma'lumotlarning qolgan qismi sifatida olingan polinomning koeffitsientlarining qiymatlari "displaystyle" "xash kodi" K} k oldindan tanlangan polinom {\ displaystyle P} P darajasiga {\ displaystyle m} m:
{\ displaystyle K (x) \ mod P (x) = h_ {m-1} x ^ {m-1} + \ nuqtalar + h_ {1} x + h_ {0}}
{\ displaystyle h (x) = h_ {m-1} ... h_ {1} h_ {0}} {\ displaystyle h (x) = h_
{m-1} ... h_ {1} h_ {0 }}
{\ Displaystyle P (x)} P (x) to'g'ri tanlovi bilan deyarli bir xil tugmalar [3] o'rtasida to'qnashuv mavjud emas.