#include #include using namespace std; long long Heshlash(char s[]) { long long h = 0; int base = 37; for(int i=0; i<=strlen(s); i++) { h = h* base + s[i] - 61 +1; } return h; }
163
int main() { char s[100]; for(int i=1; i<10; i++) { cin.getline(s,100); cout< cout< } } 9-jadval. Xesh jadvallardan foydalanish samaradorligi Konteyner / Amal Insert (qoʻshish) Remove (Oʻchirish) Izlash (find) Massiv
O(N)
O(N)
O(N)
Roʻyxat
O(1)
O(1)
O(N)
Saralangan massiv
O(N)
O(N)
O(logN)
Ikkilik
qidiruv
daraxti
O(logN)
O(logN)
O(logN)
Xesh-jadval O(1)
O(1)
O(1)
Barcha ma'lumotlar yaxshi bajarilgan konteynerlarni, yaxshi
tanlangan xesh funksiyalarini taqdim etdi.
Ushbu jadvaldan nega xesh jadvallardan foydalanish kerakligi juda
aniq koʻrinib turibdi. Ammo keyin qarama-qarshi savol tugʻiladi: nega
ular doimo ishlatilmaydi? Javob juda sodda: har doimgidek, birdaniga
hamma narsani olish mumkin emas, ya'ni: ham tezlikdan, ham xotiradan
yutib boʻlmaydi. Xesh jadvallari noqulay va ular operatsion jarayonning
164
asosiy savollariga tezda javob berishlari bilan birga, ulardan foydalanish
har doim juda qimmatga tushadi.
13.2. C++ dasturlash tilida xesh jadvallarni realizatsiya qilish C++ dasturlash tilida xesh jadvallarni hosil qilish uchun map
konteyneri aniqlangan. map konteyner vector, list, deque kabi boshqa
konteynerlarga juda o'xshaydi, lekin ozgina farqi mavjud. Bu
konteynerga birdaniga ikkita qiymat qo'yish mumkin. Shunday qilib, bu
map misolni batafsil ko'rib chiqaylik:
#include #include
165
cout << (*it).first << " : " << (*it).second << endl;
}
return 0;
}
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
