Қадағалаў сораўлары

1. Саралаў дегенде нени түсинесиз?

2. Саралаўдың тийкарғы усылларын айтып бериң.

3. Саралаўдың қайсы усылары қатаң усылға тийисли?

4. Саралаўдың жақсылаған усылларын айтып бериң.

5. Қандай саралаў турақлы делинеди?

6. Туўрыдан-туўры қосыў усылы идеясы неден ибарат?

7. Туўрыдан-туўры таңлаў усылы идеясы неден ибарат?

8. Туўрыдан-туўры алмастырыў усылы идеясы неден ибарат?

9. Жоқарыдағы усылларнинг бир биридан парқын айтып бериң.

10. Қайсы саралаў усылы ең эффектив болып есапланады?

11. Шелл усылы қайсы тийкарғы саралаў усылына тийисли?

9-лекция. Гилтлерди сәўлелендириў (жайластырыў) (2 саат)

Реже

1. Гилтлерди сәўлелендириў.

2. Сәўлелендириў функциясини таңлаў.

3. Тосқынлықты шешиў алгоритмлери

Жайластырыў усылы (хешлаштириш) мағлыўматлар структурасында элемент жайласқан орынды тез анықлаўға бағдарланған усыл. Жайластырыў усылында мағлыўматлар әпиўайы массив сыпатында аңлатылған болады. Усы усылда мағлыўматлар гилтлери Н сәўлелендириў жәрдеминде массив индекслерине сәўлелендириледи. Сол себепли усы сәўлелендириў «гилтлерди сәўлелендириў» деп аталады.

Элементти кестеге қосыўдан алдын оның адреси хеш-функция арқалы анықланады: A = h(K), бул жерде K – гилт, А – кестедеги элемент адреси болып, 0  А  N-1, шәрт орынлы болады.

Усы усылдан көбинесе тереклерде ҳәмде оны қолланыў табыс келтириўши мәселелерде пайдаланылады.

Гилтлерди сәўлелендириў менен байланыслы болған тийкарғы машқала бул гилтлердиң қабыл етиўи мүмкин болған мәнислер топламының яд адреси (массив индекслери) қабыл етилиўи мүмкин болған топламнан бир қанша кеңлигинде. Төмендегише мысал көрип шығайық. 1000 адам бар деп ойлайық. Ҳәр бир адамды анықлаў (идентификация қылыў) ушын гилт сыпатында атларын қарайық. Ҳәр бир ат 16 ға шекемги ҳәриптен ибарат болсын. Ол жағдайда биз болыўы мүмкин болған гилт мәнислери топламын (бул жерде болыўы мүмкин болған гилтлер топламы 26¹⁶ элменттен ибарат болады, егер әлипбе 26 ҳәриптен ибарат болса), 10³ индексли массивке сәўлелендириў керек болады. Жоқарыдағы мысалдан көринип турыпты, Н функция ишине сәўлелендириўши сәўлелендириў болады, яғный «көпшилик мәнис бир мәниске сәўлелендириледи». Егер қандайда бир гилт берилген болса, ол жағдайда излеў әмелиниң биринши адымы - гилт пенен байланысқан индексти есаплаў, яғный h = H(k), екинши ҳәм тийкарғысы – тексериў болып есапланады, яғный бунда ҳақыйқаттан да h функция Т массивте (кестеде) k гилтли элементтиң идентификация қылынып атырғаны тексериледи.

Сәўлелендириў функциясын таңлаў

Өз-өзинен белгили, сәўлелендириўдиң қәлеген жақсы функциясы гилтлерди берилген индекслер аралығына илажы барынша тең бөлистиреди. Егерде усы талап орынлы болса, ол жағдайда қосымша шәрт ҳәм шеклениўлер болмайды. Егерде сәўлелендириў пүткиллей тосынарлы болса және де жақсырақ болады. Усы усылга “майдалаў” (хешлаштириш), яғный аргументти бөлеклеў деп аталады. Н функция болса “жайластырыў функциясы” деп аталады. Н функция илажы барынша эффективли есапланыўы керек, яғный онша көп болмаған тийкарғы арифметикалық әмеллерден қуралған болыўы керек.

k гилт тәртип номерин барлық мүмкин болған гилтлер топламында аңлатыўшы ORD(k) функция берилген болсын. Буннан тысқары, i массив индекси 0 ... N — 1 аралықте жайласқан деп ойлайық, бул жерде N — массив өлшеми. Бундай жағдайда “жайластырыў функциясы” сыпатында төмендеги функцияны алыў мүмкин:

H(k) = ORD(k) MOD N

Егерде “жайластырыў функциясы” жоқарыдағы сыяқлы анықланатуғын болса, ол жағдайда гилт мәнислери индекслер өзгериўи аралығына тегис бөлистириледи. Сол себепли, гилтлерди сәўлелендириў әмелге асырылып атырған ўақытта көбинесе оны тийкар қылып алады. Буннан тысқары, егер массив узынлығы N екиниң қандайда бир дәрежесине тең болса, ол жағдайда функция эффектив есапланады. Лекин, егер гилт ҳәриплер избе-излигинен қуралған болса, ол жағдайда тап усындай функциядан бас тартыўға туўры келеди. Себеби, бундай жағдайда барлық гилтлер тең итималлыққа ийе деп қараў натуўғры болады. Нәтийжеде, тек ғана бир неше белгилер менен парқланыўшы сөзлерди бир индекске сәўлелендириў итималлығы жоқары болады, бул болса гилтлердиң тегис емес бөлистирилиўине алып келиўи мүмкин. Сол себепли, әмелий мәселелер шешилип атырғанда N сыпатында түп санларды алыў усыныс етиледи.

Тосқынлықты шешиў алгоритмлери

Егер берилген гилтке сәйкес кесте қатары керекли (изленип атырған) элементке ийе емеслиги белгили болса, ол жағдайда тосқынлық (“конфликт”) жүзеге келди делинеди. Бундай жағдай, егерде бир неше элемент бир индекске сәўлелендирилетуғын гилтлерге ийе болса жүзеге келеди. Бундай жағдайда усы берилген гилт арқалы толық анықланыўшы индекс бойынша екинши урыныў әмелге асырылады (Муқобил индекс қәлиплестириў арқалы). Екинши индексти қәлиплестириўдиң бир қанша усыллары бар. Ең әпиўайы жолларынан бири бул – биринши H(k) индекслери бир қыйлы болған барлық қатарды бир-бирине байланыстырыў, яғный байланысқан дизим сыяқлы. Бундай усылға туўрыдан-туўры байланыстырыў (direct chaining) деп аталады. Пайда болған дизим элементлери тийкарғы кестеде жайласыўы да жайласпаўы да мүмкин.

Бундай жағдайда дизим элементлери жайласқан яд толықлық (толып-тасыў, переполнение) тараўы делинеди. Усы усылдың кемшилиги, екилемши дизимлерди гүзетип барыў ҳәмде тосқынлыққа барыўшы элементлер дизими ҳәр бир қатарында мүрәжәт ушын орын ажыратыў керек болады.

Қарама-қарсылықты шешиўдиң және бир усылында болса берилген кестениң берилген қатарында керекли элемент бар болмаса, керекли элемент табылғанға шекем яки бос қатарға барғанша басқа қатарларды көрип шығады. Егер қарап шығыў бос қатарға шекем барып жетсе, ол жағдайда көрсетилген гилт берилген кестеде жоқ деп есапланады. Қарама-қарсылықты бундай шешиў усылына ашық адресли деп аталады. Тәбиий, қәлеген берилген гилт ушын индекслер избе-излиги екинши урыныўда бир қыйлы болыўы лазым. Бундай жағдайда қарап (көрип) шығыў алгоритми төмендеги схемада ислейди:

h = H(k)

i = 0

repeat

if T(h) = k

then элемент табылды

else if T(h) = free

then элемент кестеде жоқ

else {тосқынлық}

i := i + 1

h := H(k) + G(i)

endif

endif

until табылды, яки кестеде жоқ.