Izlew hám xeshlaw algoritmler. Izlew algoritmler: Sızıqlı algoritm, ta’rtiplengen nawbetler, binar izlew. Xesh tablica hám xesh funksiyalar. Xesh funksiyalarg’a misal. Reje

10.Kelispewshilikti sheshiw algoritmleri

Kolliziya júz beriwin pútkilley aldın alatuǵın, jaqsı xesh-funksiyan qurıw múmkinbe?

Pútkilley kolliziyaǵa ushramaslıǵı ushın xesh-funksiyanıń hár bir natiyje mánisi unikal bolıwı kerek.
Kolliziya problemasın sheshiw ushın túrli usıllardı qόllaw múmkin. Wόlardan biri “rexeshlash” metodı esaplanadı.
Bul metodqa kόre, A element ushın xesh-funksiya arqalı esaplang`an h(A) adresi bos emes bolg`an yacheykanı kόrsetse, onda n1=h1(A) funksiya mánisin esaplaw zárúr ham n1 adresge tiyisli yacheykanı bos emesligin tekseriw kerek.
Eger n1 de bos emes bolsa, onda h2(A) mánis esaplanadı, sol sıyaqlı bosh yacheyka tolǵansha yamasa hi(A) náwbettegi mánis h(A) menen sáykes kelemen degenshe dawam etedi. Sόnǵi jaǵdayda identifikatorlar kestesi tolǵan hám bos orın basqa joq degen qátelik tuwrısında maǵluwmat beredi.
hi(A) funksiyanı esaplawdıń eń ápiwayı metodı, onı hi(A)=(h(A)+pi)modNm tiykarında qurıw bolıp, bul jerde pi qandayda bir esaplanǵan pútin san, Nm –identifikatorlar kestesindegi elementlerdiń maksimal sanı. Óz ornında eń ápiwayı usıl pi di ornına i di qoyıw boladı. Onda tόmendegi formulanı alamız hi(A)=(h(A)+i)modNm. Bul jaǵdayda xesh-funksiyanıń birdey mánislerin sáykes kelgen identifikatorlardı jaylastırıw ushın bos yacheykanı izlew xesh-funksiya h(A) kόrsetken orınnan baslanadı.


Qadaǵalaw ushın sorawlar
1. Izlew waziypası neden ibarat?
2. Kemnen kem ushrasatuǵın gilt degende neni túsinesiz?
3. Dizimde berilgen giltli element joq bolǵanda qaysı ámel orınlanadı?
4. Izbe-iz izlew hám indeksli izbe-iz izlewlerdiń parqı neden ibarat?
5. Olardan qaysisi nátiyjelirek hám ne sebepten?
6. Kesteni qayta tártiplewdiń qanday usılların bilesiz?
7. Tabılǵan elementti basına qoyiw usılınıń transpoziciya usılınan tiykarǵı parqı nelerden ibarat?
8. Bul usıllar maǵlumatlar qanday kóriniste berilgende tezrek isleydi?
9. Olar qanday dizimlerde isleydi, yaǵniy tártiplengen yamasa qalegen?
10. Binar izlewdińmánis mazmunı neden ibarat?
11. Qanday qılıp binar terekti shetlep ótiw múmkin?
12. Binar izlewdi massivtaisletiw múmkin be?
13. Eger bos bolmaǵan terekte tamir óshiriletuǵın bolsa, ol jaǵdayda onıń ornına qaysi element ótedi?
14. Giltlerdi almastırıw ne?
15. Sáwlelendiriw funksiyası waziypası neden ibarat?
16. Qanday jaǵdaylarda kelispewshilik júzege keledi?
17. Kelispewshilikti sheshiwdiń qanday usılların bilesiz?


Ádebiyatlar.
1. Adam Drozdek. Data structure and algorithms in C++. Fourth edition.
2013. Chapter 9.