Кіріспе
Хаш-функцияларды таңдау техникасы Математика және информатикада әмбебап хэшинг (рандомизацияланған алгоритм немесе деректер құрылымы) — белгілі бір математикалық қасиеттері бар хаш-функциялар отбасынан кездейсоқ хаш-функцияны таңдауды білдіреді (төмендегі анықтаманы қараңыз). Бұл, егер деректерді қарсылас таңдаған жағдайда да, күтілетін соқтығысу санын азайтуға кепілдік береді. Хаш-функцияларды бүтін сандарға, векторларға, жолдарға қолдану үшін көптеген әмбебап отбасылар белгілі, олардың есептелуі көбінесе өте тиімді. әмбебап хэшинг компьютерлік ғылымда кеңінен қолданылады, мысалы, хаш-кестелерді, рандомизацияланған алгоритмдерді және криптографияны жүзеге асыруда.
In mathematics and computing, universal hashing (in a randomized algorithm or data structure) refers to selecting a hash function at random from a family of hash functions with a certain mathematical property (see definition below). This guarantees a low number of collisions in expectation, even if the data is chosen by an adversary. Many universal families are known (for hashing integers, vectors, strings), and their evaluation is often very efficient. Universal hashing has numerous uses in computer science, for example in implementations of hash tables, randomized algorithms, and cryptography.
Кіріспе
Біз кейбір ғаламның кілттерін (белгіленген) контейнерлерге орналастырғымыз келсе, алгоритм алдын ала белгісіз кілттердің деректер жиынтығын өңдеуге тиіс. Хэштеудің мақсаты, әдетте, соқтығысулардың санын азайту, яғни ғаламнан кілттердің бір контейнерге түсуін қамтамасыз ету. Детерминистік хэш-функция қарсыластық ортада ешқандай кепілдік бере алмайды, себебі қарсылас контейнердің алдын ала бейнесін таңдап алуы мүмкін. Бұл жағдайда барлық деректер кілттері бір контейнерге түсіп, хэштеудің мәнісіз болуына әкеледі. Сонымен қатар, детерминистік хэш-функция қайта хэштеуге мүмкіндік бермейді: кейде кіріс деректері хэш-функция үшін қолайсыз болып шығады (мысалы, тым көп соқтығысулар пайда болады), сондықтан хэш-функцияны өзгерту қажеттігі туындайды. Бұл мәселелерді шешу үшін хэш функцияларының отбасынан кездейсоқ функцияны таңдау керек. Функциялардың отбасы, егер ғаламның екі түрлі кілті хэш функциясы кездейсоқ түрде таңдалғанда, соқтығысу ықтималдығы белгілі бір мәннен аспаса, универсалды отбасы деп аталады. Бұл, хэш функциясы әр кілтке толығымен кездейсоқ хэш кодтарын тағайындағанда күтілетін соқтығысу ықтималдығымен сәйкес келеді. Кейде анықтама тұрақты фактормен жеңілдетіледі. Бұл ұғымды Картер мен Вегман 1977 жылы енгізген, және компьютерлік ғылымда көптеген қолданыс тапқан (мысалы, қараңыз). Егер соқтығысу ықтималдығының жоғарғы шегі болса, онда отбасы «жақындағы универсалдыққа» ие деп айтуға болады. Мысалы, универсалды отбасы жақындағы универсалдыққа ие. Көптеген, бірақ барлық емес, универсалды отбасыларда келесідей біркелкі айырмашылық қасиеті бар: хэш функциясы отбасынан кездейсоқ алынғанда, айырмашылық біркелкі таралады. Біркелкі айырмашылық қасиеті күштірек. (Сонымен қатар, универсалды отбасы XOR-универсалды болуы мүмкін, егер айырмашылықтың мәні біркелкі таратылса, онда біттік эксклюзивті немесе операциясы қолданылады. Бұл тек екінің дәрежесі болғанда ғана мүмкін.) Одан да күшті шарт – жұптық тәуелсіздік: егер кез келген екі кілттің хэш-мәндерінің жұбы толығымен кездейсоқ болса, онда бұл қасиетке ие болады. Жұптық тәуелсіздік кейде «күшті универсалдық» деп аталады. Тағы бір қасиет – біркелкілік. Егер барлық хэш-мәндер бірдей ықтималдыққа ие болса, онда отбасы біркелкі деп айтылады. Универсалдылық біркелкілікті білдірмейді. Алайда, күшті универсалдылық біркелкілікті білдіреді. Біркелкі қашықтық қасиетіне ие отбасы берілген жағдайда, жұптық тәуелсіз немесе күшті универсалды хэш отбасын жасау үшін хэш функцияларына біркелкі таратылған кездейсоқ тұрақты қосу арқылы алуға болады. (Сонымен қатар, егер екінің дәрежесі болса, XOR-универсалды хэш отбасынан жұптық тәуелсіздікке қол жеткізу үшін эксклюзивті немесе операциясын біркелкі таратылған кездейсоқ тұрақтымен орындауға болады.) Тұрақты ауытқу кейде қолданбаларда маңызды емес болғандықтан, біркелкі қашықтық қасиеті мен жұптық тәуелсіздік арасындағы айырмашылыққа көңіл бөлмейді. Кейбір қолданбалар үшін (мысалы, хэш-кестелерде) хэш-мәндерінің ең кіші маңызды биттері де универсалды болуы маңызды. Отбасы күшті универсалды болған кезде, бұл кепілдендіріледі: егер отбасы күшті универсалды болса, онда барлық функциялардан тұратын отбасы да күшті универсалды болады. Өкінішке орай, (тек) универсалды отбасылар үшін бұл дұрыс емес. Мысалы, сәйкестік функциясынан тұратын отбасы анық универсалды, бірақ функциядан тұратын отбасы универсалды бола алмайды. UMAC және Poly1305 AES және басқа да бірнеше хабарламаны аутентификациялау алгоритмдері универсалды хэштеуге негізделген. Мұндай қолданбаларда бағдарламалық қамтамасыз ету әрбір хабарлама үшін жаңа хэш-функцияны таңдайды, бұл хабарламаның бірегей нонсіне негізделген. Бірнеше хэш-кестелерді жүзеге асыру универсалды хэштеуге негізделген. Мұндай қолданбаларда бағдарламалық қамтамасыз ету әдетте «өте көп» кілттердің соқтығысқанын байқағаннан кейін ғана жаңа хэш-функцияны таңдайды; сол кезге дейін, бірдей хэш-функция қайта-қайта қолданыла береді. (Кейбір соқтығысуды шешу схемалары, мысалы, динамикалық кемелді хэштеу, соқтығысу болған сайын жаңа хэш функциясын таңдайды. Басқа соқтығысуды шешу схемалары, мысалы, кукушкалы хэштеу және 2 таңдаулы хэштеу, жаңа хэш функциясын таңдамас бұрын бірнеше соқтығысуларға мүмкіндік береді.) Бүкіл сандар, векторлар және тізбектер үшін ең жылдам белгілі универсалды және күшті универсалды хэш функцияларының шолуы табылды.
In other words, any two different keys of the universe collide with probability at most when the hash function is drawn uniformly at random from This is exactly the probability of collision we would expect if the hash function assigned truly random hash codes to every key. Sometimes, the definition is relaxed by a constant factor, only requiring collision probability rather than This concept was introduced by Carter and Wegman in 1977, and has found numerous applications in computer science (see, for example). If we have an upper bound of on the collision probability, we say that we have almost universality. So for example, a universal family has almost universality. Many, but not all, universal families have the following stronger uniform difference property:
, when is drawn randomly from the family , the difference is uniformly distributed in
Note that the definition of universality is only concerned with whether , which counts collisions. The uniform difference property is stronger. (Similarly, a universal family can be XOR universal if , the value is uniformly distributed in where is the bitwise exclusive or operation. This is only possible if is a power of two.) An even stronger condition is pairwise independence: we have this property when we have the probability that will hash to any pair of hash values is as if they were perfectly random: Pairwise independence is sometimes called strong universality. Another property is uniformity. We say that a family is uniform if all hash values are equally likely: for any hash value Universality does not imply uniformity. However, strong universality does imply uniformity. Given a family with the uniform distance property, one can produce a pairwise independent or strongly universal hash family by adding a uniformly distributed random constant with values in to the hash functions. (Similarly, if is a power of two, we can achieve pairwise independence from an XOR universal hash family by doing an exclusive or with a uniformly distributed random constant.) Since a shift by a constant is sometimes irrelevant in applications (e. g. hash tables), a careful distinction between the uniform distance property and pairwise independent is sometimes not made. For some applications (such as hash tables), it is important for the least significant bits of the hash values to be also universal. When a family is strongly universal, this is guaranteed: if is a strongly universal family with , then the family made of the functions for all is also strongly universal for Unfortunately, the same is not true of (merely) universal families. For example, the family made of the identity function is clearly universal, but the family made of the function fails to be universal. UMAC and Poly1305 AES and several other message authentication code algorithms are based on universal hashing. In such applications, the software chooses a new hash function for every message, based on a unique nonce for that message. Several hash table implementations are based on universal hashing. In such applications, typically the software chooses a new hash function only after it notices that "too many" keys have collided; until then, the same hash function continues to be used over and over. (Some collision resolution schemes, such as dynamic perfect hashing, pick a new hash function every time there is a collision. Other collision resolution schemes, such as cuckoo hashing and 2 choice hashing, allow a number of collisions before picking a new hash function). A survey of fastest known universal and strongly universal hash functions for integers, vectors, and
strings is found in.
Хашинг векторлары
Бұл бөлім машиналық сөздердің белгілі бір ұзындығындағы векторды хэштеуге арналған. Кірісті машиналық сөздердің векторы ретінде қарастырыңыз (әрқайсысы біттен тұратын бүтін сандар). Егер – біртекті айырмашылық қасиетіне ие әмбебап отбасы болса, келесі отбасы (Картер мен Вегманға дейін жетеді). Егер қос дәлдік арифметикасы қолжетімді болса, бұл көбейту-қайыру хэш функцияларының отбасымен жүзеге асырылады. Егер қос дәлдік операциялары қолжетімді болмаса, кірісті жарты сөздердің векторы ретінде қарастыруға болады (биттік бүтін сандар). Алгоритм көбейтуді қолданады, онда – вектордағы жарты сөздердің саны болды. Осылайша, алгоритм кіріс сөзінің біріне көбейту «жылдамдығымен» жұмыс істейді. Осы схеманы бүтін сандарды хэштеу үшін де қолдануға болады, олардың биттерін байттардың векторлары ретінде қарастыру арқылы. Бұл нұсқада векторлық техника кестелік хэштеу деп аталады және көбейтуге негізделген әмбебап хэштеу схемаларына практикалық балама ұсынады. Жоғары жылдамдықта күшті әмбебаптыққа да қол жеткізуге болады. Хэш-функцияны біттегі кездейсоқ бүтін сандардың векторымен бастаңыз. Нәтиже бітте күшті әмбебап болады. Эксперименттік түрде, бұл соңғы Intel процессорларында байтқа 0,2 CPU циклымен жұмыс істейтіні анықталды.
In practice, if double precision arithmetic is available, this is instantiated with the multiply shift hash family of hash functions. If double precision operations are not available, one can interpret the input as a vector of half words ( bit integers). The algorithm will then use multiplications, where was the number of half words in the vector. Thus, the algorithm runs at a "rate" of one multiplication per word of input. The same scheme can also be used for hashing integers, by interpreting their bits as vectors of bytes. In this variant, the vector technique is known as tabulation hashing and it provides a practical alternative to multiplication based universal hashing schemes. Strong universality at high speed is also possible. Initialize the hash function with a vector of random integers on bits. Compute
The result is strongly universal on bits. Experimentally, it was found to run at 0.2 CPU cycle per byte on recent Intel processors for .