Xeshlash Darsning maqsadi - Ma'ruzaning maqsadi: identifikator jadvallarini tashkil qilishning asosiy usullarini o'rganish, identifikator jadvallarini tashkil qilishning turli usullariga xos bo'lgan afzalliklar va kamchiliklar to'g'risida tasavvurga ega bo'lish
- Ketma - ket va ikkilik qidiruv usullarida qidiruv vaqti n ning funktsiyasi bo'lib, n elementlar soni. Ulardan eng yaxshisi, ikkilik qidiruv, o(log n) murakkabligiga ega.
- Qidirishning samarali usullari keraksiz taqqoslashlar sonini minimallashtiradigan usullardir. Ideal holda, men keraksiz taqqoslashlar bo'lmagan ma'lumotlarni tashkil qilishni xohlayman.
- Agar har bir kalit bitta murojaat uchun chiqarilishi kerak bo'lsa, unda yozuvning holati (uning manzili) faqat ushbu yozuvning kalit qiymatiga bog'liq bo'lishi kerak. Shuning uchun kalitni ma'lum bir diapazonda ma'lum bir manzilga aylantirish usuli zarur.
Umumiy tushunchalar - Ma'lumotlarni jadval shaklida tashkil qilish, agar har bir yozuvning manzili bo'lsa, Xash jadvali deb nomlanadi a ushbu jadvalning h(k) funktsiyasining qiymati sifatida aniqlanadi, bu Xash funktsiyasi deb ataladi. Bu erda k-yozuv kalitining qiymati agar yozuvlar soni kichik bo'lsa va oldindan ma'lum bo'lsa, unda siz berilgan kalitlar to'plamini turli manzillarga aylantirish funktsiyasini yaratishingiz mumkin. Iloji bo'lsa, virtual xotiradan foydalanganda foydali bo'lgan ketma-ket manzillarga. Agar yozuvlar soni katta bo'lsa, unda bunday funktsiyani topish qiyin. Agar paydo bo'lish ehtimoli noldan farq qiladigan turli xil kalit qiymatlari soni Xash jadvalining hajmidan oshsa, funktsiyani qurish mumkin emas. Bunday holda, siz aniqlik g'oyasidan voz kechishingiz va Xash funktsiyasini Ohm-1 manzillari to'plamida ko'plab kalitlarni tarqatadigan funktsiya sifatida ko'rib chiqishingiz kerak.
- Kalit va manzil o'rtasidagi birma-bir muvofiqlik talabidan voz kechish, ikki xil K1 K2 tugmachalari uchun Xash funktsiyasining qiymati mos kelishi mumkinligini anglatadi: h(
Do'stlaringiz bilan baham: |
