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
>
using
namespace
std
;
int
main
()
{
unordered_set
<
int
>
numbers 
{
1
,
100
,
10
,
70
,
100
};