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]