Kriptografik xesh funksiyasi. Xesh nima va u nima uchun

Xesh funksiyalari
Avvalo, kalitlarni jadval manzillariga aylantiruvchi xesh funksiyasini hisoblash masalasini hal qilish kerak. Odatda, bu arifmetik hisob-kitobni amalga oshirish qiyin emas, lekin siz hali ham turli xil nozik tuzoqlarga duch kelmaslik uchun ehtiyot bo'lishingiz kerak. Agar sizda M elementni o'z ichiga olishi mumkin bo'lgan jadvalingiz bo'lsa, kalitlarni diapazondagi butun sonlarga aylantiradigan funksiya kerak. Ideal xesh-funktsiyani hisoblash oson bo'lishi va tasodifiy funktsiyaga o'xshab ko'rinishi kerak: har qanday argumentlar uchun natijalar, ma'lum ma'noda, teng darajada ehtimolga ega bo'lishi kerak.
Xesh funktsiyasi kalit turiga bog'liq. To'g'ridan-to'g'ri aytganda, har bir mumkin bo'lgan kalit turi uchun alohida xesh funktsiyasi talab qilinadi. Samaradorlikni oshirish uchun odatda aniq turdagi konversiyalardan qochish va buning o'rniga mashina so'zida kalitlarning ikkilik ko'rinishini arifmetik hisob-kitoblarda ishlatilishi mumkin bo'lgan butun son sifatida ko'rib chiqish g'oyasiga murojaat qilish tavsiya etiladi. Xeshlash yuqori darajali tillardan oldin paydo bo'lgan - dastlabki kompyuterlarda qiymatni satr kaliti yoki butun son sifatida ko'rib chiqish odatiy hol edi. Ba'zi yuqori darajali tillarda ma'lum bir kompyuterda kalitlarning ifodalanishiga bog'liq bo'lgan dasturlarni yaratish qiyin, chunki bunday dasturlar o'z-o'zidan mashinaga bog'liq va shuning uchun boshqa kompyuterga o'tkazish qiyin. Xesh funktsiyalari odatda kalitlarni butun sonlarga aylantirish jarayoniga bog'liq, shuning uchun ham mashina mustaqilligiga, ham xeshlashda samaradorlikka erishish qiyin bo'lishi mumkin. Odatda, oddiy tamsayı yoki suzuvchi nuqtali kalitlarni faqat bitta mashina operatsiyasi bilan aylantirish mumkin, ammo string kalitlari va boshqa turdagi kompozit kalitlar qimmatroq va samaradorlikka ko'proq e'tibor beradi.
Ehtimol, eng oddiy holat - bu kalitlar sobit diapazondagi suzuvchi nuqta raqamlari. Misol uchun, agar tugmalar 0 dan katta va 1 dan kichik raqamlar bo'lsa, siz ularni oddiygina M ga ko'paytirishingiz, natijani pastki butun songa yaxlitlashingiz va 0 va M - 1 oralig'idagi manzilni olishingiz mumkin; bunday misol rasmda ko'rsatilgan. 14.1. Agar kalitlar s dan katta va t dan kichik bo'lsa, ularni s ni ayirish va ts ga bo'lish, ularni 0 dan 1 gacha bo'lgan qiymatlar oralig'iga olib kelish va jadvaldagi manzilni olish uchun M ga ko'paytirish orqali masshtablash mumkin. .