12-mavzu. Xeshlash va xesh jadvallar Reja

Ko'paytirishga asoslangan xash funktsiyalari [tahrirlash tahrirlash kodi]
{\ Displaystyle w} w so'zini mashina so'zlari bilan ifodalovchi sonlar soni bilan belgilang. Masalan, IBM PC bilan mos 32-bit kompyuterlar uchun {\ displaystyle w = 2 ^ {32}} {\ displaystyle w = 2 ^ {32}}.
{\ Displaystyle A} A bilan {\ displaystyle w} w bilan bir-biriga nisbatan sodda bo'lishi uchun bir necha doimiy {\ displaystyle A} ni tanlang. Keyin ayirish funktsiyasi yordamida ko'paytirish quyidagi kabi bo'lishi mumkin:
{\ displaystyle h (K) = \ chap [M \ chapdan \ lfloor {\ frac {a} {w}} * K \ o'ng tomonda \ o'ng]} h (K) = \ chap [M \ chap \ lfloor { \ Frac {A} {w}} * K \ o'ng \ rfloor \ right]
Bu holda, ikkilik raqamli tizimda bo'lgan kompyuterda {\ displaystyle M} M ikki kuchga ega va {\ displaystyle h (K)} h (K) mahsulotning o'ng yarmining yuqori tartibli qismlaridan iborat bo'ladi {\ displaystyle A * K} A * K .
Bo'linish va ko'paytirishga asoslangan xash funktsiyalarining afzalliklari orasida haqiqiy kalitlarning tasodifiylikdan foydalanishning foydaliligini qayd etish lozim. Misol uchun, tugmachalar arifmetik progresiya bo'lsa (masalan, "Ism 1", "Ism 2", "Ism 3" nomi ketma-ketligi), ko'paytirish yordamida xash funktsiyasi arifmetik progresiyani har xil xash qiymatlarining taxminiy arifmetik o'sishiga mos keladi, tasodifiy vaziyatga nisbatan to'qnashuvlar soni [3].
Kattalashtirishni ishlatadigan xash funktsiyalaridan biri Fibonacchi aralashmasidan foydalanadigan xash funktsiyasi. Fibonachchi xashasi oltin qismning xususiyatlariga asoslanadi. Doimiy {\ displaystyle A} A sifatida {\ displaystyle \ varphi ^ {- 1} * w} \ varphi ^ {{1}} * wga eng yaqin son tanlandi va
{\ displaystyle w} w {\ displaystyle \ varphi} \ varphi oltin nisbati [3]
Argumentlar uzunligi satrlarini aralashtirish [tahrirlash tahrirlash kodi]
Yuqoridagi usullar bir necha so'zdan yoki o'zgarmaydigan uzunlikdagi kalitlardan iborat kalitlarni ko'rib chiqish zarur bo'lsa ham qo'llaniladi.
Misol uchun, so'zlarni "modulo {\ displaystyle w} w yoki" eksklyuziv yoki "operatsiyasidan foydalanib birlashtira olasiz. Ushbu printsip bo'yicha ishlaydigan algoritmlardan biri Pearson xash funktsiyasi.
Pearson xashlashi Piter Pearson tomonidan 8-bitli protsessorlar bilan ishlaydigan protsessorlar uchun taklif qilingan algoritm bo'lib, vazifasi tezda o'zboshimchalik bilan uzunligini bir xash kodiga aylantirishdir. Kirish funktsiyasi {\ displaystyle W} W harfini oladi, har birining 1 bayt hajmidagi {\ displaystyle n} n belgilaridan iborat va 0 dan 255 gacha bo'lgan qiymatga ega bo'ladi. Shu bilan birga, aralash-kod qiymati kiritilgan so'zning har bir belgi bilan bog'liq.
Algoritm quyidagi {{\ displaystyle W} W usuli kiritilgan va {\ displaystyle T} T permutation stolini ishlatadigan quyidagi soxta kod bilan tavsiflanishi mumkin:

h := 0 for each c in W loop index := h xor c h := T[index] end loop return h
	Algoritmning afzalliklari quyidagilardan iborat:

hisoblash qulayligi;
to'qnashuv ehtimolligi eng katta bo'lgan bunday kirish ma'lumotlarining
yo'qligi; ideal xash funktsiyasiga modifikatsiya qilish imkoniyati [4].
{\ Displaystyle l} l belgilaridan iborat {\ displaystyle K} K tugmalariga muqobil usul sifatida {\ displaystyle K = x_ {1} x_ {2} ... x_ {l}} K = x _ {{1 }}
X _ {{2}} ... x _ {{l}}), siz hisob-kitob qilishingiz mumkin
{\ displaystyle h (K) = (h_ {1} (x_ {1}) + h_ {2} (x_ {2}) + ... + h_ {l} (x_
{l})) h (K) = (h _ {{1}} (h _ {{1}}) + h _ {{2}} (x _ {{2}}) + ... + h _ {{l}} (x _
{{ L}})) \ mod M [3]
Zo'r hashing [tahrirlash tahrirlash kodi]
Ideal xash funktsiyasi (mukammal mukammal xash funktsiyasi) {\ displaystyle S} S dan har bir klavishni to'qnashuvsiz aniq raqamlar majmui bilan ajraladigan funksiya. Matematikada bunday o'zgarishga in'ektsion xaritalash deyiladi. Zo'r hashing [tahrirlash tahrirlash kodi]
Ideal xash funktsiyasi (mukammal mukammal xash funktsiyasi) {\ displaystyle S} S dan har bir klavishni to'qnashuvsiz aniq raqamlar majmui bilan ajraladigan funksiya. Matematikada bunday o'zgarishga in'ektsion xaritalash deyiladi.
Hashing yoki hashing (inglizcha hashing) - o'ziga xos algoritm bilan bajarilgan ma'lum uzunlikdagi tasodifiy uzunlikdagi boshlang'ich registri (output) bit majmuasiga aylantirilishi. Algoritmni o'zida mujassam etgan va ayirboshlashni amalga oshiradigan funktsiya ... Xash funktsiyalarining bu xususiyati ularni quyidagi amalda qo'llashga imkon beradi.
Kriptografik xash funktsiyalari kriptografiyada foydalanish uchun moslashtirilgan ba'zi xususiyatlarga ega bo'lgan xash funktsiyalarining maxsus sinfidir.