Ma’lumotlarni xeshlash algoritmlari. Xesh jadval va xesh funksiyalari

using
namespace
std
;
int
h
(char
*
key
,
int
m
)
{
int
len 
=
strlen(
key
);
int
s 
=
0
;
if(
len 
<
2
)
s 
=
key
[
0
];
else
{
s 
=
key
[
0
]
+
key
[
len
-
1
];
}
return
s 
%
m
;

---

}
int
main()
{
char
key
[]
=
{
'b'
,
'a'
,
'c'
};
int
s 
=
h
(
key
,
10
);
cout<<
s
;
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 
<
iostream
>
#include 
<
string.h
>
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<<
s
;
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 
<
iostream
>
#include 
<
unordered_set
>