22. Qidiruv algoritmlarida indekslash nima?

Hash funktsiyalari

Hashlash (inglizcha xeshdan) - bu o'zboshimchalik uzunlikdagi dastlabki ma'lumot massivini sobit uzunlikdagi bitli qatorga aylantirish.

Xash funktsiyalari uchun ko'plab algoritmlar mavjud, ammo ular xarakteristikalari bilan farq qiladi - kriptografik kuch, bit chuqurligi, hisoblash murakkabligi va boshqalar.

Kriptografik jihatdan kuchli xash funktsiyalari bizni qiziqtiradi. Odatda bu ikkita talab:

• 
  Berilgan C xabari uchun xuddi shu xash bilan boshqa C "xabarini topish deyarli mumkin emas
  
• 
  Xuddi shu xashga ega bo'lgan juft xabarlarni (SS ") topish deyarli mumkin emas.
  

Talablar navbati bilan I va II tip to'qnashuvlarga qarshilik deb ataladi. Bunday funktsiyalar uchun yana bir talab muhim bo'lib qolmoqda: argumentning ozgina o'zgarishi bilan funktsiyalarning o'zida sezilarli o'zgarishlar bo'lishi kerak. Shunday qilib, xash qiymati argumentning alohida bitlari haqida ham ma'lumot bermasligi kerak.