2-tema. Xeshlash hám xesh kesteler Joba : Tuwrıdan-tuwrı adreslew kesteleri. Xesh kesteler

Bul usıldan kóbinese tereklerde hám de onı nátiyjeni ámelde qollanıw etiw muvoffaqiyat keltiretuǵın máselelerde paydalanıladı.
Giltlerdi akslantirish menen baylanıslı bolǵan tiykarǵı mashqala bul giltlerdi qabıllawı múmkin bolǵan bahalar kompleksin yad adresi (dızbek indeksleri) qabıllawı múmkin bolǵan jıynaqtan talay keńligi bolıp tabıladı. Tómendegishe mısal kórip shıǵayıq. Shama menen oylayıq, 1000 ta adam bar. Hár bir adamdı anıqlaw (identifikaciya qılıw ) ushın gilt retinde ısımların qaraylıq. Shama menen oylayıq hár bir at 16 danege shekem háripten shólkemlesken bolsın. Ol halda biz bolıwı múmkin bolǵan gilt bahaları kompleksin (bul jerde bolıwı múmkin bolǵan giltler kompleksi 2616 elmentdan ibarat boladı, eger álippe 26 xarfdan ibarat bolsa ), 103 indeksli dızbekke akslantirish kerek boladı. Joqarıdaǵı mısaldan kórinip turıptı, olda, N funktsiya ishine akslantiruvchi akslantirish boladı, yaǵnıy «ko'pgina baha bir bahaǵa akslantiriladi». Eger qandayda bir bir gilt berilgen bolsa, ol halda qıdırıw ámeliniń birinshi qádemi - gilt menen baylanısqan indeksti esaplaw, yaǵnıy h = H (k), ekinshi hám tiykarǵısı - tekseriw bolıp esaplanadı, yaǵnıy bunda haqıyqatlıqtan da h funktsiya T dızbekte (kestede) k giltli elementti identifikaciya etip atırǵanı tekseriledi.


Akslantirish funktsiyasın tańlaw
Óz-ózinen ekenin aytıw kerek, akslantirishning qálegen jaqsı funktsiyası giltlerdi berilgen indeksler aralıǵına ılajı bolǵanınsha teń bóliwleydi. Egerde bul talap orınlı bolsa, ol halda qosımsha shárt hám shekleniwler bolmaydı. Egerde akslantirish ulıwma tosınarlı bolsa taǵı da jaqsılaw boladı. Usı usılǵa “usaqlaw” (xeshlashtirish), yaǵnıy argumentni bóleklew dep ataladı. N funktsiya bolsa “jaylastırıw funktsiyasi” dep ataladı. Ayqınki, N funktsiya ılajı bolǵanınsha nátiyjeli xisoblanishi kerek, yaǵnıy onsha kóp bolmaǵan tiykarǵı arifmetik ámellerden shólkemlesken bolıwı kerek.
Shama menen oylayıq, k gilt tártip nomerin barlıq múmkin bolǵan giltler kompleksinde ańlatiwshı ORD (k) funktsiya berilgen bolsın. Bunnan tısqarı, i dızbek indeksi 0... N — 1 aralıqta jaylasqan dep shama menen oylaymız, bul jerde N — dızbek ólshemi. Bunday halda “jaylastırıw funktsiyasi” retinde tómendegi funktsiyanı alıw múmkin: