Algoritm tushunchasi

Map bilan bogʻliq ba'zi asosiy funksiyalar quyida keltirilgan:

begin() - iteratorni mapdagi birinchi elementga qaytaradi
end() - iteratorni mapdagi oxirgi elementdan keyingi nazariy elementga
qaytaradi
size() - mapdagi elementlar sonini qaytaradi
max_size() - mapda saqlanishi mumkin bo'lgan elementlarning
maksimal sonini qaytaradi
empty() - mapning bo'shligini tekshiradi
pair_insert(keyvalue, mapvalue) - mapga yangi element qo'shiladi
erase(iterator position) - elementni iterator ko'rsatgan joydan olib
tashlaydi
erase(const g) - mapdan "g" kalit qiymatini olib tashlaydi
clear() - mapdagi barcha elementlarni olib tashlaydi
48 Kolliziya tushunchasi
Kolliziya muammosi. Tabiiyki, savol tugʻiladi, nega biz bir qator
katakchaga ikki marta kirib olishimiz mumkin emas, chunki har bir
elementga mutlaqo boshqacha natural sonlarni taqqoslaydigan
funksiyani taqdim etish shunchaki mumkin emas. Kolliziya muammosi
xesh funksiyasi turli elementlar uchun bir xil natural sonni hosil
qilganda paydo boʻladigan muammo.
Ushbu muammoning bir nechta yechimlari mavjud: zanjirlash
usuli va ikki marta xeshlash usuli.
O 'zingizni kichik do'konda sotuvchi ekanligingizni tasavvur qiling. Xaridor mahsulot sotib olayotganda, siz ularning narxini kitob bilan tekshirasiz. Agar kitobdagi yozuvlar alifbo tartibida tartiblanmagan bo'lsa, har bir satrda "apelsin" so'zini topish juda uzoq vaqt talab etadi. Aslida, siz 1-bobdan oddiy qidiruvni bajarishingiz kerak va buning uchun har bir yozuvni tekshirishingiz kerak bo'ladi. Unutmang, qancha vaqt ketadi? O (n). Agar kitob alifbo tartibida saralangan bo’lsa, ikkilik qidiruvdan foydalanishingiz mumkin, bu faqat O (log n) vaqtni oladi.Shunga qaramay, sizga O (n) va O (log n) vaqtlari bir xil emasligini eslatib qo'yay! Aytaylik, siz bir soniyada kitobdagi 10 ta yozuvni ko'rishingiz mumkin. Quyidagi jadvalda oddiy va ikkilik qidiruvlar qancha vaqt ketishi ko'rsatilgan.Ikkilik qidiruv juda tezligini allaqachon bilasiz. Ammo kitobdan ma'lumotlarni topish kassir uchun bosh og'rig'i, hatto uning tarkibi saralangan bo'lsa ham. Sahifalarni varaqlaganingizda, mijoz asta-sekin o'zini yo'qotishni boshlaydi. Tovarlarning barcha nomlarini va narxlarini eslab turadigan yordamchiga ega bo'lish ancha qulayroq bo'ladi. Keyin siz hech narsa qidirishingiz shart emas: siz yordamchidan so'rasangiz, u darhol javob beradi.S izning yordamchingiz Meggi sizga kitobning hajmidan qat'i nazar, O (1) vaqt ichida har qanday buyumning narxini aytib berishi mumkin. Ikkilik qidiruvdan ham tezroq.Faqatgina mo'jiza, qiz emas! Va bu Maggini qaerdan olish mumkin?Ma'lumotlar tuzilmalariga murojaat qilaylik. Hozircha siz ikkita ma'lumotlar tuzilishi bilan tanishasiz: massivlar va ro'yxatlar. (Steklar haqida gapirmayapman, chunki oddiy stekni qidirish mumkin emas). Kitob massiv sifatida amalga oshirilishi mumkin.Massivning har bir elementi aslida ikkita elementdan iborat: mahsulot nomi va uning narxi. Agar siz massivni nomlari bo'yicha saralasangiz, unda buyumning narxini aniqlash uchun ikkilik qidiruvni amalga oshirishingiz mumkin. Bu shuni anglatadiki, qidirish O (log n) vaqtni oladi. Ammo biz qidiruvni O (1) vaqt ichida bajarilishini istaymiz (boshqacha aytganda, siz "Maggi" ni yaratmoqchisiz). Xash funktsiyalari sizga bu borada yordam beradi.

Xesh funksiyalarda kolliziya – ikkita har xil ma’lumotdan bir xil

xesh qiymat hosil boʻlib qolishi. Kolliziyaning oldini olish yoʻllaridan
biri bu xesh jadval hisoblanadi. Xeshlash algoritmlarining bardoshliligi
xa xavfsizliligi kolliziyaga chidamliligi bilan aniqlanadi.