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

H (k) = ORD (k) MOD N
Egerde “jaylastırıw funktsiyasi” joqarıdaǵı sıyaqlı anıqlanatuǵın bolsa, ol halda gilt bahaları indeksler ózgeriwi aralıǵına tegis bólistiriledi. SHu sebepli, giltlerdi akslantirish ámelge asırılıp atırǵan waqıtta kóbinese onı tiykar qılıp alıwadı. Bunnan tısqarı, eger masiv uzınlıǵı N ikkining qanday da dárejesine teń bolsa, ol halda funktsiya nátiyjeli esaplanadı. Lekin, eger gilt xarflar izbe-izliginen shólkemlesken bolsa, ol halda áyne bunday funktsiyadan waz keshiwge tuwrı keledi. Sebebi, bunday jaǵdayda barlıq giltler teńextimollikga iye dep qaraw nadurıs boladı. Nátiyjede, tek ǵana bir neshe belgiler menen parıqlanıwshı sózlerdi bir indekske akslantirish extimolligi joqarı boladı, bul bolsa giltlerdi tegis emes bólistiriliwine alıp keliwi múmkin. SHu sebepli, ámeliy tımsallar hal qılınıp atırǵanda N retinde túpkilikli sanlardı alıw usınıs etiledi.
Qarama-qarsılıqtı sheshiw algoritmları
Eger berilgen giltga uyqas keste qatarı kerekli (qıdırılıp atırǵan ) elementke iye emesligi málim bolsa, ol halda qarama-qarsılıq (“konflikt”) júzege keldi dep ataladı. Bunday jaǵday, egerde bir neshe element bir indekske akslantiriladigan giltlerge iye bolsa júzege keledi. Bunday jaǵdayda usı berilgen gilt arqalı tolıq anıqlanıwshı indeks boyınsha ekinshi urınıw ámelge asıriladı (Alternativ indeks qáliplestiriw arqalı ). Ekinshi indeksti qáliplestiriwdiń bir qansha usılları bar. Eń ápiwayı jollarınan biri bul - birinshi H (k) indeksleri bir hil bolǵan barlıq qatardı bir-birine bólew, yaǵnıy baylanısqan dizim sıyaqlı. Bunday usılǵa tuwrıdan-tuwrı bólew (direct chaining) dep ataladı. Payda bolǵan dizim elementleri tiykarǵı kestede jaylasıwı da jaylawmasligi da múmkin.
Bunday jaǵdayda dizim elementleri jaylasqan yad tolıq (to'lib-tamaqtasısh, perepolnenie) tarawı dep ataladı. Bul usıldı kemshiligi, ekilemshi dizimlerdi gúzetip barıw hám de qarama-qarsılıqǵa baratuǵın elementler dizimi hár bir qatarında shaqırıq ushın jay ajıratıw kerek boladı.
Qarama-qarsılıqtı sheshiwdiń taǵı bir usılında bolsa berilgen kesteni berilgen qatarında kerekli element ámeldegi bolmasa, tokı kerekli element tapilguncha yamasa bos qatarǵa barǵanǵa shekem basqa qatarların kórip shıǵıladı. Eger qaray shıǵıw bos qatarǵa shekem barıp yetsa, ol halda kórsetilgen gilt berilgen kestede joq dep esaplanadı. Qarama-qarsılıqtı bunday sheshiw usılına ashıq adresli dep ataladı. Tuwrısıda, qálegen berilgen gilt ushın indeksler izbe-izligi ekinshi urınıwda bir hil bolıwı kerek. Bunday jaǵdayda qaray (kórip) shıǵıw algoritmı tómendegi sxemada isleydi: h = H (k) i = 0 repeat if T (h) = k then element tapildi else if T (h) = free
then element kestede joq
else {ziddiyat} i := i + 1 h := H (k) + G (i)
endiliktef
endiliktef until tapildi, yamasa kestede joq.