1. Dasturiy ta’minot va uning turlari

Xesh jadvallar (Xesh jadvallar va ularni tashkil etish, Xeshlash)

Xeshing bilan biz deyarli har bir qadamda duch kelamiz: brauzer bilan ishlashda (veb-havolalar ro'yxati), matn muharriri va tarjimon (lug'at), skript tillari (Perl, Python, PHP va boshqalar), kompilyator (belgilar jadvali). Brian Kerniganning fikriga ko'ra, bu "kompyuter fanining eng katta kashfiyotlaridan biri". Manzil kitobiga, ensiklopediyaga, alfavit ko'rsatkichiga qarab, biz alifbo tartibida buyurtma berish xeshingdan boshqa narsa emas deb o'ylamaymiz. Xesh funktsiyasi k kalitini olgan va k bilan bog'liq ma'lumotlarni olish uchun xesh jadvalida qidirilayotgan manzilni qaytaradigan h(K) funktsiyasidir, masalan, k abonentning telefon raqami va kerakli ma'lumot uning nomi. Bu holda funktsiya bizga kerakli manzilni topish uchun aniq ma'lumot beradi. Telefon daftariga misol, taqdim etilgan CDda demo dasturi bilan tasvirlangan. Asosan, siz har doim bunday funktsiyani yaratishingiz mumkin, agar xesh jadvali kalit maydonidan kattaroq bo'lsa. Biroq, to'g'ri Xesh funktsiyasini topish vazifasi ahamiyatsiz. Albatta, bu muayyan vazifaga juda bog'liq. Bundan tashqari, Xesh funktsiyasiga o'xsxesh cheklov uning ishlashiga salbiy ta'sir ko'rsatishi mumkin. Shuning uchun, tez-tez ketma-ket namuna olish jarayoni tez-tez sodir bo'lishini oldindan bilmasa, bunday Xesh funktsiyasini izlash o'rniga indekslashga murojaat qiling.
Xeshlash Yuqorida biz mijoz dasturiga ma'lumotlarni qidirish va olish imkonini beradigan bir qator ro'yxat tuzilmalarini qo'lga kiritdik. Har bir bunday strukturada Find uslubi ro'yxatni kesib o'tishni amalga oshiradi va kalitga mos keladigan ma'lumotlar elementini qidiradi. Shu bilan birga, qidiruv samaradorligi ro'yxat tuzilishiga bog'liq. Oddiy ro'yxatga kiritilganda, Find (Oddiy) metodi O (n) elementlariga qarash uchun kafolatlanadi, ikkilik qidiruv daraxti va ikkilik qidiruv sharoitida esa, O (log2n) samaradorligi yuqori bo'ladi. Ideal holda biz O (1) vaqtida ma'lumotlarni tanlashni xohlaymiz. Bunday holda, zarur taqqoslashlar soni ma'lumotlar elementlarining soniga bog'liq emas. Bir element katalogda indeks sifatida foydalanilganda element (1) vaqtida namuna olinadi. Misol uchun, aktsiyadagi menyudan taomlar buxgalteriyani soddalashtirish uchun raqamlar bilan soddalashtiriladi. "Aralashtirilgan basturma" turidagi har qanday nozikligi ma'lumotlar bazasida faqat 2 raqami bilan ko'rsatilgan. Go'shtning egasi faqatgina 2-tugma bilan ro'yxatga kiritilishi mumkin. Hashing yoki hashing (inglizcha hashing) - o'ziga xos algoritm bilan bajarilgan ma'lum uzunlikdagi tasodifiy uzunlikdagi boshlang'ich registrini (chiqish) bit majmuasiga aylantirish. Algoritmni bajaradigan va ishlashni amalga oshiradigan vazifaga "xash funktsiyasi" yoki "konvolution funktsiyasi" deb nomlanadi. Resurslar ma'lumotlariga kirish majmuasi, "kalit" yoki "xabar" deb ataladi. Konvertatsiya (chiqdi) natijalariga "xash", "xash kodi", "xash summasi", "xabar xulosasi" deb nomlanadi.