Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Соқтығысусыз хэш функциясы
Hash function without any collisions
Компьютер ғылымында, S жиыны үшін h кемел хэш функциясы – S жиынындағы әр түрлі элементтерді m бүтін сан жиынына бейнелейтін, ешқандай соқтығысусыз хэш функциясы болып табылады. Математикалық тұрғыдан алғанда, бұл инъективті функция. Кемел хэш функцияларын тұрақты нашар жағдайда қол жеткізу уақытымен іздеу кестесін іске асыру үшін пайдалануға болады. Кемел хэш функциясы, кез келген хэш функциясы сияқты, хэш кестелерін іске асыру үшін қолданылуы мүмкін, бірақ соқтығысуды шешуді іске асыру қажеттілігі болмайды. Сонымен қатар, кілттер деректерде болмаса және сұралатын кілттердің жарамды екені белгілі болса, кілттерді іздеу кестесінде сақтаудың қажеті жоқ, бұл жадты үнемдейді. Кемел хэш функцияларының кемшіліктері – кемел хэш функциясын құру үшін S жиыны белгілі болуы керек. S жиыны өзгерген жағдайда, динамикалық емес кемел хэш функцияларын қайта құру қажет. S жиыны жиі өзгеріп отырса, қосымша жад шығынымен динамикалық кемел хэш функцияларын пайдалануға болады.
In computer science, a perfect hash function h for a set S is a hash function that maps distinct elements in S to a set of m integers, with no collisions. In mathematical terms, it is an injective function. Perfect hash functions may be used to implement a lookup table with constant worst case access time. A perfect hash function can, as any hash function, be used to implement hash tables, with the advantage that no collision resolution has to be implemented. In addition, if the keys are not in the data and if it is known that queried keys will be valid, then the keys do not need to be stored in the lookup table, saving space. Disadvantages of perfect hash functions are that S needs to be known for the construction of the perfect hash function. Non dynamic perfect hash functions need to be re constructed if S changes. For frequently changing S dynamic perfect hash functions may be used at the cost of additional space.
Динамикалық кемелді хэштеу
Кемел хэш функциясын пайдалану жиі сұралатын үлкен жиын, S, болғанда ең жақсы, және ол сирек жаңартылады. Өйткені жиын S-тің кез келген өзгеруі хэш функциясының өзгертілген жиын үшін енді кемелді болмауына себеп болуы мүмкін. Жиын өзгерген сайын хэш функциясын жаңартатын әдістер динамикалық кемел хэштеу деп аталады, бірақ мұндай әдістерді іске асыру салыстырмалы түрде қиын.
Using a perfect hash function is best in situations where there is a frequently queried large set, S, which is seldom updated. This is because any modification of the set S may cause the hash function to no longer be perfect for the modified set. Solutions which update the hash function any time the set is modified are known as dynamic perfect hashing, but these methods are relatively complicated to implement.
Минималды кемелді хэш-функциясы
Минималды кемелді хэш-функция – n кілтті n тізбекті бүтін санға бейімдейтін кемелді хэш-функция, әдетте 0-ден n-1-ге дейінгі немесе 1-ден n-ге дейінгі сандарға. Мұны формалды түрде былай түсіндіруге болады: j және k белгілі бір шекті жиынның элементтері болсын. Онда h минималды кемелді хэш-функция болады, егер және тек қана h(j) = h(k) болса, j = k болады (инъективтілік) және h функциясының мәндер жиыны a деп аталатын бүтін санмен анықталса. Жалпы қолданысқа арналған минималды кемелді хэш-схемаға кем дегенде біт/кілт қажет екені дәлелденді. Егер S жиынындағы элементтердің саны n болса және олар белгілі бір диапазон ішіндегі бүтін сандардан тұрса, онда S жиынынан н-ге дейін нақты минималды кемелді хэш-функцияны тиімді құруға болады, бұл функция кеңістікте біт пайдаланады және тұрақты есептеу уақытын қамтамасыз етеді. Іс жүзінде, егер жеткілікті уақыт болса, шамамен 1,56 бит/кілт пайдаланатын минималды кемелді хэш-схемалар бар.
A minimal perfect hash function is a perfect hash function that maps n keys to n consecutive integers – usually the numbers from 0 to n − 1 or from 1 to n. A more formal way of expressing this is: Let j and k be elements of some finite set S. Then h is a minimal perfect hash function if and only if 1=h(j) = h(k) implies 1=j = k (injectivity) and there exists an integer a such that the range of h is It has been proven that a general purpose minimal perfect hash scheme requires at least bits/key. Assuming that is a set of size containing integers in the range , it is known how to efficiently construct an explicit minimal perfect hash function from to that uses space bits and that supports constant evaluation time. In practice, there are minimal perfect hashing schemes that use roughly 1.56 bits/key if given enough time.
Тапсырманы сақтау
F минималды кемелді хэш функциясы кілттер a1, a2, ..., an белгілі бір ретпен берілгенде реттілікті сақтайды, егер кез келген aj және ak кілттері үшін j < k болса, F(aj) < F(ak) болады. Бұл жағдайда функцияның мәні – барлық кілттердің реттелген тізімінде әрбір кілттің орны. Тұрақты қолжетімділік уақытымен минималды кемелді хэш функциясын іске асырудың қарапайым жолы – әрбір кілттің орнын іздеу кестесі ретінде сақтау үшін (қалыпты) кемелді хэш функциясын пайдалану. Бұл шешім биттерді пайдаланады, бұл кілттерді салыстыру функциясы кез келген болуы мүмкін жағдайда оңтайлы. Дегенмен, егер a1, a2, ..., an кілттері белгілі бір жиыннан алынған бүтін сандар болса, онда кеңістіктің биттерін ғана пайдаланып реттілікті сақтайтын хэш функциясын құруға болады. Бұл шектеудің де оңтайлы екені белгілі.
A minimal perfect hash function F is order preserving if keys are given in some order a1, a2, , an and for any keys aj and ak, j < k implies F(aj) < F(ak). In this case, the function value is just the position of each key in the sorted ordering of all of the keys. A simple implementation of order preserving minimal perfect hash functions with constant access time is to use an (ordinary) perfect hash function to store a lookup table of the positions of each key. This solution uses bits, which is optimal in the setting where the comparison function for the keys may be arbitrary. However, if the keys a1, a2, , an are integers drawn from a universe , then it is possible to construct an order preserving hash function using only bits of space. Moreover, this bound is known to be optimal.
Қатынасты құрылыстар
Жақсы өлшемделген хэш-кестелер іздеу, қосу және жою операциялары үшін амортизацияланған орташа есеп бойынша O(1) уақытты (тұрақты уақытты) қамтамасыз етеді, бірақ көптеген хэш-кесте алгоритмдері нашар жағдайда әлдеқайда ұзаққа созылатын уақытпен күреседі. Көптеген қолданбалар үшін (желілік маршрутизаторлар мен жад кэштері сияқты) нашар жағдайда да O(1) уақыт (тұрақты уақыт) тиімдірек болар еді. Нашар жағдайда O(1) іздеу уақытын (нашар жағдайда да тұрақты іздеу уақытын) қолдайтын хэш-кесте алгоритмдері өте аз. Олардың қатарында: толық хэштеу, динамикалық толық хэштеу, кукушка хэштеу, хопскотч хэштеу және кеңейтілмелі хэштеу.
While well dimensioned hash tables have amortized average O(1) time (amortized average constant time) for lookups, insertions, and deletion, most hash table algorithms suffer from possible worst case times that take much longer. A worst case O(1) time (constant time even in the worst case) would be better for many applications (including network router and memory caches). Few hash table algorithms support worst case O(1) lookup time (constant lookup time even in the worst case). The few that do include: perfect hashing; dynamic perfect hashing; cuckoo hashing; hopscotch hashing; and extendible hashing.