Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Деректер құрылымы хэштеу схемасы
Data structure hashing scheme
Cuckoo hashing – компьютерлік бағдарламалауда кестедегі хэш функцияларының мәндерінің хэш-тұрастығын шешуге арналған схема, ең нашар жағдайда тұрақты іздеу уақытын қамтамасыз етеді. Атауы, кейбір көкек түрлерінің мінез-құлқынан алынған, онда көкек балапаны шайқап шығарып, ұядағы басқа жұмыртқаларды немесе жастарды қуып шығарады – бұл ұя паразиттерінің мінез-құлқының бір түрі; сол сияқты, Cuckoo hashing кестесіне жаңа кілт енгізу, ескі кілтті кестедегі басқа орынға ығыстыруы мүмкін.
Cuckoo hashing is a scheme in computer programming for resolving hash collisions of values of hash functions in a table, with worst case constant lookup time. The name derives from the behavior of some species of cuckoo, where the cuckoo chick pushes the other eggs or young out of the nest when it hatches in a variation of the behavior referred to as brood parasitism; analogously, inserting a new key into a cuckoo hashing table may push an older key to a different location in the table.
Тарих
Куку шашуын алғаш рет Расмус Паг және Флеминг Фриче Родлер 2001 жылғы конференция баяндамасында сипаттады. Бұл баяндама 2020 жылы Еуропалық алгоритмдер симпозиумының «Уақыт сынағынан өткен» сыйлығымен марапатталды.
Cuckoo hashing was first described by Rasmus Pagh and Flemming Friche Rodler in a 2001 conference paper. The paper was awarded the European Symposium on Algorithms Test of Time award in 2020.
Операциялар
Cuckoo хэшинг – хэш-таблицаның бос емес ұяшықтарында кілт немесе кілт-мәндік жұптар сақталатын ашық адрестеу түрі. Әр кілттің орналасуын анықтау үшін хэш-функция қолданылады, ал оның таблицадағы болуы (немесе оған сәйкес келетін мән) сол ұяшықты қарастыру арқылы табылады. Дегенмен, ашық адрестеу соқтығыстардан зардап шегеді, бұл бірнеше кілттің бір ұяшыққа түсуінен пайда болады. Cuckoo хэшингінің негізгі идеясы – соқтығыстарды шешу үшін бір емес, екі хэш-функцияны пайдалану. Бұл әр кілт үшін хэш-таблицада екі мүмкін орынды ұсынады. Алгоритмнің көп қолданылатын нұсқаларының бірінде хэш-таблица тең өлшемді екі кіші таблицаға бөлінеді, және әр хэш-функция осы екі таблицаның бірінде индексті анықтайды. Екі хэш-функция да бір таблицаға индекстер беруі мүмкін.
Cuckoo hashing is a form of open addressing in which each non empty cell of a hash table contains a key or key–value pair. A hash function is used to determine the location for each key, and its presence in the table (or the value associated with it) can be found by examining that cell of the table. However, open addressing suffers from collisions, which happens when more than one key is mapped to the same cell. The basic idea of cuckoo hashing is to resolve collisions by using two hash functions instead of only one. This provides two possible locations in the hash table for each key. In one of the commonly used variants of the algorithm, the hash table is split into two smaller tables of equal size, and each hash function provides an index into one of these two tables. It is also possible for both hash functions to provide indexes into a single table.
Жою
Жою операциясы іздеу болмағандықтан дереу орындалады. Егер кесте тым сирек болса, қысқарту операциясының бағасы ескерілмейді.
Deletion is performed in time since probing is not involved. This ignores the cost of the shrinking operation if the table is too sparse.
Практика
Іс жүзінде, кукушкалық хэштеу желілік зондтаудан шамамен 20–30% баяу, ал желілік зондтау – қолданылатын әдістердің ең жылдам түрі. Кукушкалық хэштеудің тағы бір жалпылама түрі – бұғатталған кукушкалық хэштеу, ол әр бөшкеге бірнеше кілтті орналастырып, теңгерімді үлестіру схемасын қолданады. Әр бөшкеге тек 2 кілтті қолдану 80% жоғары жүктемеге мүмкіндік береді. Кукушкалық хэштеудің тағы бір зерттелген түрі – қоймасы бар кукушкалық хэштеу. Бұл дерек құрылымындағы қойма – тұрақты мөлшердегі кілттер массиві, ол құрылымның негізгі хэш-кестесіне сәтті енгізілмейтін кілттерді сақтау үшін пайдаланылады. Бұл өзгеріс кукушкалық хэштеудің сәтсіздік деңгейін инверстік полиномдық функцияға дейін төмендетеді, оның көрсеткіші қойманың көлемін арттыру арқылы кез келген деңгейде үлкен болуы мүмкін. Дегенмен, үлкен қоймалар кілттерді іздеуді де баяулатады, егер олар болмаса немесе қоймада сақталса. Қойманы жоғары жүктеме коэффициенттеріне және төмен сәтсіздік деңгейлеріне қол жеткізу үшін екіден астам хэш-функциялармен немесе бұғатталған кукушкалық хэштеумен бірге пайдалануға болады. Қоймасы бар кукушкалық хэштеуді талдау, хэштеудің теориялық талдауында жиі қолданылатын кездейсоқ хэш-функциялар моделіне ғана емес, сонымен қатар практикалық хэш-функцияларға да қатысты. Кейбір мамандар кейбір процессорлардың кэштерінде бұрыс ассоциативтік кэш деп аталатын кукушкалық хэштеудің қарапайымдалған түрін ұсынады. Кукушкалық хэш-кестенің тағы бір нұсқасы – кукушкалық сүзгі, ол кукушкалық хэш-кестедегі сақталған кілттерді кілттерге басқа хэш-функцияны қолдану арқылы есептелген әлдеқайда қысқарақ іздермен алмастырады. Бұл іздерді олардың бастапқы кілттері белгілі болмаса, кукушкалық сүзгінің ішінде жылжытуға мүмкіндік беру үшін, әр іздің екі орны бірін-бірінен біттегі қосымша операциясы (XOR) немесе іздің хэші арқылы есептелуі мүмкін. Бұл дерек құрылымы Блум сүзгісіне ұқсас қасиеттері бар шамамен жиын мүшелігін анықтайтын дерек құрылымын құрайды: ол кілттер жиынының мүшелерін сақтай алады және сұраныс кілті жиынға жататынын тексереді, бірақ жалған оң нәтижелер (жиынға жататын емес кілттің жиынға жатады деп қате көрсетілуі) болуы мүмкін, бірақ жалған теріс нәтижелер болмайды. Дегенмен, ол Блум сүзгісінен бірнеше жағынан жақсырақ: жадты пайдалану тұрақты факторға сәйкес кішірек, сілтемелердің жақсы жергіліктілігі бар және (Блум сүзгілерінен айырмашылығы) қосымша жадты пайдаланбастан жиын элементтерін жылдам жоюға мүмкіндік береді.
In practice, cuckoo hashing is about 20–30% slower than linear probing, which is the fastest of the common approaches. Another generalization of cuckoo hashing called blocked cuckoo hashing uses more than one key per bucket and a balanced allocation scheme. Using just 2 keys per bucket permits a load factor above 80%. Another variation of cuckoo hashing that has been studied is cuckoo hashing with a stash. The stash, in this data structure, is an array of a constant number of keys, used to store keys that cannot successfully be inserted into the main hash table of the structure. This modification reduces the failure rate of cuckoo hashing to an inverse polynomial function with an exponent that can be made arbitrarily large by increasing the stash size. However, larger stashes also mean slower searches for keys that are not present or are in the stash. A stash can be used in combination with more than two hash functions or with blocked cuckoo hashing to achieve both high load factors and small failure rates. The analysis of cuckoo hashing with a stash extends to practical hash functions, not just to the random hash function model commonly used in theoretical analysis of hashing. Some people recommend a simplified generalization of cuckoo hashing called skewed associative cache in some CPU caches. Another variation of a cuckoo hash table, called a cuckoo filter, replaces the stored keys of a cuckoo hash table with much shorter fingerprints, computed by applying another hash function to the keys. In order to allow these fingerprints to be moved around within the cuckoo filter, without knowing the keys that they came from, the two locations of each fingerprint may be computed from each other by a bitwise exclusive or operation with the fingerprint, or with a hash of the fingerprint. This data structure forms an approximate set membership data structure with much the same properties as a Bloom filter: it can store the members of a set of keys, and test whether a query key is a member, with some chance of false positives (queries that are incorrectly reported as being part of the set) but no false negatives. However, it improves on a Bloom filter in multiple respects: its memory usage is smaller by a constant factor, it has better locality of reference, and (unlike Bloom filters) it allows for fast deletion of set elements with no additional storage penalty.