Мазмұнға өту

Араластыру

Уикипедия — ашық энциклопедиясынан алынған мәлімет

Араластыру (Хеширование; hashing) — тез іздестіру мен кестелік түрлендіру мүмкіндігін жасақтайтын кестені ұйымдастыру әдісі. Бүл әдіс күтпеген жағдайда кестеге қосымша жаңа элемент енгізілген кезде ерекше пайдалы, мысалы, компиляторларда символдар кестесіне тән. Аралас кестеге енгізілетін әрбір элементтің ерекше кілті болады, ал енгізудің өзі кесте адрестері аумағының ішінде жататын бүтін сандар жиынына (аралас функция мәндеріне) кілтті бейнелейтін аралас функция арқылы жүзеге асырылады. Көрсетілген функция кесте адрестері бойынша кілттерді біркелкі үлестіруді қамтамасыз етуі тиіс. Алайда мұндай бейнелеу өзара бір мәнді бола алмайды. Әр түрлі екі кілтке бір ғана адрес сәйкес келуі мүмкін. Жалпы жағдайда аралас функция мәнін кестедегі негізгі адрес анықтайды. Егер осы адресі бар ұяшық бос болмаса, онда келесі адрестерді бос ұяшық табылғанша тексере береді (сонымен бірге кестенің сақиналық құрылымы бар деп есептелінеді) жоне элемент өз кілтімен бірге осы бос ұяшыққа орналастырылады. Кестедегі элементті іздестіру үшін ұқсас алгоритм пайдаланылады. Алдымен кілтке сәйкес аралас функция мәні есептеледі де, көрсетілген адрес бойынша тұрған кесте элементі тексеріледі. Егер элемент кілті талап етілген кілтпен сәйкес келсе, онда элемент табылған болып саналады, ал олай болмаған жағдайда керекті кілті бар элемент немесе бос ұяшық табылғанша кестенің келесі ұяшықтары тексеріледі. Соңғы жағдай кестеде іздестірілген кілттің жоқ екендігін айғақтайды. Өйткені жаңа элементті енгізу процедурасы міндетті түрде осы бос ұяшықты пайдаланған болар еді. Бұл әдіс тек кесте мөлшері орналастырылатын элементтер санынан біршама көп болған жағдайда ғана қолданылады. Егер аралас кесте 60%-дан артық толтырылмаса, онда оған жаңа элементті орналастыруға орта есеппен екіден көп емес ұяшықты тексеру қажет. Аралас функция мәні бос емес ұяшыққа сәйкес болған жағдайда туындайтын қақтығыстар мәселесін шешу үшін айтарлықтай күрделі әдістер пайдаланылуы мүмкін. Сонымен бірге бұл жағдайда кестелік түрлендіру жылдамдығы айтарлықтай артады. Кестелік түрлендірулер мен жаңа элементтерді орналастыру бірінен кейін бірі орындалады. Сондай-ақ кестеден элементтерді жойғаннан кейін босаған кеңістік қайтадан пайдаланылмайды. [1]

Дереккөздер

[өңдеу | қайнарын өңдеу]
  1. Қазақ тілі терминдерінің салалық ғылыми түсіндірме сөздігі: Информатика және компьютерлік техника / Жалпы редакциясын басқарған түсіндірме сөздіктер топтамасын шығару жөніндегі ғылыми-баспа бағдарламасының ғылыми жетекшісі, педагогика ғылымдарының докторы, профессор, Қазақстан Республикасы Мемлекеттік сыйлығының лауреаты А.Қ.Құсайынов. – Алматы: «Мектеп» баспасы» ЖАҚ, 2002 жыл. – 456 бет. ISBN 5-7667-8284-5