4-laboratoriya ishi. Mavzu: Xesh funksiyalar va xesh algoritmlarini tuzish. Ishdan maqsad

Shakl 14.4.

Ikki n dan kam tub sonlarning jadvali, stolning o'lchami bosh bo'lishi uchun zarur bo'lganda, hash stolni dinamik ravishda tarqatish uchun ishlatilishi mumkin. Berilgan diapazondagi har qanday ijobiy qiymat uchun ushbu jadvaldan undan 2 martaga kam farq qiluvchi ko'payishni aniqlash uchun foydalanish mumkin.

Butun sonli tugmachalarni qayta ishlashning yana bir varianti multiplikativ va modulli usullarni birlashtirishdir: siz kalitni 0 va 1 oralig'idagi doimiyga ko'paytirishingiz kerak, keyin M. bo'linish modulini bajaring. Boshqacha aytganda, siz funktsiyadan foydalanishingiz kerak. Nazariy jihatdan g'ayritabiiy xatti-harakatlarga olib kelishi mumkin bo'lgan qadriyatlar, M va kalitlarni raqamlash tizimining samarali bazasi o'rtasida bog'liqlik mavjud, ammo agar siz a-ning ixtiyoriy qiymatidan foydalansangiz, haqiqiy dasturda har qanday muammo bo'lmaydi. Ko'pincha f \u003d 0.618033 ... (oltin nisbat) ning qiymati a sifatida tanlanadi.

Ushbu mavzudagi boshqa ko'plab o'zgarishlar o'rganildi, xususan, siljitish va niqobni tanlash kabi samarali mashina ko'rsatmalaridan foydalanib bajarilishi mumkin bo'lgan hash funktsiyalari (bog'lanishlar bo'limiga qarang).

Belgilar jadvalidan foydalanadigan ko'plab dasturlarda kalitlar raqam emas va ular qisqa bo'lishi shart emas; tez-tez bu juda uzun bo'lishi mumkin bo'lgan alfanumerik raqamlardir. Averylongkey kabi so'z uchun hash funktsiyasini qanday hisoblash mumkin?

7 bitli ASCII kodida bu so'z 84 bitli raqamga to'g'ri keladi \\ boshlash (tekislang *) 97 \\ cdot 128 ^ (11) va + 118 \\ cdot 128 ^ (10) + 101 \\ cdot 128 ^ (9) + 114 \\ ^ (3) \\\\ & + 107 \\ cdot 128 ^ (2) + 101 \\ cdot 128 ^ (1) + 121 \\ cdot 128 ^ (0), \\ end (tekislang *),

ko'pgina kompyuterlar bilan odatiy arifmetik funktsiyalarni bajarish uchun juda katta. Va ko'pincha siz uzoqroq tugmachalarni qayta ishlashingiz kerak.

Uzoq tugmachalar uchun modulli hash funktsiyasini hisoblash uchun ular qismlarga bo'laklarga aylantiriladi. Modul funktsiyasining arifmetik xususiyatlaridan foydalanishingiz va Horner algoritmidan foydalanishingiz mumkin (4.9 "Mavhum ma'lumot turlari" bo'limiga qarang). Ushbu usul tugmachalarga mos keladigan raqamlarni yozishning boshqa usuliga asoslangan. Ko'rib chiqilayotgan misol uchun biz quyidagi ifodani yozamiz: \\ boshlamoq (tekislang *) (((((((((((((((97) cdot 128 ^ (11)) 128) (+) 118) \\ cdot 128 ^ (10) + 101)) 9) + 114) \\ cdot 128 ^ (8) + 121) \\ cdot 128 ^ (7) \\\\ & + 108) \\ cdot 128 ^ (6) + 111) \\ cdot 128 ^ (5) + 110) \\ cdot 128 ^ (4) + 103) \\ cdot 128 ^ (3) \\\\ & + 107) \\ cdot 128 ^ (2) + 101) \\ cdot 128 ^ (1) + 121. \\ end (tekislang *)

Ya'ni, satrni belgilar kodlashiga mos keladigan o'nlik raqamni chapdan o'ngga qarab ko'rib chiqishda, to'plangan qiymatni 128 ga ko'paytirganda va keyingi belgining kod qiymatini qo'shganda hisoblash mumkin. Uzun simli holatda bu hisoblash usuli oxir-oqibat umuman kompyuterda namoyish etilishi mumkin bo'lganidan kattaroq songa olib keladi. Ammo bu raqam kerak emas, chunki uning M.ga bo'linishidan faqat kichik (kichik) qismi talab qilinadi.Natijani katta to'plangan qiymatni saqlamasdan olish mumkin, chunki hisoblash paytida istalgan vaqtda, siz M ga ko'paygan sonni tashlab yuborishingiz mumkin - har safar ko'paytirsangiz va qo'shsangiz, siz M. bo'linish modulining faqat qolgan qismini saqlashingiz kerak bo'ladi, natijada biz uzoq raqamni hisoblash va keyin bo'linishni amalga oshirish imkoniga ega bo'lgandek bo'lamiz (qarang). mashq 14.10). Ushbu kuzatish uzun simlar uchun modulli xesh funktsiyalarini hisoblash uchun to'g'ridan-to'g'ri arifmetik usulga olib keladi - 14.1 dasturiga qarang. Ushbu dasturda yana bitta, oxirgi hiyla qo'llaniladi: baza 128 o'rniga, u 127 raqamini ishlatadi. Ushbu o'zgarish sababi keyingi paragrafda muhokama qilinadi.

Misol:
10. “Canon”, “Kodak”, “fujifilm”, “Sanyo”, “Sony ”, “ordro ”, “haier ”, “Pentax ”, “Panasonic” ma’lumotdan foydalangan xolda ASCII kodlari topilsin , ular asosida kalit aniqlansin, xesh jadvallar tuzilsin indexlar ishtirokida.

package r_xarfi; import java.util.Iterator; import java.util.TreeSet;

public class TreeSetExample {

public static void main(String[] args) {

String name = "admin";

char[] ch = name.toString().toCharArray(); //it will read and store each character of String and store into char[].

for(int i=0; i"+

(int)ch[i]); //this will print both character and its value}}}