यूनिवर्सल हैशिंग: Difference between revisions
(→परिचय) |
No edit summary |
||
(5 intermediate revisions by 3 users not shown) | |||
Line 77: | Line 77: | ||
</ref> ऐसे अनुप्रयोगों में, सॉफ़्टवेयर प्रत्येक संदेश के लिए विशिष्ट अस्थायी रूप के आधार पर, प्रत्येक संदेश के लिए एक नया हैश फ़ंक्शन चुनता है। | </ref> ऐसे अनुप्रयोगों में, सॉफ़्टवेयर प्रत्येक संदेश के लिए विशिष्ट अस्थायी रूप के आधार पर, प्रत्येक संदेश के लिए एक नया हैश फ़ंक्शन चुनता है। | ||
कई हैश टेबल कार्यान्वयन यूनिवर्सल हैशिंग पर आधारित हैं। ऐसे अनुप्रयोगों में, प्रायः सॉफ़्टवेयर नया हैश फ़ंक्शन तभी चुनता है जब उसे पता चलता है कि "बहुत अधिक" कीज़ टकरा गई हैं तब तक, एक ही हैश फ़ंक्शन का बार-बार उपयोग किया जाता रहेगा। (कुछ संघटन समाधान योजनाएं, जैसे कि [[ गतिशील उत्तम हैशिंग |गतिशील पूर्ण हैशिंग]], प्रत्येक बार संघटन होने पर नया हैश फ़ंक्शन चुनती हैं। अन्य संघटन समाधान योजनाएं, जैसे [[कोयल हैशिंग|कुक्कू हैशिंग]] और [[2-विकल्प हैशिंग]], नया हैश फ़ंक्शन चुनने से पहले कई संघटनों की अनुमति देती हैं)। पूर्णांकों, | कई हैश टेबल कार्यान्वयन यूनिवर्सल हैशिंग पर आधारित हैं। ऐसे अनुप्रयोगों में, प्रायः सॉफ़्टवेयर नया हैश फ़ंक्शन तभी चुनता है जब उसे पता चलता है कि "बहुत अधिक" कीज़ टकरा गई हैं तब तक, एक ही हैश फ़ंक्शन का बार-बार उपयोग किया जाता रहेगा। (कुछ संघटन समाधान योजनाएं, जैसे कि [[ गतिशील उत्तम हैशिंग |गतिशील पूर्ण हैशिंग]], प्रत्येक बार संघटन होने पर नया हैश फ़ंक्शन चुनती हैं। अन्य संघटन समाधान योजनाएं, जैसे [[कोयल हैशिंग|कुक्कू हैशिंग]] और [[2-विकल्प हैशिंग]], नया हैश फ़ंक्शन चुनने से पहले कई संघटनों की अनुमति देती हैं)। पूर्णांकों, वेक्टरों और स्ट्रिंग्स के लिए सबसे तीव्र ज्ञात यूनिवर्सल और दृढ़ता से यूनिवर्सल हैश फ़ंक्शन का सर्वेक्षण पाया गया है।<ref> | ||
{{cite arXiv | {{cite arXiv | ||
| last = Thorup | | last = Thorup | ||
Line 111: | Line 111: | ||
== निर्माण == | == निर्माण == | ||
चूंकि किसी भी कंप्यूटर डेटा को एक या अधिक मशीनी शब्दों के रूप में दर्शाया जा सकता है, इसलिए प्रायः तीन प्रकार के डोमेन के लिए हैश फ़ंक्शन की आवश्यकता होती है- मशीनी शब्द ("पूर्णांक"), मशीनी शब्दों के निश्चित-लंबाई वाले वेक्टर, और चर-लंबाई वाले वेक्टर ("स्ट्रिंग्स")। | |||
=== | === हैशिंग पूर्णांक === | ||
यह खंड हैशिंग पूर्णांकों | यह खंड हैशिंग पूर्णांकों की स्थिति को संदर्भित करता है जो मशीन शब्दों में फिट होते हैं इस प्रकार, गुणा, जोड़, भाग आदि जैसे ऑपरेशन सस्ते मशीन-स्तरीय निर्देश हैं। माना यूनिवर्स को हैश किया जाना <math>\{0, \dots, |U| - 1\}</math> है। | ||
कार्टर और वेगमैन | कार्टर और वेगमैन<ref name=CW77 /> का मूल प्रस्ताव अभाज्य <math>p \ge |U|</math> चुनना और परिभाषित करना था | ||
: <math> h_{a,b}(x) = ((ax + b)~\bmod ~ p)~\bmod ~ m</math> | : <math> h_{a,b}(x) = ((ax + b)~\bmod ~ p)~\bmod ~ m</math> | ||
जहां <math>a,b</math> को <math>a \neq 0</math> के साथ यादृच्छिक रूप से चुने गए पूर्णांक सापेक्ष <math>p</math> हैं। (यह [[रैखिक सर्वांगसम जनरेटर]] की एकल पुनरावृत्ति है।) | |||
यह देखने के लिए कि <math>H = \{ h_{a,b} \}</math> यूनिवर्सल समूह है, ध्यान दें कि <math>h(x) = h(y)</math> केवल तभी मान्य होता है जब | |||
: <math>ax+b \equiv ay + b + i\cdot m \pmod{p}</math> | : <math>ax+b \equiv ay + b + i\cdot m \pmod{p}</math> | ||
कुछ पूर्णांक | कुछ पूर्णांक <math>i</math> के लिए <math>0</math> और <math>(p-1)/m</math> के बीच। चूँकि <math>p \ge |U|</math>, यदि <math>x \neq y</math> उनका अंतर <math>x-y</math> शून्येतर है और इसका व्युत्क्रम सापेक्ष <math>p</math> है। <math>a</math> के लिए हल करने पर परिणाम प्राप्त होता है | ||
: <math>a \equiv i\cdot m \cdot (x-y)^{-1} \pmod{p}</math>. | : <math>a \equiv i\cdot m \cdot (x-y)^{-1} \pmod{p}</math>. | ||
<math>a</math> के लिए <math>p-1</math> संभावित विकल्प हैं (चूंकि <math>a=0</math> को बाहर रखा गया है) और, <math>i</math> को अनुमत सीमा में भिन्न करते हुए, दाईं ओर के लिए <math>\lfloor (p - 1)/m \rfloor</math> संभावित गैर-शून्य मान हैं। इस प्रकार संघटन की संभावना है | |||
: <math>\lfloor (p - 1)/m \rfloor / (p-1) \le ((p-1)/m)/(p-1) = 1/m</math>. | : <math>\lfloor (p - 1)/m \rfloor / (p-1) \le ((p-1)/m)/(p-1) = 1/m</math>. | ||
देखने का | यह देखने का एक और तरीका है कि <math>H</math> यूनिवर्सल समूह है, [[सांख्यिकीय दूरी]] की धारणा के माध्यम से। अंतर <math>h(x) - h(y)</math> के रूप में लिखें | ||
: <math>h(x)-h(y) \equiv (a(x-y)~ \bmod~ p) \pmod{m}</math>. | : <math>h(x)-h(y) \equiv (a(x-y)~ \bmod~ p) \pmod{m}</math>. | ||
चूँकि <math>x - y</math> गैर-शून्य है और <math>a</math> को <math>\{1,\dots,p-1\}</math> में समान रूप से वितरित किया जाता है, इसलिए यह इस प्रकार है कि <math>a(x-y)</math> सापेक्ष <math>p</math> को <math>\{1,\dots,p-1\}</math> में भी समान रूप से वितरित किया जाता है। इस प्रकार <math>(h(x)-h(y)) ~\bmod~ m</math> का वितरण नमूनों के बीच <math>\pm 1/p</math> की संभावना के अंतर तक लगभग एक समान है। परिणामस्वरूप, एक समान समूह के लिए सांख्यिकीय दूरी <math>O(m/p)</math> है, जो <math>p \gg m</math> होने पर नगण्य हो जाती है। | |||
सरल हैश फ़ंक्शंस का | सरल हैश फ़ंक्शंस का समूह | ||
: <math>h_a(x) = (ax~\bmod~p)~\bmod~m</math> | : <math>h_a(x) = (ax~\bmod~p)~\bmod~m</math> | ||
केवल लगभग | केवल ''लगभग'' यूनिवर्सल है- सभी <math>x\neq y</math> के लिए <math>\Pr\{h_a(x) = h_a(y)\} \le 2/m</math>।<ref name=CW77 /> इसके अतिरिक्त, यह विश्लेषण लगभग दृढ़ है कार्टर और वेगमैन<ref name=CW77 /> दिखाते हैं कि <math>\Pr\{h_a(1) = h_a(m+1)\} \ge 2/(m-1)</math> जब भी <math>(p-1)~\bmod~ m = 1</math>। | ||
==== | ==== मापांक अंकगणित से बचना ==== | ||
हैशिंग पूर्णांकों के लिए कला की स्थिति डाइट्ज़फेलबिंगर एट अल द्वारा वर्णित | हैशिंग पूर्णांकों के लिए कला की स्थिति 1997 में डाइट्ज़फेलबिंगर एट अल. द्वारा वर्णित '''गुणन-परिवर्तन''' योजना है।<ref name=DHKP97> | ||
{{cite journal | {{cite journal | ||
| last1 = Dietzfelbinger | first1 = Martin | | last1 = Dietzfelbinger | first1 = Martin | ||
Line 161: | Line 161: | ||
| format = Postscript | | format = Postscript | ||
| year = 1997 | | year = 1997 | ||
}}</ref> | }}</ref> मापांक अंकगणित से बचने के कारण, इस विधि को लागू करना बहुत आसान है और अभ्यास (प्रायः कम से कम चार के कारक से<ref> | ||
{{cite web | {{cite web | ||
| last = Thorup | | last = Thorup | ||
Line 167: | Line 167: | ||
| title = Text-book algorithms at SODA | | title = Text-book algorithms at SODA | ||
| date = 18 December 2009 | url = http://mybiasedcoin.blogspot.com/2009/12/text-book-algorithms-at-soda-guest-post.html | | date = 18 December 2009 | url = http://mybiasedcoin.blogspot.com/2009/12/text-book-algorithms-at-soda-guest-post.html | ||
}}</ref>) | }}</ref>) में भी काफी तीव्रता से चलता है। योजना मानती है कि बिन्स की संख्या दो, <math>m=2^M</math>की क्षमता है। माना <math>w</math> मशीनी शब्द में बिट्स की संख्या है। फिर हैश फ़ंक्शंस को विषम धनात्मक पूर्णांक <math>a < 2^w</math> (जो <math>w</math> बिट्स के शब्द में फिट होते हैं) पर पैरामीटराइज़ किया जाता है। <math>h_{a}(x)</math> का मूल्यांकन करने के लिए, <math>x</math> को <math>a</math> सापेक्ष <math>2^w</math> से गुणा करें और फिर उच्च क्रम <math>M</math> बिट्स को हैश कोड के रूप में रखें। गणितीय संकेतन में, यह है | ||
: <math>h_a(x) = (a\cdot x\,\, \bmod\, 2^w)\,\, \mathrm{div}\,\, 2^{w-M} .</math> | : <math>h_a(x) = (a\cdot x\,\, \bmod\, 2^w)\,\, \mathrm{div}\,\, 2^{w-M} .</math> | ||
यह योजना समान अंतर गुण को संतुष्ट नहीं करती है और केवल <math>2/m</math>-लगभग-यूनिवर्सल है किसी भी <math>x\neq y</math>, <math>\Pr\{h_a(x) = h_a(y)\} \le 2/m</math> के लिए। | |||
यह विश्लेषण | हैश फ़ंक्शन के व्यवहार को समझने के लिए, ध्यान दें कि, यदि <math>ax \bmod 2^w</math> और <math>ay\bmod 2^w</math> में समान उच्चतम-क्रम वाले 'M' बिट्स हैं, तो <math>a(x-y) \bmod 2^w</math> के उच्चतम क्रम M बिट्स के रूप में या तो सभी 1 या सभी 0 हैं (यह इस पर निर्भर करता है कि <math>ax \bmod 2^w</math> या <math>ay \bmod 2^w</math> बड़ा है या नहीं)। मान लें कि <math>x-y</math> का सबसे कम महत्वपूर्ण सेट बिट स्थिति <math>w-c</math> पर दिखाई देता है। चूँकि <math>a</math> एक यादृच्छिक विषम पूर्णांक है और विषम पूर्णांकों का व्युत्क्रम <math>Z_{2^w}</math> वलय में होता है, इसलिए यह इस प्रकार है कि <math>a(x-y)\bmod 2^w</math> को <math>w</math>-बिट पूर्णांकों के बीच समान रूप से वितरित किया जाएगा, जिसमें स्थिति <math>w-c</math> पर सबसे कम महत्वपूर्ण सेट बिट होगा। इसलिए संभावना यह है कि ये बिट्स सभी 0 या सभी 1 हैं, इसलिए अधिकतम <math>2/2^M=2/m</math> है। दूसरी ओर, यदि <math>c < M</math>, तो <math>a(x-y) \bmod 2^w</math> के उच्च-क्रम M बिट्स में 0 और 1 दोनों सम्मिलित हैं, इसलिए यह निश्चित है कि <math>h(x) \ne h(y)</math>। अंत में, यदि <math>c=M</math> है तो <math>a(x-y) \bmod 2^w</math> का बिट <math>w-M</math> 1 है और <math>h_a(x)=h_a(y)</math> यदि और केवल यदि बिट्स <math>w-1,\ldots,w-M+1</math> भी 1 है, जो संभावना <math>1/2^{M-1}=2/m</math> के साथ होता है। | ||
वास्तव में ' | |||
यह विश्लेषण दृढ़ है, जैसा कि उदाहरण <math>x=2^{w-M-2}</math> और <math>y=3x</math> के साथ दिखाया जा सकता है। वास्तव में 'यूनिवर्सल' हैश फ़ंक्शन प्राप्त करने के लिए, कोई व्यक्ति गुणा-जोड़-स्थानांतरण योजना का उपयोग कर सकता है जो उच्च-क्रम बिट्स चुनता है | |||
: <math>h_{a,b}(x) = ((ax + b) \bmod 2^{w+M})\, \mathrm{div}\, 2^w ,</math> | : <math>h_{a,b}(x) = ((ax + b) \bmod 2^{w+M})\, \mathrm{div}\, 2^w ,</math> | ||
जहां <math>a</math>, <math>a < 2^{2w}</math> के साथ यादृच्छिक धनात्मक पूर्णांक है और <math>b</math>, <math>b < 2^{2w}</math> के साथ यादृच्छिक गैर-ऋणात्मक पूर्णांक है। इसके लिए <math>2w</math>-बिट अहस्ताक्षरित पूर्णांकों पर अंकगणित करने की आवश्यकता है। गुणा-स्थानांतरण का यह संस्करण डिट्ज़फेलबिंगर के कारण है, और बाद में वोल्फ़ेल द्वारा इसका अधिक सटीक विश्लेषण किया गया।<ref name="w99">{{cite conference | |||
इसके लिए | |||
| last1 = Woelfel | first1 = Philipp | | last1 = Woelfel | first1 = Philipp | ||
| title = Efficient Strongly Universal and Optimally Universal Hashing | | title = Efficient Strongly Universal and Optimally Universal Hashing | ||
Line 194: | Line 186: | ||
| year = 1999 | | year = 1999 | ||
}}</ref> | }}</ref> | ||
=== हैशिंग वेक्टर === | |||
यह अनुभाग मशीनी शब्दों के एक निश्चित-लंबाई वाले वेक्टर को हैश करने से संबंधित है। इनपुट को <math>k</math> मशीन शब्दों (प्रत्येक <math>w</math> बिट के पूर्णांक) के वेक्टर <math>\bar{x} = (x_0, \dots, x_{k-1})</math> के रूप में व्याख्या करें। यदि <math>H</math> एक समान अंतर गुण वाला यूनिवर्सल समूह है, तो निम्नलिखित समूह (कार्टर और वेगमैन के समय का<ref name=CW77 />) में भी एक समान अंतर गुण है (और इसलिए यूनिवर्सल है)- | |||
: <math>h(\bar{x}) = \left( \sum_{i=0}^{k-1} h_i(x_i) \right)\,\bmod~m</math>, जहां प्रत्येक <math>h_i\in H</math> को यादृच्छिक रूप से स्वतंत्र रूप से चुना जाता है। | |||
: <math>h(\bar{x}) = \left( \sum_{i=0}^{k-1} h_i(x_i) \right)\,\bmod~m</math>, जहां प्रत्येक <math>h_i\in H</math> यादृच्छिक रूप से स्वतंत्र रूप से चुना जाता है। | |||
यदि <math>m</math> दो की घात है, तो योग को अपवर्जित या से प्रतिस्थापित किया जा सकता है।<ref name="thorup09"> | |||
{{cite conference | {{cite conference | ||
| last = Thorup | first = Mikkel | author-link = Mikkel Thorup | | last = Thorup | first = Mikkel | author-link = Mikkel Thorup | ||
Line 212: | Line 202: | ||
| isbn = 978-0-89871-680-1 | citeseerx = 10.1.1.215.4253 | | isbn = 978-0-89871-680-1 | citeseerx = 10.1.1.215.4253 | ||
}}, section 5.3 | }}, section 5.3 | ||
</ref> | </ref> | ||
अभ्यास में, यदि द्विक-परिशुद्धता अंकगणित उपलब्ध है, तो इसे हैश फ़ंक्शंस के गुणा-स्थानांतरण हैश समूह के साथ त्वरित किया जाता है। प्रत्येक <math>2w</math> बिट्स पर यादृच्छिक विषम पूर्णांकों के वेक्टर <math>\bar{a} = (a_0, \dots, a_{k-1})</math> के साथ हैश फ़ंक्शन प्रारंभ करें। फिर यदि <math>M\le w</math> के लिए डिब्बे की संख्या <math>m=2^M</math> है- | |||
: <math>h_{\bar{a}}(\bar{x}) = \left(\big( \sum_{i=0}^{k-1} x_i \cdot a_i \big) ~\bmod ~ 2^{2w} \right) \,\, \mathrm{div}\,\, 2^{2w-M}</math>. | : <math>h_{\bar{a}}(\bar{x}) = \left(\big( \sum_{i=0}^{k-1} x_i \cdot a_i \big) ~\bmod ~ 2^{2w} \right) \,\, \mathrm{div}\,\, 2^{2w-M}</math>. | ||
गुणन की संख्या को आधा करना संभव है, जो | गुणन की संख्या को आधा करना संभव है, जो अभ्यास में मोटे तौर पर दो गुना गति में बदल जाता है।<ref name="thorup09" /> प्रत्येक <math>2w</math> बिट्स पर यादृच्छिक विषम पूर्णांकों के वेक्टर <math>\bar{a} = (a_0, \dots, a_{k-1})</math> के साथ हैश फ़ंक्शन को आरंभ करें। निम्नलिखित हैश समूह यूनिवर्सल है-<ref name="black"> | ||
{{cite conference | {{cite conference | ||
| last1 = Black | first1 = J. | | last1 = Black | first1 = J. | ||
Line 230: | Line 221: | ||
: <math>h_{\bar{a}}(\bar{x}) = \left(\Big( \sum_{i=0}^{\lceil k/2 \rceil} (x_{2i} + a_{2i}) \cdot (x_{2i+1} + a_{2i+1}) \Big) \bmod ~ 2^{2w} \right) \,\, \mathrm{div}\,\, 2^{2w-M}</math>. | : <math>h_{\bar{a}}(\bar{x}) = \left(\Big( \sum_{i=0}^{\lceil k/2 \rceil} (x_{2i} + a_{2i}) \cdot (x_{2i+1} + a_{2i+1}) \Big) \bmod ~ 2^{2w} \right) \,\, \mathrm{div}\,\, 2^{2w-M}</math>. | ||
यदि | यदि द्विक परिशुद्धता ऑपरेशन उपलब्ध नहीं हैं, तो कोई इनपुट को आधे-शब्दों (<math>w/2</math>-बिट पूर्णांक) के वेक्टर के रूप में व्याख्या कर सकता है। इसके बाद एल्गोरिदम <math>\lceil k/2 \rceil</math> गुणन का उपयोग करेगा, जहां <math>k</math> वेक्टर में आधे शब्दों की संख्या थी। इस प्रकार, एल्गोरिदम इनपुट के प्रति शब्द गुणन की "दर" पर चलता है। | ||
उसी योजना का उपयोग पूर्णांकों | उसी योजना का उपयोग पूर्णांकों के बिट्स को बाइट्स के वेक्टर के रूप में व्याख्या करके, हैशिंग पूर्णांकों के लिए भी किया जा सकता है। इस प्रकार में, वेक्टर तकनीक को सारणीकरण हैशिंग के रूप में जाना जाता है और यह गुणन-आधारित यूनिवर्सल हैशिंग योजनाओं के लिए व्यावहारिक विकल्प प्रदान करता है।<ref>{{cite conference | ||
| last1 = Pătraşcu | first1 = Mihai | author1-link = Mihai Pătrașcu (computer scientist) | | last1 = Pătraşcu | first1 = Mihai | author1-link = Mihai Pătrașcu (computer scientist) | ||
| last2 = Thorup | first2 = Mikkel | author2-link = Mikkel Thorup | | last2 = Thorup | first2 = Mikkel | author2-link = Mikkel Thorup | ||
Line 240: | Line 231: | ||
| pages = 1–10 | | pages = 1–10 | ||
| work = Proceedings of the 43rd annual ACM Symposium on Theory of Computing (STOC '11) | | work = Proceedings of the 43rd annual ACM Symposium on Theory of Computing (STOC '11) | ||
| year = 2011| isbn = 9781450306911 }}</ref> | | year = 2011| isbn = 9781450306911 }}</ref> | ||
उच्च गति पर | |||
उच्च गति पर सुदृढ़ सार्वभौमिकता भी संभव है।<ref name="kaser2013">{{cite journal | |||
| last1 = Kaser | first1 = Owen | | last1 = Kaser | first1 = Owen | ||
| last2 = Lemire | first2 = Daniel | | last2 = Lemire | first2 = Daniel | ||
Line 252: | Line 244: | ||
| pages = 1624–1638 | | pages = 1624–1638 | ||
| doi = 10.1093/comjnl/bxt070 | | doi = 10.1093/comjnl/bxt070 | ||
| publisher = Oxford University Press}}</ref> | | publisher = Oxford University Press}}</ref> <math>2w</math> बिट्स पर यादृच्छिक पूर्णांकों के वेक्टर <math>\bar{a} = (a_0, \dots, a_{k})</math> के साथ हैश फ़ंक्शन प्रारंभ करें। गणना करें | ||
: <math>h_{\bar{a}}(\bar{x})^{\mathrm{strong}} = (a_0 + \sum_{i=0}^{k-1} a_{i+1} x_{i} \bmod ~ 2^{2w} ) \,\, \mathrm{div}\,\, 2^w </math>. | : <math>h_{\bar{a}}(\bar{x})^{\mathrm{strong}} = (a_0 + \sum_{i=0}^{k-1} a_{i+1} x_{i} \bmod ~ 2^{2w} ) \,\, \mathrm{div}\,\, 2^w </math>. | ||
परिणाम | परिणाम <math>w</math> बिट्स पर दृढ़ता से यूनिवर्सल है। प्रायोगिक तौर पर, यह हाल के इंटेल प्रोसेसर पर <math>w = 32</math> के लिए 0.2 सीपीयू (CPU) चक्र प्रति बाइट पर रन हुआ पाया गया। | ||
=== हैशिंग स्ट्रिंग === | === हैशिंग स्ट्रिंग === | ||
इसका तात्पर्य मशीनी शब्दों के चर-आकार वाले वेक्टर को हैश करने से है। यदि स्ट्रिंग की लंबाई को छोटी संख्या से सीमित किया जा सकता है, तो ऊपर से (वैचारिक रूप से वेक्टर को ऊपरी सीमा तक शून्य के साथ विस्तारण) वेक्टर हल का उपयोग करना सबसे अच्छा है। आवश्यक स्थान स्ट्रिंग की अधिकतम लंबाई है, लेकिन <math>h(s)</math> का मूल्यांकन करने का समय केवल <math>s</math> की लंबाई है। जब तक स्ट्रिंग में शून्य वर्जित हैं, सार्वभौमिकता को प्रभावित किए बिना हैश फ़ंक्शन का मूल्यांकन करते समय शून्य-विस्तारण को अनदेखा किया जा सकता है।<ref name="thorup09" /> ध्यान दें कि यदि स्ट्रिंग में शून्य की अनुमति है, तो विस्तारण से पहले सभी स्ट्रिंग्स में एक काल्पनिक गैर-शून्य (उदाहरण के लिए, 1) वर्ण जोड़ना सबसे अच्छा हो सकता है- इससे यह सुनिश्चित होगा कि सार्वभौमिकता प्रभावित नहीं होती है।<ref name="kaser2013" /> | |||
अब मान | अब मान लें कि हम <math>\bar{x} = (x_0,\dots, x_\ell)</math>, को हैश करना चाहते हैं, जहां <math>\ell</math> पर एक अच्छी सीमा प्राथमिकता से ज्ञात नहीं है। व्यवहार द्वारा प्रस्तावित यूनिवर्सल समूह<ref name="DGMP"> | ||
{{cite conference | {{cite conference | ||
| last1 = Dietzfelbinger | first1 = Martin | | last1 = Dietzfelbinger | first1 = Martin | ||
Line 272: | Line 264: | ||
| pages = 235–246 | | pages = 235–246 | ||
| year = 1992 | | year = 1992 | ||
}}</ref> स्ट्रिंग | }}</ref> स्ट्रिंग <math>x</math> को बहुपद सापेक्ष बड़े अभाज्य के गुणांक के रूप में मानता है। यदि <math>x_i \in [u]</math>, माना <math>p \ge \max \{ u, m \}</math> एक अभाज्य है और परिभाषित करें- | ||
:<math>h_a(\bar{x}) = h_\mathrm{int} \left( \big(\sum_{i=0}^\ell x_i\cdot a^{\ell-i} \big) \bmod ~p \right)</math>, | :<math>h_a(\bar{x}) = h_\mathrm{int} \left( \big(\sum_{i=0}^\ell x_i\cdot a^{\ell-i} \big) \bmod ~p \right)</math>, जहां <math>a \in [p]</math> समान रूप से यादृच्छिक है और <math>h_\mathrm{int}</math> को यूनिवर्सल समूह मानचित्रण पूर्णांक क्षेत्र <math>[p] \mapsto [m]</math> से यादृच्छिक रूप से चुना गया है। | ||
मॉड्यूलर अंकगणित के गुणों का उपयोग करके, बड़े स्ट्रिंग के लिए बड़ी | मॉड्यूलर अंकगणित के गुणों का उपयोग करके, बड़े स्ट्रिंग के लिए बड़ी संख्याएँ उत्पन्न किए बिना उपरोक्त की गणना निम्नानुसार की जा सकती है-<ref>{{cite web | url = http://www.cs.huji.ac.il/course/2002/dast/slides/tirgul9.pdf | title = Hebrew University Course Slides}}</ref> | ||
<syntaxhighlight lang="C"> | <syntaxhighlight lang="C"> | ||
Line 285: | Line 277: | ||
return h | return h | ||
</syntaxhighlight> | </syntaxhighlight> | ||
यह | यह राबिन-कार्प रोलिंग हैश एक रैखिक सर्वांगसम जनरेटर पर आधारित है।<ref> | ||
Robert Uzgalis. | Robert Uzgalis. | ||
[http://www.serve.net/buz/hash.adt/java.002.html "Library Hash Functions"]. | [http://www.serve.net/buz/hash.adt/java.002.html "Library Hash Functions"]. | ||
1996. | 1996. | ||
</ref> | </ref> उपरोक्त एल्गोरिदम को ''गुणक हैश फ़ंक्शन'' के रूप में भी जाना जाता है।<ref>{{cite web|last1=Kankowsk|first1=Peter|title=Hash functions: An empirical comparison|url=http://www.strchr.com/hash_functions}}</ref> अभ्ययास में, पूर्णांक को अतिप्रवाह की अनुमति देकर ''मॉड'' ऑपरेटर और पैरामीटर ''p'' से पूरी तरह बचा जा सकता है क्योंकि यह कई प्रोग्रामिंग भाषाओं में ''mod'' (''Max-Int-Value'' + 1) के बराबर है। नीचे दी गई तालिका कुछ लोकप्रिय कार्यान्वयनों के लिए ''h'' और a को प्रारंभ करने के लिए चुने गए मान दिखाती है। | ||
उपरोक्त एल्गोरिदम को | |||
{| class="wikitable" | {| class="wikitable" | ||
|- | |- | ||
! | !कार्यान्वयन | ||
! | !प्रारंभिक_मान | ||
!a | !a | ||
|- | |- | ||
|[[Daniel J. Bernstein| | |[[Daniel J. Bernstein|बर्नस्टीन]] का हैश फ़ंक्शन ''djb2''<ref>{{cite web|url = http://www.cse.yorku.ca/~oz/hash.html|title = String hash functions|last = Yigit|first = Ozan}}</ref> | ||
|5381 | |5381 | ||
|33 | |33 | ||
|- | |- | ||
|STLPort 4.6.2 | |एसटीएलपोर्ट 4.6.2 (STLPort 4.6.2) | ||
|0 | |0 | ||
|5 | |5 | ||
|- | |- | ||
|[[Brian Kernighan| | |[[Brian Kernighan|कर्निघन]] और [[Dennis Ritchie|रिची]] का हैश फ़ंक्शन<ref>{{Cite book|title = The C Programming Language|last = Kernighan; Ritchie|year = 1988|isbn = 0-13-110362-8|pages = [https://archive.org/details/cprogramminglang00bria/page/118 118]|chapter = 6|edition = 2nd|chapter-url-access = registration|chapter-url = https://archive.org/details/cprogramminglang00bria/page/118}}</ref> | ||
|0 | |0 | ||
|31 | |31 | ||
|- | |- | ||
|<code> | |<code>जावा.लैंग.स्ट्रिंग.हैशकोड()</code><ref>{{cite web|title = String (Java Platform SE 6)|url = http://docs.oracle.com/javase/6/docs/api/java/lang/String.html#hashCode()|website = docs.oracle.com|access-date = 2015-06-10}}</ref> | ||
|0 | |0 | ||
|31 | |31 | ||
|} | |} | ||
दो | दो स्ट्रिंगों <math>\bar{x}, \bar{y}</math> पर विचार करें और मान लें कि <math>\ell</math> लंबी स्ट्रिंग की लंबाई है विश्लेषण के लिए, छोटी स्ट्रिंग को वैचारिक रूप से लंबाई <math>\ell</math> तक शून्य के साथ स्थूल है। <math>h_\mathrm{int}</math> लगाने से पहले संघटन का तात्पर्य है कि <math>a</math> गुणांक <math>\bar{x} - \bar{y}</math> वाले बहुपद का रूट है। इस बहुपद में अधिकतम <math>\ell</math> रूट सापेक्ष <math>p</math> हैं, इसलिए संघटन की संभावना अधिकतम <math>\ell/p</math> है। यादृच्छिक <math>h_\mathrm{int}</math> के माध्यम से संघटन की संभावना कुल संघटन की संभावना को <math>\frac{1}{m} + \frac{\ell}{p}</math> पर लाती है। इस प्रकार, यदि अभाज्य <math>p</math> स्ट्रिंग हैशेड की लंबाई की तुलना में पर्याप्त रूप से बड़ा है, तो समूह यूनिवर्सल (सांख्यिकीय दूरी में) के बहुत समीप है। | ||
अज्ञात-लंबाई स्ट्रिंग को निश्चित-लंबाई वाले हैश मानों में हैश करने के लिए उपयोग किए जाने वाले हैश फ़ंक्शंस के अन्य | अज्ञात-लंबाई स्ट्रिंग को निश्चित-लंबाई वाले हैश मानों में हैश करने के लिए उपयोग किए जाने वाले हैश फ़ंक्शंस के अन्य यूनिवर्सल समूहों में [[राबिन फ़िंगरप्रिंट]] और [[बुजस|बुज़ैश]] सम्मिलित हैं। | ||
==== | ==== मापांक अंकगणित से बचना ==== | ||
मापांक अंकगणित के कम्प्यूटेशनल दंड को कम करने के लिए, अभ्यास में तीन युक्तियों का उपयोग किया जाता है-<ref name=thorup09 /> | |||
# कोई | # कोई दो की घात के समीप होने के लिए अभाज्य <math>p</math> चुनता है, जैसे कि [[मेर्सन प्रीमियम|मेर्सन अभाज्य]]। यह अंकगणित सापेक्ष <math>p</math> को विभाजन के बिना (जोड़ और बदलाव जैसे तीव्र ऑपरेशन का उपयोग करके) लागू करने की अनुमति देता है। उदाहरण के लिए, आधुनिक आर्किटेक्चर पर कोई व्यक्ति <math>p = 2^{61}-1</math> के साथ काम कर सकता है, जबकि <math>x_i</math> 32-बिट मान हैं। | ||
# कोई | #कोई ब्लॉकों पर वेक्टर हैशिंग लागू कर सकता है। उदाहरण के लिए, कोई स्ट्रिंग के प्रत्येक 16-शब्द ब्लॉक पर वेक्टर हैशिंग लागू करता है, और <math>\lceil k/16 \rceil</math> परिणामों पर स्ट्रिंग हैशिंग लागू करता है। चूंकि धीमी स्ट्रिंग हैशिंग को काफी छोटे वेक्टर पर लागू किया जाता है, यह अनिवार्य रूप से वेक्टर हैशिंग जितना तीव्र होगा। | ||
# कोई विभाजक के रूप में दो की घात को चुनता है, जिससे अंकगणित सापेक्ष <math>2^w</math> को बिना विभाजन ([[बिट मास्किंग]] के तीव्र ऑपरेशन का उपयोग करके) के लागू किया जा सकता है। एनएच (NH) हैश-फ़ंक्शन समूह यह दृष्टिकोण अपनाता है। | |||
==यह भी देखें== | ==यह भी देखें== | ||
* [[के-स्वतंत्र हैशिंग]] | * [[के-स्वतंत्र हैशिंग|के (K)-स्वतंत्र हैशिंग]] | ||
* [[रोलिंग हैशिंग]] | * [[रोलिंग हैशिंग]] | ||
* सारणीकरण हैशिंग | * सारणीकरण हैशिंग | ||
*[[न्यूनतम-वार स्वतंत्रता]] | *[[न्यूनतम-वार स्वतंत्रता]] | ||
* [[यूनिवर्सल वन-वे हैश फ़ंक्शन]] | * [[यूनिवर्सल वन-वे हैश फ़ंक्शन|यूनिवर्सल एकतरफ़ा हैश फ़ंक्शन]] | ||
* कम | * कम विसंगति अनुक्रम | ||
* | * उचित हैशिंग | ||
== संदर्भ == | == संदर्भ == | ||
<references /> | <references /> | ||
== अग्रिम पठन == | == अग्रिम पठन == | ||
* {{cite book | * {{cite book | ||
Line 348: | Line 338: | ||
| isbn = 0-201-89685-0 | | isbn = 0-201-89685-0 | ||
}} | }} | ||
==बाहरी संबंध== | ==बाहरी संबंध== | ||
* [http://opendatastructures.org/versions/edition-0.1e/ods-java/5_1_ChainedHashTable_Hashin.html#SECTION00811000000000000000 Open Data Structures - Section 5.1.1 - Multiplicative Hashing], [[Pat Morin]] | * [http://opendatastructures.org/versions/edition-0.1e/ods-java/5_1_ChainedHashTable_Hashin.html#SECTION00811000000000000000 Open Data Structures - Section 5.1.1 - Multiplicative Hashing], [[Pat Morin]] | ||
[[Category: | [[Category:Articles with hatnote templates targeting a nonexistent page]] | ||
[[Category:CS1 maint]] | |||
[[Category:Created On 10/07/2023]] | [[Category:Created On 10/07/2023]] | ||
[[Category:Lua-based templates]] | |||
[[Category:Machine Translated Page]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates that add a tracking category]] | |||
[[Category:Templates that generate short descriptions]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:एल्गोरिदम खोजें]] | |||
[[Category:कम्प्यूटेशनल जटिलता सिद्धांत]] | |||
[[Category:क्रिप्टोग्राफ़िक हैश फ़ंक्शंस]] | |||
[[Category:हैशिंग]] |
Latest revision as of 06:58, 1 August 2023
गणित और कंप्यूटिंग में, यूनिवर्सल हैशिंग (यादृच्छिक एल्गोरिथ्म या डेटा संरचना में) निश्चित गणितीय गुण के साथ हैश फ़ंक्शन के समूह से यादृच्छिक रूप से हैश फ़ंक्शन का चयन करने को संदर्भित करता है (नीचे परिभाषा देखें)। यह प्रत्याशित रूप से कम संख्या में संघटन की गारंटी देता है, भले ही डेटा किसी प्रतिद्वंद्वी द्वारा चुना गया हो। कई यूनिवर्सल समूह (हैशिंग पूर्णांक, वैक्टर, स्ट्रिंग्स के लिए) ज्ञात हैं, और उनका मूल्यांकन प्रायः बहुत कुशल होता है। कंप्यूटर विज्ञान में यूनिवर्सल हैशिंग के कई उपयोग हैं, उदाहरण के लिए हैश टेबल, यादृच्छिक एल्गोरिदम और क्रिप्टोग्राफी के कार्यान्वयन में।
परिचय
माना कि हम कुछ यूनिवर्स से कीज़ को बिन्स (लेबल ) में मैप करना चाहते हैं। एल्गोरिदम को कीज़ के कुछ डेटा सेट को संभालना होगा, जो पहले से ज्ञात नहीं है। प्रायः, हैशिंग का लक्ष्य कम संख्या में संघटनों ( से कीज़ जो एक ही बिन में आती है) को प्राप्त करना है। नियतात्मक हैश फ़ंक्शन प्रतिकूल सेटिंग में कोई गारंटी नहीं दे सकता है यदि , क्योंकि प्रतिद्वंद्वी को बिन की पूर्वचित्र के रूप में चुन सकता है। इसका अर्थ यह है कि सभी डेटा कीज़ एक ही बिन में आ जाती हैं, जिससे हैशिंग अनुपयोगी हो जाती है। इसके अलावा, नियतात्मक हैश फ़ंक्शन रीहैशिंग की अनुमति नहीं देता है- कभी-कभी इनपुट डेटा हैश फ़ंक्शन (उदाहरण के लिए बहुत अधिक संघटन होते हैं) के लिए व्यर्थ हो जाता है, इसलिए कोई हैश फ़ंक्शन को बदलना चाहेगा।
इन समस्याओं का समाधान हैश फ़ंक्शंस के समूह से किसी फ़ंक्शन को यादृच्छिक रूप से चुनना है। फ़ंक्शंस के समूह को यूनिवर्सल समूह कहा जाता है यदि, ।
दूसरे शब्दों में, जब हैश फ़ंक्शन को से यादृच्छिक रूप से समान रूप से खींचा जाता है, तो यूनिवर्स की कोई भी दो अलग-अलग कीज़ अधिकतम की संभावना के साथ टकराती हैं। यदि हैश फ़ंक्शन प्रत्येक कीज़ को वास्तव में यादृच्छिक हैश कोड निर्दिष्ट करता है तो हम टकराव की बिल्कुल यही संभावना की अपेक्षा करेंगे।
कभी-कभी, परिभाषा को स्थिर कारक द्वारा शिथिल कर दिया जाता है, जिसके लिए केवल संघटन की संभावना की आवश्यकता होती है न कि की। यह अवधारणा 1977 में कार्टर और वेगमैन[1] द्वारा प्रस्तुत की गई थी, और कंप्यूटर विज्ञान में इसके कई अनुप्रयोग पाए गए हैं (उदाहरण के लिए देखें[2])।
यदि संघटन की संभावना पर हमारी ऊपरी सीमा है, तो हम कहते हैं कि हमारे पास -लगभग सार्वभौमिकता है। इसलिए उदाहरण के लिए, यूनिवर्सल समूह में -लगभग सार्वभौमिकता होती है।
कई, लेकिन सभी नहीं, यूनिवर्सल समूह में निम्नलिखित दृढ़ एकसमान असमानता गुण होते हैं-
, जब को समूह से यादृच्छिक रूप से निकाला जाता है, तो अंतर समान रूप से में वितरित होता है।
ध्यान दें कि सार्वभौमिकता की परिभाषा केवल इस बात से संबंधित है कि क्या , जो संघटनों की गणना करता है। एकसमान असमानता गुण अधिक दृढ़ होता है।
(इसी प्रकार, यूनिवर्सल समूह एक्सओआर (XOR) यूनिवर्सल हो सकता है यदि , मान को में समान रूप से वितरित किया जाता है जहां बिटवाइज़ विशिष्ट या ऑपरेशन है। यह केवल तभी संभव है जब दो की घात हो।)
एक और भी दृढ़ स्थिति युग्मानूसार स्वतंत्रता है- हमारे पास यह गुण है जब हमारे पास संभावना है कि हैश मानों के किसी भी युग्म के लिए हैश होगा जैसे कि वे पूरी तरह से यादृच्छिक थे- । युग्मानूसार स्वतंत्रता को कभी-कभी दृढ़ सार्वभौमिकता कहा जाता है।
एक अन्य गुण एकरूपता है. हम कहते हैं कि समूह एक समान है यदि सभी हैश मान समान रूप से संभावित हैं- किसी भी हैश मान के लिए। सार्वभौमिकता का तात्पर्य एकरूपता नहीं है। हालाँकि, दृढ़ सार्वभौमिकता का तात्पर्य एकरूपता से है।
समान दूरी के गुण वाले समूह को देखते हुए, कोई हैश फ़ंक्शन में मानों के साथ एक समान रूप से वितरित यादृच्छिक स्थिरांक जोड़कर युग्मानूसार स्वतंत्र या दृढ़ता से यूनिवर्सल हैश समूह का उत्पादन कर सकता है। (इसी प्रकार, यदि दो की घात है, तो हम एक्सओआर यूनिवर्सल हैश समूह से एक विशेष या समान रूप से वितरित यादृच्छिक स्थिरांक के साथ युग्मानूसार स्वतंत्रता प्राप्त कर सकते हैं।) चूंकि स्थिरांक द्वारा बदलाव कभी-कभी अनुप्रयोगों में अप्रासंगिक होता है (जैसे हैश टेबल), समान दूरी के गुण और युग्मानूसार स्वतंत्र के बीच सावधानीपूर्वक अंतर कभी-कभी नहीं किया जाता है।[3]
कुछ अनुप्रयोगों (जैसे हैश टेबल) के लिए, हैश मानों के कम से कम महत्वपूर्ण बिट्स का भी यूनिवर्सल होना महत्वपूर्ण है। जब कोई समूह दृढ़ता से यूनिवर्सल होता है, तो इसकी गारंटी होती है- यदि , के साथ दृढ़ता से यूनिवर्सल समूह है, तो सभी के लिए फ़ंक्शन से बना समूह भी के लिए दृढ़ता से यूनिवर्सल है। दुर्भाग्य से, यह बात (केवल) यूनिवर्सल समूहों के लिए सत्य नहीं है। उदाहरण के लिए, सर्वसमिका फ़ंक्शन से बना समूह स्पष्ट रूप से यूनिवर्सल है, लेकिन फ़ंक्शन से बना समूह यूनिवर्सल होने में विफल रहता है।
यूएमएसी (UMAC) और पॉली1305-एईएस (Poly1305-AES) और कई अन्य संदेश प्रमाणीकरण कोड एल्गोरिदम यूनिवर्सल हैशिंग पर आधारित हैं।[4][5] ऐसे अनुप्रयोगों में, सॉफ़्टवेयर प्रत्येक संदेश के लिए विशिष्ट अस्थायी रूप के आधार पर, प्रत्येक संदेश के लिए एक नया हैश फ़ंक्शन चुनता है।
कई हैश टेबल कार्यान्वयन यूनिवर्सल हैशिंग पर आधारित हैं। ऐसे अनुप्रयोगों में, प्रायः सॉफ़्टवेयर नया हैश फ़ंक्शन तभी चुनता है जब उसे पता चलता है कि "बहुत अधिक" कीज़ टकरा गई हैं तब तक, एक ही हैश फ़ंक्शन का बार-बार उपयोग किया जाता रहेगा। (कुछ संघटन समाधान योजनाएं, जैसे कि गतिशील पूर्ण हैशिंग, प्रत्येक बार संघटन होने पर नया हैश फ़ंक्शन चुनती हैं। अन्य संघटन समाधान योजनाएं, जैसे कुक्कू हैशिंग और 2-विकल्प हैशिंग, नया हैश फ़ंक्शन चुनने से पहले कई संघटनों की अनुमति देती हैं)। पूर्णांकों, वेक्टरों और स्ट्रिंग्स के लिए सबसे तीव्र ज्ञात यूनिवर्सल और दृढ़ता से यूनिवर्सल हैश फ़ंक्शन का सर्वेक्षण पाया गया है।[6]
गणितीय गारंटी
कीज़ के किसी भी निश्चित समुच्चय के लिए, यूनिवर्सल समूह का उपयोग निम्नलिखित गुणों की गारंटी देता है।
- में किसी निश्चित के लिए, बिन में कीज़ की अपेक्षित संख्या है। श्रृंखलन द्वारा हैश तालिकाओं को कार्यान्वित करते समय, यह संख्या की (उदाहरण के लिए परिप्रश्न, सम्मिलन या विलोपन) से जुड़े ऑपरेशन के अपेक्षित कार्यावधि के समानुपाती होती है।
- में के साथ कीज़ के युग्म की अपेक्षित संख्या जो () से टकराती है, ऊपर से परिबद्ध है, जो क्रम की है। जब बिन्स की संख्या, को में रैखिक चुना जाता है (अर्थात, में फ़ंक्शन द्वारा निर्धारित किया जाता है, तो संघटन की अपेक्षित संख्या होती है। जब बिन्स में हैशिंग की जाती है, तो कम से कम आधी संभावना के साथ कोई संघटन नहीं होता है।
- कम से कम कीज़ वाली बिन्स में कीज़ की अपेक्षित संख्या ऊपर से परिबद्ध है।[7] इस प्रकार, यदि प्रत्येक बिन की क्षमता को औसत आकार () से तीन गुना तक सीमित किया जाता है, तो अतिप्रवाहित बिन्स में कीज़ की कुल संख्या अधिकतम होती है। यह केवल उस हैश समूह के साथ लागू होता है जिसकी संघटन की संभावना से ऊपर होती है। यदि कमजोर परिभाषा का उपयोग किया जाता है, इसे द्वारा सीमित किया जाता है, तो यह परिणाम अब सत्य नहीं है।[7]
जैसा कि उपरोक्त गारंटी किसी भी निश्चित समुच्चय के लिए होती है, वे तब भी मान्य होती हैं जब डेटा समुच्चय किसी प्रतिद्वंद्वी द्वारा चुना जाता है। हालाँकि, प्रतिद्वंद्वी को एल्गोरिदम के हैश फ़ंक्शन के यादृच्छिक चयन से पहले (या उससे स्वतंत्र) यह विकल्प चुनना होगा। यदि प्रतिद्वंद्वी एल्गोरिथ्म की यादृच्छिक चयन का निरीक्षण कर सकता है, तो यादृच्छिकता का कोई उद्देश्य नहीं है, और स्थिति नियतात्मक हैशिंग के समान है।
दूसरी और तीसरी गारंटी का उपयोग प्रायः रीहैशिंग के संयोजन में किया जाता है। उदाहरण के लिए, कुछ संख्या में संघटनों को संभालने के लिए यादृच्छिक एल्गोरिदम तैयार किया जा सकता है। यदि यह बहुत अधिक संघटन देखता है, तो यह समूह से एक और यादृच्छिक चुनता है और दोहराता है। सार्वभौमिकता यह गारंटी देती है कि पुनरावृत्ति की संख्या ज्यामितीय यादृच्छिक चर है।
निर्माण
चूंकि किसी भी कंप्यूटर डेटा को एक या अधिक मशीनी शब्दों के रूप में दर्शाया जा सकता है, इसलिए प्रायः तीन प्रकार के डोमेन के लिए हैश फ़ंक्शन की आवश्यकता होती है- मशीनी शब्द ("पूर्णांक"), मशीनी शब्दों के निश्चित-लंबाई वाले वेक्टर, और चर-लंबाई वाले वेक्टर ("स्ट्रिंग्स")।
हैशिंग पूर्णांक
यह खंड हैशिंग पूर्णांकों की स्थिति को संदर्भित करता है जो मशीन शब्दों में फिट होते हैं इस प्रकार, गुणा, जोड़, भाग आदि जैसे ऑपरेशन सस्ते मशीन-स्तरीय निर्देश हैं। माना यूनिवर्स को हैश किया जाना है।
कार्टर और वेगमैन[1] का मूल प्रस्ताव अभाज्य चुनना और परिभाषित करना था
जहां को के साथ यादृच्छिक रूप से चुने गए पूर्णांक सापेक्ष हैं। (यह रैखिक सर्वांगसम जनरेटर की एकल पुनरावृत्ति है।)
यह देखने के लिए कि यूनिवर्सल समूह है, ध्यान दें कि केवल तभी मान्य होता है जब
कुछ पूर्णांक के लिए और के बीच। चूँकि , यदि उनका अंतर शून्येतर है और इसका व्युत्क्रम सापेक्ष है। के लिए हल करने पर परिणाम प्राप्त होता है
- .
के लिए संभावित विकल्प हैं (चूंकि को बाहर रखा गया है) और, को अनुमत सीमा में भिन्न करते हुए, दाईं ओर के लिए संभावित गैर-शून्य मान हैं। इस प्रकार संघटन की संभावना है
- .
यह देखने का एक और तरीका है कि यूनिवर्सल समूह है, सांख्यिकीय दूरी की धारणा के माध्यम से। अंतर के रूप में लिखें
- .
चूँकि गैर-शून्य है और को में समान रूप से वितरित किया जाता है, इसलिए यह इस प्रकार है कि सापेक्ष को में भी समान रूप से वितरित किया जाता है। इस प्रकार का वितरण नमूनों के बीच की संभावना के अंतर तक लगभग एक समान है। परिणामस्वरूप, एक समान समूह के लिए सांख्यिकीय दूरी है, जो होने पर नगण्य हो जाती है।
सरल हैश फ़ंक्शंस का समूह
केवल लगभग यूनिवर्सल है- सभी के लिए ।[1] इसके अतिरिक्त, यह विश्लेषण लगभग दृढ़ है कार्टर और वेगमैन[1] दिखाते हैं कि जब भी ।
मापांक अंकगणित से बचना
हैशिंग पूर्णांकों के लिए कला की स्थिति 1997 में डाइट्ज़फेलबिंगर एट अल. द्वारा वर्णित गुणन-परिवर्तन योजना है।[8] मापांक अंकगणित से बचने के कारण, इस विधि को लागू करना बहुत आसान है और अभ्यास (प्रायः कम से कम चार के कारक से[9]) में भी काफी तीव्रता से चलता है। योजना मानती है कि बिन्स की संख्या दो, की क्षमता है। माना मशीनी शब्द में बिट्स की संख्या है। फिर हैश फ़ंक्शंस को विषम धनात्मक पूर्णांक (जो बिट्स के शब्द में फिट होते हैं) पर पैरामीटराइज़ किया जाता है। का मूल्यांकन करने के लिए, को सापेक्ष से गुणा करें और फिर उच्च क्रम बिट्स को हैश कोड के रूप में रखें। गणितीय संकेतन में, यह है
यह योजना समान अंतर गुण को संतुष्ट नहीं करती है और केवल -लगभग-यूनिवर्सल है किसी भी , के लिए।
हैश फ़ंक्शन के व्यवहार को समझने के लिए, ध्यान दें कि, यदि और में समान उच्चतम-क्रम वाले 'M' बिट्स हैं, तो के उच्चतम क्रम M बिट्स के रूप में या तो सभी 1 या सभी 0 हैं (यह इस पर निर्भर करता है कि या बड़ा है या नहीं)। मान लें कि का सबसे कम महत्वपूर्ण सेट बिट स्थिति पर दिखाई देता है। चूँकि एक यादृच्छिक विषम पूर्णांक है और विषम पूर्णांकों का व्युत्क्रम वलय में होता है, इसलिए यह इस प्रकार है कि को -बिट पूर्णांकों के बीच समान रूप से वितरित किया जाएगा, जिसमें स्थिति पर सबसे कम महत्वपूर्ण सेट बिट होगा। इसलिए संभावना यह है कि ये बिट्स सभी 0 या सभी 1 हैं, इसलिए अधिकतम है। दूसरी ओर, यदि , तो के उच्च-क्रम M बिट्स में 0 और 1 दोनों सम्मिलित हैं, इसलिए यह निश्चित है कि । अंत में, यदि है तो का बिट 1 है और यदि और केवल यदि बिट्स भी 1 है, जो संभावना के साथ होता है।
यह विश्लेषण दृढ़ है, जैसा कि उदाहरण और के साथ दिखाया जा सकता है। वास्तव में 'यूनिवर्सल' हैश फ़ंक्शन प्राप्त करने के लिए, कोई व्यक्ति गुणा-जोड़-स्थानांतरण योजना का उपयोग कर सकता है जो उच्च-क्रम बिट्स चुनता है
जहां , के साथ यादृच्छिक धनात्मक पूर्णांक है और , के साथ यादृच्छिक गैर-ऋणात्मक पूर्णांक है। इसके लिए -बिट अहस्ताक्षरित पूर्णांकों पर अंकगणित करने की आवश्यकता है। गुणा-स्थानांतरण का यह संस्करण डिट्ज़फेलबिंगर के कारण है, और बाद में वोल्फ़ेल द्वारा इसका अधिक सटीक विश्लेषण किया गया।[10]
हैशिंग वेक्टर
यह अनुभाग मशीनी शब्दों के एक निश्चित-लंबाई वाले वेक्टर को हैश करने से संबंधित है। इनपुट को मशीन शब्दों (प्रत्येक बिट के पूर्णांक) के वेक्टर के रूप में व्याख्या करें। यदि एक समान अंतर गुण वाला यूनिवर्सल समूह है, तो निम्नलिखित समूह (कार्टर और वेगमैन के समय का[1]) में भी एक समान अंतर गुण है (और इसलिए यूनिवर्सल है)-
- , जहां प्रत्येक को यादृच्छिक रूप से स्वतंत्र रूप से चुना जाता है।
यदि दो की घात है, तो योग को अपवर्जित या से प्रतिस्थापित किया जा सकता है।[11]
अभ्यास में, यदि द्विक-परिशुद्धता अंकगणित उपलब्ध है, तो इसे हैश फ़ंक्शंस के गुणा-स्थानांतरण हैश समूह के साथ त्वरित किया जाता है। प्रत्येक बिट्स पर यादृच्छिक विषम पूर्णांकों के वेक्टर के साथ हैश फ़ंक्शन प्रारंभ करें। फिर यदि के लिए डिब्बे की संख्या है-
- .
गुणन की संख्या को आधा करना संभव है, जो अभ्यास में मोटे तौर पर दो गुना गति में बदल जाता है।[11] प्रत्येक बिट्स पर यादृच्छिक विषम पूर्णांकों के वेक्टर के साथ हैश फ़ंक्शन को आरंभ करें। निम्नलिखित हैश समूह यूनिवर्सल है-[12]
- .
यदि द्विक परिशुद्धता ऑपरेशन उपलब्ध नहीं हैं, तो कोई इनपुट को आधे-शब्दों (-बिट पूर्णांक) के वेक्टर के रूप में व्याख्या कर सकता है। इसके बाद एल्गोरिदम गुणन का उपयोग करेगा, जहां वेक्टर में आधे शब्दों की संख्या थी। इस प्रकार, एल्गोरिदम इनपुट के प्रति शब्द गुणन की "दर" पर चलता है।
उसी योजना का उपयोग पूर्णांकों के बिट्स को बाइट्स के वेक्टर के रूप में व्याख्या करके, हैशिंग पूर्णांकों के लिए भी किया जा सकता है। इस प्रकार में, वेक्टर तकनीक को सारणीकरण हैशिंग के रूप में जाना जाता है और यह गुणन-आधारित यूनिवर्सल हैशिंग योजनाओं के लिए व्यावहारिक विकल्प प्रदान करता है।[13]
उच्च गति पर सुदृढ़ सार्वभौमिकता भी संभव है।[14] बिट्स पर यादृच्छिक पूर्णांकों के वेक्टर के साथ हैश फ़ंक्शन प्रारंभ करें। गणना करें
- .
परिणाम बिट्स पर दृढ़ता से यूनिवर्सल है। प्रायोगिक तौर पर, यह हाल के इंटेल प्रोसेसर पर के लिए 0.2 सीपीयू (CPU) चक्र प्रति बाइट पर रन हुआ पाया गया।
हैशिंग स्ट्रिंग
इसका तात्पर्य मशीनी शब्दों के चर-आकार वाले वेक्टर को हैश करने से है। यदि स्ट्रिंग की लंबाई को छोटी संख्या से सीमित किया जा सकता है, तो ऊपर से (वैचारिक रूप से वेक्टर को ऊपरी सीमा तक शून्य के साथ विस्तारण) वेक्टर हल का उपयोग करना सबसे अच्छा है। आवश्यक स्थान स्ट्रिंग की अधिकतम लंबाई है, लेकिन का मूल्यांकन करने का समय केवल की लंबाई है। जब तक स्ट्रिंग में शून्य वर्जित हैं, सार्वभौमिकता को प्रभावित किए बिना हैश फ़ंक्शन का मूल्यांकन करते समय शून्य-विस्तारण को अनदेखा किया जा सकता है।[11] ध्यान दें कि यदि स्ट्रिंग में शून्य की अनुमति है, तो विस्तारण से पहले सभी स्ट्रिंग्स में एक काल्पनिक गैर-शून्य (उदाहरण के लिए, 1) वर्ण जोड़ना सबसे अच्छा हो सकता है- इससे यह सुनिश्चित होगा कि सार्वभौमिकता प्रभावित नहीं होती है।[14]
अब मान लें कि हम , को हैश करना चाहते हैं, जहां पर एक अच्छी सीमा प्राथमिकता से ज्ञात नहीं है। व्यवहार द्वारा प्रस्तावित यूनिवर्सल समूह[15] स्ट्रिंग को बहुपद सापेक्ष बड़े अभाज्य के गुणांक के रूप में मानता है। यदि , माना एक अभाज्य है और परिभाषित करें-
- , जहां समान रूप से यादृच्छिक है और को यूनिवर्सल समूह मानचित्रण पूर्णांक क्षेत्र से यादृच्छिक रूप से चुना गया है।
मॉड्यूलर अंकगणित के गुणों का उपयोग करके, बड़े स्ट्रिंग के लिए बड़ी संख्याएँ उत्पन्न किए बिना उपरोक्त की गणना निम्नानुसार की जा सकती है-[16]
uint hash(String x, int a, int p)
uint h = INITIAL_VALUE
for (uint i=0 ; i < x.length ; ++i)
h = ((h*a) + x[i]) mod p
return h
यह राबिन-कार्प रोलिंग हैश एक रैखिक सर्वांगसम जनरेटर पर आधारित है।[17] उपरोक्त एल्गोरिदम को गुणक हैश फ़ंक्शन के रूप में भी जाना जाता है।[18] अभ्ययास में, पूर्णांक को अतिप्रवाह की अनुमति देकर मॉड ऑपरेटर और पैरामीटर p से पूरी तरह बचा जा सकता है क्योंकि यह कई प्रोग्रामिंग भाषाओं में mod (Max-Int-Value + 1) के बराबर है। नीचे दी गई तालिका कुछ लोकप्रिय कार्यान्वयनों के लिए h और a को प्रारंभ करने के लिए चुने गए मान दिखाती है।
कार्यान्वयन | प्रारंभिक_मान | a |
---|---|---|
बर्नस्टीन का हैश फ़ंक्शन djb2[19] | 5381 | 33 |
एसटीएलपोर्ट 4.6.2 (STLPort 4.6.2) | 0 | 5 |
कर्निघन और रिची का हैश फ़ंक्शन[20] | 0 | 31 |
जावा.लैंग.स्ट्रिंग.हैशकोड() [21]
|
0 | 31 |
दो स्ट्रिंगों पर विचार करें और मान लें कि लंबी स्ट्रिंग की लंबाई है विश्लेषण के लिए, छोटी स्ट्रिंग को वैचारिक रूप से लंबाई तक शून्य के साथ स्थूल है। लगाने से पहले संघटन का तात्पर्य है कि गुणांक वाले बहुपद का रूट है। इस बहुपद में अधिकतम रूट सापेक्ष हैं, इसलिए संघटन की संभावना अधिकतम है। यादृच्छिक के माध्यम से संघटन की संभावना कुल संघटन की संभावना को पर लाती है। इस प्रकार, यदि अभाज्य स्ट्रिंग हैशेड की लंबाई की तुलना में पर्याप्त रूप से बड़ा है, तो समूह यूनिवर्सल (सांख्यिकीय दूरी में) के बहुत समीप है।
अज्ञात-लंबाई स्ट्रिंग को निश्चित-लंबाई वाले हैश मानों में हैश करने के लिए उपयोग किए जाने वाले हैश फ़ंक्शंस के अन्य यूनिवर्सल समूहों में राबिन फ़िंगरप्रिंट और बुज़ैश सम्मिलित हैं।
मापांक अंकगणित से बचना
मापांक अंकगणित के कम्प्यूटेशनल दंड को कम करने के लिए, अभ्यास में तीन युक्तियों का उपयोग किया जाता है-[11]
- कोई दो की घात के समीप होने के लिए अभाज्य चुनता है, जैसे कि मेर्सन अभाज्य। यह अंकगणित सापेक्ष को विभाजन के बिना (जोड़ और बदलाव जैसे तीव्र ऑपरेशन का उपयोग करके) लागू करने की अनुमति देता है। उदाहरण के लिए, आधुनिक आर्किटेक्चर पर कोई व्यक्ति के साथ काम कर सकता है, जबकि 32-बिट मान हैं।
- कोई ब्लॉकों पर वेक्टर हैशिंग लागू कर सकता है। उदाहरण के लिए, कोई स्ट्रिंग के प्रत्येक 16-शब्द ब्लॉक पर वेक्टर हैशिंग लागू करता है, और परिणामों पर स्ट्रिंग हैशिंग लागू करता है। चूंकि धीमी स्ट्रिंग हैशिंग को काफी छोटे वेक्टर पर लागू किया जाता है, यह अनिवार्य रूप से वेक्टर हैशिंग जितना तीव्र होगा।
- कोई विभाजक के रूप में दो की घात को चुनता है, जिससे अंकगणित सापेक्ष को बिना विभाजन (बिट मास्किंग के तीव्र ऑपरेशन का उपयोग करके) के लागू किया जा सकता है। एनएच (NH) हैश-फ़ंक्शन समूह यह दृष्टिकोण अपनाता है।
यह भी देखें
- के (K)-स्वतंत्र हैशिंग
- रोलिंग हैशिंग
- सारणीकरण हैशिंग
- न्यूनतम-वार स्वतंत्रता
- यूनिवर्सल एकतरफ़ा हैश फ़ंक्शन
- कम विसंगति अनुक्रम
- उचित हैशिंग
संदर्भ
- ↑ 1.0 1.1 1.2 1.3 1.4 Carter, Larry; Wegman, Mark N. (1979). "Universal Classes of Hash Functions". Journal of Computer and System Sciences. 18 (2): 143–154. doi:10.1016/0022-0000(79)90044-8. Conference version in STOC'77.
- ↑ Miltersen, Peter Bro. "Universal Hashing" (PDF). Archived from the original (PDF) on 24 May 2011. Retrieved 24 June 2009.
- ↑ Motwani, Rajeev; Raghavan, Prabhakar (1995). Randomized Algorithms. Cambridge University Press. p. 221. ISBN 0-521-47465-5.
- ↑ David Wagner, ed. "Advances in Cryptology - CRYPTO 2008". p. 145.
- ↑ Jean-Philippe Aumasson, Willi Meier, Raphael Phan, Luca Henzen. "The Hash Function BLAKE". 2014. p. 10.
- ↑ Thorup, Mikkel (2015). "High Speed Hashing for Integers and Strings". arXiv:1504.06804 [cs.DS].
- ↑ 7.0 7.1 Baran, Ilya; Demaine, Erik D.; Pătraşcu, Mihai (2008). "Subquadratic Algorithms for 3SUM" (PDF). Algorithmica. 50 (4): 584–596. doi:10.1007/s00453-007-9036-3. S2CID 9855995.
- ↑ Dietzfelbinger, Martin; Hagerup, Torben; Katajainen, Jyrki; Penttonen, Martti (1997). "A Reliable Randomized Algorithm for the Closest-Pair Problem" (Postscript). Journal of Algorithms. 25 (1): 19–51. doi:10.1006/jagm.1997.0873. Retrieved 10 February 2011.
- ↑ Thorup, Mikkel (18 December 2009). "Text-book algorithms at SODA".
- ↑ Woelfel, Philipp (1999). Efficient Strongly Universal and Optimally Universal Hashing. Mathematical Foundations of Computer Science 1999. LNCS. Vol. 1672. pp. 262–272. doi:10.1007/3-540-48340-3_24.
- ↑ 11.0 11.1 11.2 11.3 Thorup, Mikkel (2009). String hashing for linear probing. Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 655–664. CiteSeerX 10.1.1.215.4253. doi:10.1137/1.9781611973068.72. ISBN 978-0-89871-680-1., section 5.3
- ↑ Black, J.; Halevi, S.; Krawczyk, H.; Krovetz, T. (1999). UMAC: Fast and Secure Message Authentication (PDF). Advances in Cryptology (CRYPTO '99)., Equation 1
- ↑ Pătraşcu, Mihai; Thorup, Mikkel (2011). The power of simple tabulation hashing. Proceedings of the 43rd annual ACM Symposium on Theory of Computing (STOC '11). pp. 1–10. arXiv:1011.5200. doi:10.1145/1993636.1993638. ISBN 9781450306911.
- ↑ 14.0 14.1 Kaser, Owen; Lemire, Daniel (2013). "Strongly universal string hashing is fast". Computer Journal. Oxford University Press. 57 (11): 1624–1638. arXiv:1202.4961. doi:10.1093/comjnl/bxt070.
- ↑ Dietzfelbinger, Martin; Gil, Joseph; Matias, Yossi; Pippenger, Nicholas (1992). Polynomial Hash Functions Are Reliable (Extended Abstract). Proc. 19th International Colloquium on Automata, Languages and Programming (ICALP). pp. 235–246.
- ↑ "Hebrew University Course Slides" (PDF).
- ↑ Robert Uzgalis. "Library Hash Functions". 1996.
- ↑ Kankowsk, Peter. "Hash functions: An empirical comparison".
- ↑ Yigit, Ozan. "String hash functions".
- ↑ Kernighan; Ritchie (1988). "6". The C Programming Language (2nd ed.). pp. 118. ISBN 0-13-110362-8.
{{cite book}}
: CS1 maint: multiple names: authors list (link) - ↑ "String (Java Platform SE 6)". docs.oracle.com. Retrieved 2015-06-10.
अग्रिम पठन
- Knuth, Donald Ervin (1998). The Art of Computer Programming, Vol. III: Sorting and Searching (3rd ed.). Reading, Mass; London: Addison-Wesley. ISBN 0-201-89685-0.