Mavzu: Xesh jadvallari va funktsiyalari

Ko'paytirish usuli (multiplikativ)
Multiplikativ xeshing uchun quyidagi formuladan foydalaniladi:

h(K) = [M * ((C * K) mod 1)]

Bu erda ma'lum bir sobit C tomonidan kalit ko'paytiriladi, intervalda yotgan [0..1]. Shundan so'ng, bu iboraning fraksiyonel qismi olinadi va natija xesh jadvalining chegarasidan tashqariga chiqmasligi uchun tanlangan m sobit bilan ko'paytiriladi. Operator [] eng katta tamsayı qaytaradi, bu argumentdan kamroq.
Agar doimiy C to'g'ri tanlangan bo'lsa, unda juda yaxshi natijalarga erishishingiz mumkin, ammo bu tanlov qilish qiyin. Donald qamchi (qarang: [3], p. 553), ko'paytirish ba'zan bo'linishdan ko'ra tezroq amalga oshirilishi mumkinligini ta'kidlaydi.
Multiplikativ usul haqiqiy fayllar tasodifiy emasligini yaxshi biladi. Misol uchun, faylda {k, K + d, K + 2d, ..., K + td} tugmachalari mavjud bo'lganda, ko'pincha kalitlarning ko'pligi arifmetik progressiyalardir. Misol uchun, {PART1, PART2,..., PARTN} kabi nomlarni ko'rib chiqing. Multiplikativ usul arifmetik progressni taxminan arifmetik progressiyaga aylantiradi h(K), h(K + d), h(K + 2d),... turli xil Xesh qiymatlari, tasodifiy vaziyatga nisbatan to'qnashuvlar sonini kamaytiradi. Biroq, adolat uchun, bo'linish usuli bir xil xususiyatga ega ekanligini ta'kidlash kerak.
Doimiy tanlashning alohida usuli-oltin qismning qiymati.= (√5 - 1)/2 ≈ 0,6180339887. Agar {φ} ketma-ketlikni olib bo'lsa, {2φ}, {3φ}... operator { } argument kasr qismini qaytaradi qaerda, keyin segmentida [0..1] bu juda teng taqsimlanadi. Boshqacha aytganda, har bir yangi qiymat eng katta intervalgacha tushadi. Bu hodisa birinchi marta J. Oderfeld (J. Oderfeld) tomonidan ko'rilgan va S. Sverchkovski (S. Świerczkowski) tomonidan tasdiqlangan (qarang: [8]). Dalillar Fibonacci raqamining muhim rol o'ynaydi. Xeshing bilan bog'liq holda, agar C sobit bo'lsa, oltin qismni tanlang, keyin funktsiya {PART1, PART2,..., PARTN} turlarining kalitlarini yaxshi tarqatadi. Bunday xeshing Fibonacci xeshing deb ataladi. Shu bilan birga, Fibonacci xeshing eng maqbul bo'lmasa (o'zgarish oxirgi holatda bo'lmasa) bir qator kalitlar mavjud [3].
Dinamik xeshing
Yuqorida tavsiflangan xeshing usullari statik, ya'ni. birinchi navbatda ma'lum bir xesh jadvali ajratiladi, uning hajmi uchun Xesh funktsiyasi uchun sobit tanlanadi. Afsuski, bu ma'lumotlar bazasi hajmi tez-tez va sezilarli darajada o'zgarib turadigan vazifalar uchun mos emas [9]. Ma'lumotlar bazasi o'sishi mumkin
to'qnashuvlarning o'sishi tufayli hosildorlikni yo'qotib, dastlabki xesh funktsiyasidan foydalaning;
disk maydonini keraksiz yo'qotishlarga olib keladigan "margin bilan" Xesh funktsiyasini tanlang;
funksiyani vaqti-vaqti bilan o'zgartirish, barcha manzillarni qayta hisoblash. Bu juda ko'p resurslarni oladi va bazani bir muncha vaqt o'chiradi.
Xesh tuzilishi [10] hajmini dinamik ravishda o'zgartirishga imkon beruvchi texnik mavjud. Bu dinamik xeshing. Xesh funktsiyasi faqat qisman elementga kirish uchun ishlatiladigan"pseudokey" deb nomlangan pseudokey ("pseudokey") hosil qiladi. Boshqa so'zlar bilan aytganda, barcha mumkin bo'lgan elementlarni hal qilish uchun etarli bo'lishi kerak, deb etarli uzoq bit ketma-hosil bo'ladi. Statik xeshing juda katta jadvalni talab qilganda (odatda kirishni tezlashtirish uchun ramda saqlanadi), bu erda band bo'lgan xotira hajmi ma'lumotlar bazasidagi elementlar soniga to'g'ridan-to'g'ri proportsionaldir. Jadvaldagi har bir yozuv alohida emas, balki ba'zi bloklarda ("bucket") saqlanadi. Ushbu bloklar saqlash qurilmasidagi jismoniy birliklar bilan mos keladi. Agar blokda yozuvni joylashtirish uchun ko'proq joy bo'lmasa, blok ikkiga bo'linadi va uning o'rniga ikkita yangi blok uchun marker qo'yiladi.