Mavzu: Xesh jadval va xesh funksiyalar. Qidiruv algoritmlar samaradorligi Ishdan maqsad

Xeshlash – bu ma'lum bir turdagi va ixtiyoriy uzunlikdagikirishma'lumotlari massivini fiksirlangan uzunlikdagi chiquvchi bitlar qatoriga (butun son) aylantirish. Bunday akslantirish (aylantirish) xesh-funksiya deb ham ataladi. Xeshfunksiya – bukirishma’lumotlarini sonlarga aylantiruvchi funksiya bo’lib, bir xil ma’lumotlar to’plami hamma vaqt bir xil natija beradi Kriptografiyada, xesh-funksiya deb ixtiyoriy uzunlikdagi (bitlar yoki baytlar birliklarida) ma’lumotni biror fiksirlangan (belgilangan) uzunlikdagi (bitlar yoki baytlar birliklariga) qiymatga o‘tkazib beruvchi funksiyaga aytiladi.
• Kriptografiyada, xesh-funksiya deb ixtiyoriy uzunlikdagi (bitlar yoki baytlar birliklarida) ma’lumotni biror fiksirlangan (belgilangan) uzunlikdagi (bitlar yoki baytlar birliklariga) qiymatga o‘tkazib beruvchi funksiyaga aytiladi.
• Xesh funksiya (ingl. hash function) deb, ixtiyoriy uzunlikdagi M ma’lumotni fiksirlangan uzunlikdagi h(M)=H qiymatga akslantirib beruvchi, oson hisoblanadigan bir tomonlama funksiyaga aytiladi.
• Xesh funksiyalardan - statistik tajribalar o‘tkazishda, mantiqiy qurilmalarni tekshirishda, ma’lumotlar bazasida tez qidirib topish algoritmlarini yaratishda va ma’lumotlar bazasidagi ma’lumotlarning butunligini tekshirishda foydalaniladi.
Xesh jadval- bu assotsiativ massiv ko’rinishidagi ma’lumotlar tuzilmasi deb qarash mumkin.
• Xesh jadval- bu assotsiativ massiv ko’rinishidagi ma’lumotlar tuzilmasi deb qarash mumkin.
• Assosiativ (uyushgan yoki birikgan) massiv-indekslari kalitlardan tashkil topgan massiv. Bunda kalit tiplari har bir element uchun turlicha bo’lishi mumkin (satriy, bool, va b.). Assosiativ massivning har bir elementiga juft “kalit-qiymat” mos keladi va unga quyidagi bazaviy operatsiyalar mos keladi.
• INSERT- massivga juftlik qo’shish;
• REASSIGN-mavjud juftlikni o’zgartirish (yoki almashtirish);
• DELETE-juftlikni o’chirish;
• SEARCH- massivdan juftlikni qidirish
Bular standart operatsiyalar bo’lib, unga qo’shimcha amallar kiritish mumkin
Xesh funksiya: “xesh qiymat”, “daydjest”, “barmoq izlari” deb ham ataladi.
Xesh funksiya: “xesh qiymat”, “daydjest”, “barmoq izlari” deb ham ataladi.
Hesh jadvalning ikki xil variant mavjud:
o Zanjirsimon (ochiq xeshlash) kodlash;
o Ochiq adressatsiyali (yopiq xeshlash) kodlash;
Ochiq xeshlash:
Ochiq xeshlashning asosiy maqsadi- xesh jadval yacheykasida boshlangan ma’lumotlarni mantiqiy jihatdan bog’langan (zanjirsimon) ma’lumot xosil qilish. Zanjir deganda ko’rsatkichlari xesh jadval yacheykalarida saqlangan bog’langan ro’yhat nazarda tutiladi.

Jadvalning 1-chi ustuni xeshlangan kalit qiymatlar, ikkinchisi– ro’yhatga ko’rsatkich. Ma’lumot(ro’yhat) 3 ta maydondan iborat. : & — ro’yhat elementi adresi, $ — Ma’lumot, * — ko’rsatkich(ссылка).

Yopiq xeshlash
o Ochiq xeshlashdan asosiy farqi: xeshlash soni xesh jadval o’lchami bilan chegaralangan;
o Qo’shimch ma’lumot tuzilma talab etilmaydi;
o Jadval yacheykalarida ko’rsatkichlar emas, aksincha xesh kod orqali murojaat qilinadigan joriy massiv elementlari saqlanadi;
Xeshlash funksiyasi. Xesh-funksiya mexanizmi
o Xeshlash funksiyasi zamonaviy kriptografiyada asosiy rol o’ynaydi;
o Xesh funksiya yordamida:
o Ma’lumotlarning butunligini tekshirishda (o’zgarishlarni aniqlashda)
o Autintifikatsiyalashda
o ERI yaratish va tekshirishda keng qo’llaniladi;
Assosiativ massivni qo’llashga oid bo’lgan tipik misollardan biri bu masalan: Universitet kutubxonasidagi kitob va undan foydalanish uchun olgan talaba:
o Assosiativ massivni qo’llashga oid bo’lgan tipik misollardan biri bu masalan: Universitet kutubxonasidagi kitob va undan foydalanish uchun olgan talaba:
o Bunda kitob nomi - “Kalit” vazifasini bajarasa;
o Talaba ismi- qiymat vazifasini bajaradi.
Ko’rib turganimizdek bitta qiymatga bir-nechta kalitlar mos kelishi mumkin. Ammo kalitlar takrorlanmasligi lozim
Hashtable sinfi kalitlarni qiymatlar bilan taqqoslaydigan xesh jadvalini amalga oshiradi. Har qanday null bo'lmagan obyekt kalit yoki qiymat sifatida ishlatilishi mumkin. Obyektlarni heshtableda muvaffaqiyatli saqlash va olish uchun kalit sifatida ishlatiladigan obyektlar hashCode usuli va tenglar usulini qo'llashi kerak.

Hashtable

Hashtable sinfi kalitlarni qiymatlar bilan taqqoslaydigan xesh jadvalini amalga oshiradi. Har qanday null bo'lmagan obyekt kalit yoki qiymat sifatida ishlatilishi mumkin. Obyektlarni heshtableda muvaffaqiyatli saqlash va olish uchun kalit sifatida ishlatiladigan obyektlar hashCode usuli va tenglar usulini qo'llashi kerak.

Hashtable ko’rinishida yoziladi

Hashtable xususiyatlari

U HashMap-ga o'xshaydi, lekin sinxronlashtiriladi.

Hashtable kalit/qiymat juftligini xesh jadvalida saqlaydi.
Hashtable-da biz kalit sifatida ishlatiladigan obyektni va biz ushbu kalit bilan bog'lanmoqchi bo'lgan qiymatni belgilaymiz. Keyin kalit xeshlanadi va natijada olingan xesh-kod qiymat jadvalda saqlanadigan indeks sifatida ishlatiladi.
Hashtable sinfining dastlabki standart sig'imi 11, loadFactor esa 0,75.
HashMap hech qanday ro'yxatga olishni ta'minlamaydi, Hashtable esa tez ro'yxatga olishni ta'minlaydi.
K - ushbu xaritada saqlanadigan kalitlar turi
V - ko'rsatilgan qiymatlar turi
Parametrlar turi:
Hashtable yaratishning turli usullari mavjud.
Hashtable yaratishning turli usullari mavjud.
1. Hashtable(): Bu standart yuklanish koeffitsienti 0,75 va boshlang'ich sig'imi 11 bo'lgan bo'sh xesh-jadval yaratadi.
Hashtable ht = new Hashtable();

Hashtable ht1 = new Hashtable<>();

Hashtable ht2 = new Hashtable();
ht1.put(1, "one");
ht1.put(2, "two");
ht1.put(3, "three");
ht2.put(4, "four");
ht2.put(5, "five");
ht2.put(6, "six");
System.out.println("Mappings of ht1 : " + ht1);
System.out.println("Mappings of ht2 : " + ht2);
Chiqish ht1 xaritalari: {3=uch, 2=ikki, 1=bir}
ht2 xaritalari: {6=olti, 5=besh, 4=toʻrt}
2. Hashtable(int initialCapacity): Bu initialCapacity tomonidan belgilangan boshlang'ich o'lchamga ega va standart yuklash koeffitsienti 0,75 bo'lgan xesh jadvalini yaratadi.
2. Hashtable(int initialCapacity): Bu initialCapacity tomonidan belgilangan boshlang'ich o'lchamga ega va standart yuklash koeffitsienti 0,75 bo'lgan xesh jadvalini yaratadi.
Hashtable ht = new Hashtable(int initialCapacity);
3. Hashtable(int size, float fillRatio): Ushbu versiya fillRatio tomonidan belgilangan o'lcham va to'ldirish nisbati bilan belgilangan boshlang'ich o'lchamga ega bo'lgan xesh jadvalini yaratadi. To'ldirish nisbati: Asosan, u yuqoriga qarab o'lchamini o'zgartirishdan oldin xesh-jadval qanchalik to'liq bo'lishi mumkinligini aniqlaydi va uning qiymati 0,0 dan 1,0 gacha.
Hashtable ht = new Hashtable(int hajmi, float fillRatio);
4. Xesh jadvali(Map m ni kengaytiradi): Bu m dagi elementlar bilan ishga tushiriladigan xesh jadvalini yaratadi.
4. Xesh jadvali(Map m ni kengaytiradi): Bu m dagi elementlar bilan ishga tushiriladigan xesh jadvalini yaratadi.
Hashtable ht = new Hashtable(Map m);

Map hm = new HashMap<>();

hm.put(1, "one");
hm.put(2, "two");
hm.put(3, "three");
Hashtable ht2 = new Hashtable(hm);
System.out.println("Mappings of ht2 : " + ht2);
Chiqish
{3=uch, 2=ikki, 1=bir}
Jadval kaliti bo’yicha qiymatni chiqarish

if (ht.containsKey("vishal")) {

Integer a = ht.get(“keytext");
System.out.println("value for key"+ " \“keytext\" is:- " + a);
}
Hashtableda turli operatsiyalarni bajarish
o Elementlarni qo'shish: heshtablega element qo'shish uchun biz put() usulidan foydalanishimiz mumkin. Biroq, kiritish tartibi xesh-jadvalda saqlanmaydi. Ichkarida, har bir element uchun alohida xesh hosil bo'ladi va uni samaraliroq qilish uchun elementlar ushbu xesh asosida indekslanadi.

Hashtable ht1 = new Hashtable<>();

ht1.put(1, "text1");
ht1.put(2, "text2");
ht1.put(3, "text3");
System.out.println("Mappings of ht1 : " + ht1);
{3=text3, 2=text2, 1=text1}
2. Elementlarni o'zgartirish: Elementlarni qo'shgandan so'ng, agar biz elementni o'zgartirmoqchi bo'lsak, uni yana elementni put() usuli bilan qo'shish orqali amalga oshirish mumkin. Xesh-jadvaldagi elementlar kalitlar yordamida indekslanganligi sababli, kalitning qiymati biz o'zgartirmoqchi bo'lgan kalit uchun yangilangan qiymatni kiritish orqali o'zgartirilishi mumkin.
2. Elementlarni o'zgartirish: Elementlarni qo'shgandan so'ng, agar biz elementni o'zgartirmoqchi bo'lsak, uni yana elementni put() usuli bilan qo'shish orqali amalga oshirish mumkin. Xesh-jadvaldagi elementlar kalitlar yordamida indekslanganligi sababli, kalitning qiymati biz o'zgartirmoqchi bo'lgan kalit uchun yangilangan qiymatni kiritish orqali o'zgartirilishi mumkin.
// Update the value at key 2
ht1.put(2, "For");
3. Elementni olib tashlash: Xaritadan elementni olib tashlash uchun biz remove() usulidan foydalanishimiz mumkin. Ushbu usul kalit qiymatini oladi va agar u xaritada mavjud bo'lsa, ushbu xaritadan kalit uchun xaritalashni olib tashlaydi.
// Remove the map entry with key 4
ht1.remove(4);
4. Xeshtable bo'ylab harakatlanish: Jadvalni takrorlash uchun biz kengaytirilgan for loop dan foydalanishimiz mumkin . Quyida xesh-jadvalni takrorlash misoli keltirilgan.
4. Xeshtable bo'ylab harakatlanish: Jadvalni takrorlash uchun biz kengaytirilgan for loop dan foydalanishimiz mumkin . Quyida xesh-jadvalni takrorlash misoli keltirilgan.

ht.put("vishal", 10);

ht.put("sachin", 30);
ht.put("vaibhav", 20);
for (Map.Entry e : ht.entrySet())
System.out.println(e.getKey() + " "+ e.getValue());
Hashtable ma'lumotlar strukturasi - bu kalit/qiymat juftlarini saqlaydigan ma’lumotlar to'plami. U hashCode() usulidan kalit/qiymat juftligini qaysi qiymat bilan taqqoslash kerakligini aniqlash uchun foydalaniladi.
Hashtable ma'lumotlar strukturasi - bu kalit/qiymat juftlarini saqlaydigan ma’lumotlar to'plami. U hashCode() usulidan kalit/qiymat juftligini qaysi qiymat bilan taqqoslash kerakligini aniqlash uchun foydalaniladi.
Xesh funksiyasi ma’lumotlar ro'yxatida berilgan kalit uchun joyni aniqlashga yordam beradi. Umuman olganda, xeshkod - bu teng bo'lmagan obyektlar uchun teng bo'lgan manfiy bo'lmagan butun son va teng bo'lmagan obyektlar uchun teng bo'lishi yoki teng bo'lmasligi mumkin. Ikki obyekt teng yoki teng emasligini aniqlash uchun hashtable equals() usulidan foydalanadi.
Ikkita teng bo'lmagan obyektlar bir xil xeshkodga ega bo'lishi mumkin. Bu to'qnashuv deb ataladi . To'qnashuvlarni hal qilish uchun xeshtable ro'yxatlar qatoridan foydalanadi. Bitta qiymatga (massiv indeksi) moslashtirilgan juftliklar ro'yxatda saqlanadi va ro'yxat havolasi massiv indeksida saqlanadi.
Ikkita teng bo'lmagan obyektlar bir xil xeshkodga ega bo'lishi mumkin. Bu to'qnashuv deb ataladi . To'qnashuvlarni hal qilish uchun xeshtable ro'yxatlar qatoridan foydalanadi. Bitta qiymatga (massiv indeksi) moslashtirilgan juftliklar ro'yxatda saqlanadi va ro'yxat havolasi massiv indeksida saqlanadi.

Bu jadval xesh jadval deb ataladi. Kalit i=h(key) funksiyasi orqali aniqlanadi. Bu funksiya xesh-funksiya deb ataladi. Xeshlash algoritmi qidirilayotgan elementni uning kaliti bo’yicha xesh-jadvalda joylashuvini aniqlaydi. Xeshlash bu katta ko’plikni kichik ko’rinish saqlash usuli. Masalan, lug’at, bunda ma’lumotlar alifbo tartibida joylashadi, bu yerda alifbo kalit deb qabul qilinadi. Dasturlashda xeshlash termini 1967 yili Xellerman tarafidan kiritilgan. Haqiqatda xeshlash bu ma’lumotlarni kalitlari bo’yicha tez qidirish uchun adreslashning maxsus usuli.

Agar to’plam N ta elementdan iborat bo’lsa, uni 2N ta har xil ko’pliklarga ajratish mumkin. XESH FUNKSIYA VA XESH-JADVAL Funksiya, kichik to’plamlar xosiyati belgilaydi, ma’lumotlar elementi kalitini jadval indeksiga (xeshjadval) shakllantiradi. Bu funksiya xesh-funksiya deb ataladi: i = h(key) key – kalit, i – jadval indeksi. Funksiya natijasi bo’yicha bir necha kalit qiymatlari bir xil i indeksini berishi mumkin. Bu holat xeshlashda kolliziya deb ataladi. Yaxshi funksiya bu kolliziyani minimallashtiradigan va jadval bo’yicha ma’lumotlarni tengday tarqatadigan funksiya bo’lib hisoblanadi. Mukammal xesh-funksiya bu umuman kolliziya keltirib chiqarmaydigan funksiya. Xesh-jadval bu oddiy massiv bo’lib, standart emas ko’rinishda adreslanadi. Xeshlash usullari har xil bo’lib ular h(key) funksiyalari va konfliktlarni yechish usullari bilan farq qiladi. Masalan, m uzunlikdagi simvolli n ta qator berilgan. Qatorlardan ikkitasini tengligina q marta tekshirish kerak. Buning uchun O(q * n * m) murakkablikda amal bajariladi. Buning o’rniga biz barcha qatorlar xeshlash, saqlash keyin ikki qator solishtirish o’rniga ikki sonni solishtirishimiz mumkin. Xeshlanadigan obyektlar har xil bo’lishi mumkin. Simvolli qatorlar, rasm, graf, bitli fayllar. Xesh funksiya faqat bir tarafga ishlaydi, ya’ni xeshlangan kalitni qayta tiklab bo’lmaydi. XESH-FUNKSIYA METODLARI Bo’lish usuli. Dastlabki ma’lumot bu biror bir key butun kalit va m o’lchamli jadval. Bu funksiya natijasi jadval o’lchamini kalit bo’lishdan qolgan qoldiq. int h(int key, int m) { return key % m;

Adabiyotlar ro’yxati

1. Акбаров Д. Е. Ахборот хавфсизлигини таъминлашнинг криптографик усуллари ва уларнинг қўлланилиши – Т 2008
2. Арипов М.М., Пудовченко Ю.Е. Основы криптологии – Ташкент: 2004.
3. Бабаш А.В., Гольев Ю.И., Ларин Д.А. Шанкин Г.П. Криптографические идеи XIX века. Защита информации. Конфидент. 2004 г
4. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. –М.: издательство ТРИУМФ, 2003 Жельников В. Криптография от папируса до компьютера. М. АВF, 1997. – 336 c.
5. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии: Учебное пособие, 2-е изд. –М.: Гелиос АРВ, 2002.-480 с.
6. Vernam G.S. Cipher printing telegraph systems for secret wire and radio telegraphic communications, «J. Amer. Inst. Elec. Eng., vol. 55, pp. 109-115, 1926.