|
2-amaliy topshiriq!
|
bet | 15/16 | Sana | 14.11.2022 | Hajmi | 1.14 Mb. | | #30196 |
Bog'liq modul-1 funcsion, Psixologiya amaliy 3, cry1, Документ Microsoft Wordint s = h(key, 10); cout<return 0;
}
Kvadrat o’rtasi usuli. Kalit kvadratga oshiriladi va indeks sifatida olingan qiymatning bir necha o’rta raqamlari olinadi.
3-masala. Kalit 32 bit son, xesh funksiya qiymat sifatida kvadratning o’rtadagi 10 bit olinadi.
#include
#include
using namespace std;
int h(int key)
{
key *= key;
key >>= 11; //11 ta kichik bit olib tashlanadi return key % 1024; //10 kichik bitni oladi
}
int main()
{
int key = 145; int s = h(key); cout<return 0;
}
KOLLIZIYA MASALASINI YECHISH
Chiziqli probalash usulida kolliziya masalasini yechish mumkin. Agar hisoblangan xesh qiymati ko’rsatgan o’rinda boshqa element mavjud bo’lsa u holda unda keyin bo’sh o’rin qidiriladi. Bo’sh o’rin topilganda qiymat shu o’ringa yoziladi.
С++ STL kutubxonasida xeshlash
Xesh jadval bu konteyner bo’lib unga elementlarni qo’shish, o’chirish, qidirish o’rtacha O(1) murakkablikda amalga oshiriladi.
Xesh-jadval zanjirli yoki ochiq bo’lishi mumkin.
Zanjirli jadvalda asosiy ma’lumotga havola saqlanadi. Ya’ni xesh-jadvalda ma’lumotning o’zi saqlanmaydi, faqat xesh va havolalar saqlanadi (bucket).
Ochiq jadvalda ma’lumotlar jadvalning o’zida saqlanadi. Lekin asosiy ma’lumot aniq shu xeshda saqlanishiga kafolat yo’q.
STL zanjirli xesh-jadvalni unordered_set orqali realizatsiya qiladi.
Metodlari:
insert() – to’plamga element qo’shish
count() – elementlar sonini aniqlash
find() – elementni qidirsh
size() – to’plam o’lchamini aniqlash
erase() – to’plamdan elementni o’chirish
clear() – barcha elementlarni o’chirish
empty() – to’plam bo’shligini tekshirish
4-masala. unordered_set tipida xesh-jadval yaratiladi va ma’lumotlar jadvalga yuklanadi.
#include
#include using namespace std;
|
| |