Xesh funktsiyasi nima? Kriptografik xesh funktsiyalari

Shakl 14.3.

Ushbu jadvalning har bir satrida quyidagilar ko'rsatilgan: 3 harfdan iborat so'z, ASCII kodidagi ushbu so'zning sakkizburchak va o'nlik shakllardagi 21 bitli raqami va 64 va 31-jadvallarning o'lchamlari uchun standart modulli xesh funktsiyalari (ikkita o'ng ustun). 64-jadvalning o'lchami istalmagan natijalarga olib keladi, chunki hash qiymatini olish uchun faqat kalitning o'ng tomonidagi bitlar ishlatiladi va umumiy til so'zlaridagi harflar teng taqsimlanmagan. Masalan, y harfi bilan tugaydigan barcha so'zlarning xesh qiymati 57 ga teng. Aksincha, 31 ning oddiy qiymati jadvalda hajmning yarmidan ko'prog'iga kamroq to'qnashuvlarga olib keladi.

Modulli xeshni amalga oshirish juda oddiy, stolning kattaligi bosh raqam bo'lishi kerak. Ba'zi bir amaliy dasturlar uchun siz ozgina ma'lum bo'lgan tub sonlar bilan qoniqishingiz yoki jadvalning kerakli hajmiga yaqin bo'lgan tub sonlar ro'yxatiga qarashingiz mumkin. Masalan, 2 t - 1 ga teng bo'lgan raqamlar juda muhimdir t \u003d 2, 3, 5, 7, 13, 17, 19 va 31  (va t ning boshqa qiymatlari yo'qligi uchun)< 31 ): это известные простые числа Мерсенна. Чтобы динамически распределить таблицу нужного размера, нужно вычислить простое число, близкое к этому значению. Такое вычисление нетривиально (хотя для этого и существует остроумный алгоритм, который будет рассмотрен в части 5), поэтому на практике обычно используют таблицу заранее вычисленных значений (см. рис. 14.4). Использование модульного хеширования - не единственная причина, по которой размер таблицы стоит сделать простым числом; еще одна причина рассматривается в разделе 14.4.