यूनिवर्सल हैशिंग

गणित और कंप्यूटिंग में, यूनिवर्सल हैशिंग (यादृच्छिक एल्गोरिथ्म या डेटा संरचना में) निश्चित गणितीय गुण के साथ हैश फ़ंक्शन के समूह से यादृच्छिक रूप से हैश फ़ंक्शन का चयन करने को संदर्भित करता है (नीचे परिभाषा देखें)। यह प्रत्याशित रूप से कम संख्या में संघटन की गारंटी देता है, भले ही डेटा किसी प्रतिद्वंद्वी द्वारा चुना गया हो। कई यूनिवर्सल समूह (हैशिंग पूर्णांक, वैक्टर, स्ट्रिंग्स के लिए) ज्ञात हैं, और उनका मूल्यांकन प्रायः बहुत कुशल होता है। कंप्यूटर विज्ञान में यूनिवर्सल हैशिंग के कई उपयोग हैं, उदाहरण के लिए हैश टेबल, यादृच्छिक एल्गोरिदम और क्रिप्टोग्राफी के कार्यान्वयन में।

परिचय

See also: हैश फंकशन

माना कि हम कुछ यूनिवर्स $U$ से कीज़ को $m$ बिन्स (लेबल $[m]=\{0,\dots ,m-1\}$) में मैप करना चाहते हैं। एल्गोरिदम को $|S|=n$ कीज़ के कुछ डेटा सेट $S\subseteq U$ को संभालना होगा, जो पहले से ज्ञात नहीं है। प्रायः, हैशिंग का लक्ष्य कम संख्या में संघटनों ($S$ से कीज़ जो एक ही बिन में आती है) को प्राप्त करना है। नियतात्मक हैश फ़ंक्शन प्रतिकूल सेटिंग में कोई गारंटी नहीं दे सकता है यदि $|U|>m\cdot n$, क्योंकि प्रतिद्वंद्वी $S$ को बिन की पूर्वचित्र के रूप में चुन सकता है। इसका अर्थ यह है कि सभी डेटा कीज़ एक ही बिन में आ जाती हैं, जिससे हैशिंग अनुपयोगी हो जाती है। इसके अलावा, नियतात्मक हैश फ़ंक्शन रीहैशिंग की अनुमति नहीं देता है- कभी-कभी इनपुट डेटा हैश फ़ंक्शन (उदाहरण के लिए बहुत अधिक संघटन होते हैं) के लिए व्यर्थ हो जाता है, इसलिए कोई हैश फ़ंक्शन को बदलना चाहेगा।

इन समस्याओं का समाधान हैश फ़ंक्शंस के समूह से किसी फ़ंक्शन को यादृच्छिक रूप से चुनना है। फ़ंक्शंस के समूह $H=\{h:U\to [m]\}$ को यूनिवर्सल समूह कहा जाता है यदि, $\forall x,y\in U,~x\neq y:~~|\{h\in H:h(x)=h(y)\}|\leq {\frac {|H|}{m}}$।

दूसरे शब्दों में, जब हैश फ़ंक्शन $h$ को $H$ से यादृच्छिक रूप से समान रूप से खींचा जाता है, तो यूनिवर्स की कोई भी दो अलग-अलग कीज़ अधिकतम $1/m$ की संभावना के साथ टकराती हैं। यदि हैश फ़ंक्शन प्रत्येक कीज़ को वास्तव में यादृच्छिक हैश कोड निर्दिष्ट करता है तो हम टकराव की बिल्कुल यही संभावना की अपेक्षा करेंगे।

कभी-कभी, परिभाषा को स्थिर कारक द्वारा शिथिल कर दिया जाता है, जिसके लिए केवल संघटन की संभावना $O(1/m)$ की आवश्यकता होती है न कि $\leq 1/m$ की। यह अवधारणा 1977 में कार्टर और वेगमैन द्वारा प्रस्तुत की गई थी, और कंप्यूटर विज्ञान में इसके कई अनुप्रयोग पाए गए हैं (उदाहरण के लिए देखें)।

यदि संघटन की संभावना पर हमारी ऊपरी सीमा $\epsilon <1$ है, तो हम कहते हैं कि हमारे पास $\epsilon$-लगभग सार्वभौमिकता है। इसलिए उदाहरण के लिए, यूनिवर्सल समूह में $1/m$-लगभग सार्वभौमिकता होती है।

कई, लेकिन सभी नहीं, यूनिवर्सल समूह में निम्नलिखित दृढ़ एकसमान असमानता गुण होते हैं-

$\forall x,y\in U,~x\neq y$, जब $h$ को समूह $H$ से यादृच्छिक रूप से निकाला जाता है, तो अंतर $h(x)-h(y)~{\bmod {~}}m$ समान रूप से $[m]$ में वितरित होता है।

ध्यान दें कि सार्वभौमिकता की परिभाषा केवल इस बात से संबंधित है कि क्या $h(x)-h(y)=0$, जो संघटनों की गणना करता है। एकसमान असमानता गुण अधिक दृढ़ होता है।

(इसी प्रकार, यूनिवर्सल समूह एक्सओआर (XOR) यूनिवर्सल हो सकता है यदि $\forall x,y\in U,~x\neq y$, मान $h(x)\oplus h(y)~{\bmod {~}}m$ को $[m]$ में समान रूप से वितरित किया जाता है जहां $\oplus$ बिटवाइज़ विशिष्ट या ऑपरेशन है। यह केवल तभी संभव है जब $m$ दो की घात हो।)

एक और भी दृढ़ स्थिति युग्‍मानूसार स्वतंत्रता है- हमारे पास यह गुण है जब $\forall x,y\in U,~x\neq y$ हमारे पास संभावना है कि $x,y$ हैश मानों $z_{1},z_{2}$ के किसी भी युग्म के लिए हैश होगा जैसे कि वे पूरी तरह से यादृच्छिक थे- $P(h(x)=z_{1}\land h(y)=z_{2})=1/m^{2}$। युग्‍मानूसार स्वतंत्रता को कभी-कभी दृढ़ सार्वभौमिकता कहा जाता है।

एक अन्य गुण एकरूपता है. हम कहते हैं कि समूह एक समान है यदि सभी हैश मान समान रूप से संभावित हैं- $P(h(x)=z)=1/m$ किसी भी हैश मान $z$ के लिए। सार्वभौमिकता का तात्पर्य एकरूपता नहीं है। हालाँकि, दृढ़ सार्वभौमिकता का तात्पर्य एकरूपता से है।

समान दूरी के गुण वाले समूह को देखते हुए, कोई हैश फ़ंक्शन में $[m]$ मानों के साथ एक समान रूप से वितरित यादृच्छिक स्थिरांक जोड़कर युग्‍मानूसार स्वतंत्र या दृढ़ता से यूनिवर्सल हैश समूह का उत्पादन कर सकता है। (इसी प्रकार, यदि $m$ दो की घात है, तो हम एक्सओआर यूनिवर्सल हैश समूह से एक विशेष या समान रूप से वितरित यादृच्छिक स्थिरांक के साथ युग्‍मानूसार स्वतंत्रता प्राप्त कर सकते हैं।) चूंकि स्थिरांक द्वारा बदलाव कभी-कभी अनुप्रयोगों में अप्रासंगिक होता है (जैसे हैश टेबल), समान दूरी के गुण और युग्‍मानूसार स्वतंत्र के बीच सावधानीपूर्वक अंतर कभी-कभी नहीं किया जाता है।

कुछ अनुप्रयोगों (जैसे हैश टेबल) के लिए, हैश मानों के कम से कम महत्वपूर्ण बिट्स का भी यूनिवर्सल होना महत्वपूर्ण है। जब कोई समूह दृढ़ता से यूनिवर्सल होता है, तो इसकी गारंटी होती है- यदि $H$, $m=2^{L}$ के साथ दृढ़ता से यूनिवर्सल समूह है, तो सभी $h\in H$ के लिए $h{\bmod {2^{L'}}}$ फ़ंक्शन से बना समूह भी $L'\leq L$ के लिए दृढ़ता से यूनिवर्सल है। दुर्भाग्य से, यह बात (केवल) यूनिवर्सल समूहों के लिए सत्य नहीं है। उदाहरण के लिए, सर्वसमिका फ़ंक्शन $h(x)=x$ से बना समूह स्पष्ट रूप से यूनिवर्सल है, लेकिन फ़ंक्शन $h(x)=x{\bmod {2^{L'}}}$ से बना समूह यूनिवर्सल होने में विफल रहता है।

यूएमएसी (UMAC) और पॉली1305-एईएस (Poly1305-AES) और कई अन्य संदेश प्रमाणीकरण कोड एल्गोरिदम यूनिवर्सल हैशिंग पर आधारित हैं। ऐसे अनुप्रयोगों में, सॉफ़्टवेयर प्रत्येक संदेश के लिए विशिष्ट अस्थायी रूप के आधार पर, प्रत्येक संदेश के लिए एक नया हैश फ़ंक्शन चुनता है।

कई हैश टेबल कार्यान्वयन यूनिवर्सल हैशिंग पर आधारित हैं। ऐसे अनुप्रयोगों में, प्रायः सॉफ़्टवेयर नया हैश फ़ंक्शन तभी चुनता है जब उसे पता चलता है कि "बहुत अधिक" कीज़ टकरा गई हैं तब तक, एक ही हैश फ़ंक्शन का बार-बार उपयोग किया जाता रहेगा। (कुछ संघटन समाधान योजनाएं, जैसे कि गतिशील पूर्ण हैशिंग, प्रत्येक बार संघटन होने पर नया हैश फ़ंक्शन चुनती हैं। अन्य संघटन समाधान योजनाएं, जैसे कुक्कू हैशिंग और 2-विकल्प हैशिंग, नया हैश फ़ंक्शन चुनने से पहले कई संघटनों की अनुमति देती हैं)। पूर्णांकों, सदिशों और स्ट्रिंग्स के लिए सबसे तीव्र ज्ञात यूनिवर्सल और दृढ़ता से यूनिवर्सल हैश फ़ंक्शन का सर्वेक्षण पाया गया है।

गणितीय गारंटी

$n$ कीज़ के किसी भी निश्चित समुच्चय $S$ के लिए, यूनिवर्सल समूह का उपयोग निम्नलिखित गुणों की गारंटी देता है।

1. $S$ में किसी निश्चित $x$ के लिए, बिन $h(x)$ में कीज़ की अपेक्षित संख्या $n/m$ है। श्रृंखलन द्वारा हैश तालिकाओं को कार्यान्वित करते समय, यह संख्या की $x$ (उदाहरण के लिए परिप्रश्न, सम्मिलन या विलोपन) से जुड़े ऑपरेशन के अपेक्षित कार्यावधि के समानुपाती होती है।
2. $S$ में $x\neq y$ के साथ कीज़ $x,y$ के युग्म की अपेक्षित संख्या जो ($h(x)=h(y)$) से टकराती है, ऊपर $n(n-1)/2m$ से परिबद्ध है, जो $O(n^{2}/m)$ क्रम की है। जब बिन्स की संख्या, $m$ को $n$ में रैखिक चुना जाता है (अर्थात, $\Omega (n)$ में फ़ंक्शन द्वारा निर्धारित किया जाता है, तो संघटन की अपेक्षित संख्या $O(n)$ होती है। जब $n^{2}$ बिन्स में हैशिंग की जाती है, तो कम से कम आधी संभावना के साथ कोई संघटन नहीं होता है।
3. कम से कम $t$ कीज़ वाली बिन्स में कीज़ की अपेक्षित संख्या ऊपर $2n/(t-2(n/m)+1)$ से परिबद्ध है। इस प्रकार, यदि प्रत्येक बिन की क्षमता को औसत आकार ($t=3n/m$) से तीन गुना तक सीमित किया जाता है, तो अतिप्रवाहित बिन्स में कीज़ की कुल संख्या अधिकतम $O(m)$ होती है। यह केवल उस हैश समूह के साथ लागू होता है जिसकी संघटन की संभावना $1/m$ से ऊपर होती है। यदि कमजोर परिभाषा का उपयोग किया जाता है, इसे $O(1/m)$ द्वारा सीमित किया जाता है, तो यह परिणाम अब सत्य नहीं है।

जैसा कि उपरोक्त गारंटी किसी भी निश्चित समुच्चय $S$ के लिए होती है, वे तब भी मान्य होती हैं जब डेटा समुच्चय किसी प्रतिद्वंद्वी द्वारा चुना जाता है। हालाँकि, प्रतिद्वंद्वी को एल्गोरिदम के हैश फ़ंक्शन के यादृच्छिक चयन से पहले (या उससे स्वतंत्र) यह विकल्प चुनना होगा। यदि प्रतिद्वंद्वी एल्गोरिथ्म की यादृच्छिक चयन का निरीक्षण कर सकता है, तो यादृच्छिकता का कोई उद्देश्य नहीं है, और स्थिति नियतात्मक हैशिंग के समान है।

दूसरी और तीसरी गारंटी का उपयोग प्रायः रीहैशिंग के संयोजन में किया जाता है। उदाहरण के लिए, कुछ $O(n)$ संख्या में संघटनों को संभालने के लिए यादृच्छिक एल्गोरिदम तैयार किया जा सकता है। यदि यह बहुत अधिक संघटन देखता है, तो यह समूह से एक और यादृच्छिक $h$ चुनता है और दोहराता है। सार्वभौमिकता यह गारंटी देती है कि पुनरावृत्ति की संख्या ज्यामितीय यादृच्छिक चर है।

निर्माण

चूँकि किसी भी कंप्यूटर डेटा को एक या अधिक मशीनी शब्दों के रूप में दर्शाया जा सकता है, इसलिए आमतौर पर तीन प्रकार के डोमेन के लिए हैश फ़ंक्शन की आवश्यकता होती है: मशीनी शब्द (पूर्णांक); मशीनी शब्दों के निश्चित-लंबाई वाले वैक्टर; और चर-लंबाई वाले सदिश (स्ट्रिंग्स)।

पूर्णांकों को हैश करना

यह खंड हैशिंग पूर्णांकों के मामले को संदर्भित करता है जो मशीन शब्दों में फिट होते हैं; इस प्रकार, गुणा, जोड़, भाग आदि जैसे ऑपरेशन सस्ते मशीन-स्तरीय निर्देश हैं। ब्रह्माण्ड को हैशेड होने दीजिये $\{0,\dots ,|U|-1\}$.

कार्टर और वेगमैन का मूल प्रस्तावएक प्राइम चुनना था $p\geq |U|$ और परिभाषित करें

$h_{a,b}(x)=((ax+b)~{\bmod {~}}p)~{\bmod {~}}m$

कहाँ $a,b$ बेतरतीब ढंग से चुने गए पूर्णांक मॉड्यूलो हैं $p$ साथ $a\neq 0$. (यह एक रैखिक सर्वांगसम जनरेटर का एकल पुनरावृत्ति है।)

उसे देखने के लिए $H=\{h_{a,b}\}$ एक सार्वभौमिक परिवार है, इस पर ध्यान दें $h(x)=h(y)$ केवल तभी धारण करता है जब

$ax+b\equiv ay+b+i\cdot m{\pmod {p}}$

कुछ पूर्णांक के लिए $i$ बीच में $0$ और $(p-1)/m$. तब से $p\geq |U|$, अगर $x\neq y$ उनका अंतर $x-y$ शून्येतर है और इसका व्युत्क्रम मापांक है $p$. के लिए समाधान $a$ पैदावार

$a\equiv i\cdot m\cdot (x-y)^{-1}{\pmod {p}}$.

वहाँ हैं $p-1$ के लिए संभावित विकल्प $a$ (तब से $a=0$ बाहर रखा गया है) और, अलग-अलग $i$ अनुमत सीमा में, $\lfloor (p-1)/m\rfloor$ दाहिनी ओर के लिए संभावित गैर-शून्य मान। इस प्रकार टकराव की संभावना है

$\lfloor (p-1)/m\rfloor /(p-1)\leq ((p-1)/m)/(p-1)=1/m$.

देखने का दूसरा तरीका $H$ एक सार्वभौमिक परिवार सांख्यिकीय दूरी की धारणा के माध्यम से है। अंतर लिखिए $h(x)-h(y)$ जैसा

$h(x)-h(y)\equiv (a(x-y)~{\bmod {~}}p){\pmod {m}}$.

तब से $x-y$ शून्येतर है और $a$ में समान रूप से वितरित किया जाता है $\{1,\dots ,p-1\}$, यह इस प्रकार है कि $a(x-y)$ मापांक $p$ में भी समान रूप से वितरित किया जाता है $\{1,\dots ,p-1\}$. का वितरण $(h(x)-h(y))~{\bmod {~}}m$ इस प्रकार लगभग एक समान है, संभावना में अंतर तक $\pm 1/p$ नमूनों के बीच. परिणामस्वरूप, एक समान परिवार से सांख्यिकीय दूरी होती है $O(m/p)$जो कि जब नगण्य हो जाता है $p\gg m$.

सरल हैश फ़ंक्शंस का परिवार

$h_{a}(x)=(ax~{\bmod {~}}p)~{\bmod {~}}m$

केवल लगभग सार्वभौमिक है: $\Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m$ सभी के लिए $x\neq y$. इसके अलावा, यह विश्लेषण लगभग कड़ा है; कार्टर और वेगमैन बताते हैं कि $\Pr\{h_{a}(1)=h_{a}(m+1)\}\geq 2/(m-1)$ जब कभी भी $(p-1)~{\bmod {~}}m=1$.

मॉड्यूलर अंकगणित से बचना

हैशिंग पूर्णांकों के लिए कला की स्थिति डाइट्ज़फेलबिंगर एट अल द्वारा वर्णित बहु-शिफ्ट योजना है। 1997 में। मॉड्यूलर अंकगणित से बचकर, इस विधि को लागू करना बहुत आसान है और व्यवहार में भी काफी तेजी से चलता है (आमतौर पर कम से कम चार के कारक से)). योजना मानती है कि डिब्बे की संख्या दो की शक्ति है, $m=2^{M}$. होने देना $w$ एक मशीन शब्द में बिट्स की संख्या हो। फिर हैश फ़ंक्शंस को विषम सकारात्मक पूर्णांकों पर पैरामीटराइज़ किया जाता है $a<2^{w}$ (यह एक शब्द में फिट बैठता है $w$ बिट्स)। मूल्यांकन करना $h_{a}(x)$, गुणा करें $x$ द्वारा $a$ मापांक $2^{w}$ और फिर उच्च क्रम बनाए रखें $M$ हैश कोड के रूप में बिट्स। गणितीय संकेतन में, यह है

$h_{a}(x)=(a\cdot x\,\,{\bmod {\,}}2^{w})\,\,\mathrm {div} \,\,2^{w-M}.$

यह योजना एक समान अंतर संपत्ति को संतुष्ट नहीं करती है और केवल है$2/m$-लगभग-सार्वभौमिक; किसी के लिए $x\neq y$, $\Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m$.

हैश फ़ंक्शन के व्यवहार को समझने के लिए, ध्यान दें कि, यदि $ax{\bmod {2}}^{w}$ और $ay{\bmod {2}}^{w}$ फिर, समान उच्चतम-क्रम वाले 'एम' बिट्स हों $a(x-y){\bmod {2}}^{w}$ इसके उच्चतम क्रम के एम बिट्स के रूप में या तो सभी 1 या सभी 0 हैं (यह इस पर निर्भर करता है कि क्या $ax{\bmod {2}}^{w}$ या $ay{\bmod {2}}^{w}$ बड़ा है)। मान लें कि सबसे कम महत्वपूर्ण सेट बिट $x-y$ पद पर प्रकट होता है $w-c$. तब से $a$ एक यादृच्छिक विषम पूर्णांक है और विषम पूर्णांकों का रिंग में व्युत्क्रम होता है (गणित) $Z_{2^{w}}$, यह इस प्रकार है कि $a(x-y){\bmod {2}}^{w}$ के बीच समान रूप से वितरित किया जाएगा $w$-बिट पूर्णांक स्थिति पर सबसे कम महत्वपूर्ण सेट बिट के साथ $w-c$. इसलिए संभावना यह है कि ये बिट्स सभी 0 या सभी 1 हैं $2/2^{M}=2/m$. दूसरी ओर, यदि $c<M$, फिर उच्च-क्रम के एम बिट्स

$a(x-y){\bmod {2}}^{w}$ इसमें 0 और 1 दोनों शामिल हैं, इसलिए

यह निश्चित है $h(x)\neq h(y)$. अंततः, यदि $c=M$ फिर बिट $w-M$ का

$a(x-y){\bmod {2}}^{w}$ 1 और है $h_{a}(x)=h_{a}(y)$ यदि और केवल यदि बिट्स $w-1,\ldots ,w-M+1$ 1 भी हैं, जो प्रायिकता से घटित होता है $1/2^{M-1}=2/m$.

यह विश्लेषण कड़ा है, जैसा कि उदाहरण से दिखाया जा सकता है $x=2^{w-M-2}$ और $y=3x$. वास्तव में 'सार्वभौमिक' हैश फ़ंक्शन प्राप्त करने के लिए, कोई मल्टीपल-ऐड-शिफ्ट योजना का उपयोग कर सकता है जो उच्च-क्रम बिट्स चुनता है

$h_{a,b}(x)=((ax+b){\bmod {2}}^{w+M})\,\mathrm {div} \,2^{w},$

कहाँ $a$ के साथ एक यादृच्छिक धनात्मक पूर्णांक है $a<2^{2w}$ और $b$ के साथ एक यादृच्छिक गैर-नकारात्मक पूर्णांक है $b<2^{2w}$. इसके लिए अंकगणित करने की आवश्यकता है $2w$-बिट अहस्ताक्षरित पूर्णांक। मल्टीपल-शिफ्ट का यह संस्करण डाइट्ज़फेलबिंगर के कारण है, और बाद में वोल्फेल द्वारा इसका अधिक सटीक विश्लेषण किया गया।

हैशिंग सदिश

यह अनुभाग मशीनी शब्दों के एक निश्चित-लंबाई वाले सदिश को हैश करने से संबंधित है। इनपुट को सदिश के रूप में समझें ${\bar {x}}=(x_{0},\dots ,x_{k-1})$ का $k$ मशीनी शब्द (पूर्णांक) $w$ प्रत्येक बिट)। अगर $H$ समान अंतर संपत्ति वाला एक सार्वभौमिक परिवार है, निम्नलिखित परिवार (कार्टर और वेगमैन के समय का है)। इसमें समान अंतर गुण भी है (और इसलिए सार्वभौमिक है):

$h({\bar {x}})=\left(\sum _{i=0}^{k-1}h_{i}(x_{i})\right)\,{\bmod {~}}m$, जहां प्रत्येक $h_{i}\in H$ यादृच्छिक रूप से स्वतंत्र रूप से चुना जाता है।

अगर $m$ दो की घात है, एक योग को अनन्य या से प्रतिस्थापित कर सकता है। व्यवहार में, यदि डबल-सटीक अंकगणित उपलब्ध है, तो इसे हैश फ़ंक्शंस के मल्टीपल-शिफ्ट हैश परिवार के साथ त्वरित किया जाता है।एक सदिश के साथ हैश फ़ंक्शन को प्रारंभ करें ${\bar {a}}=(a_{0},\dots ,a_{k-1})$ यादृच्छिक विषम पूर्णांकों पर $2w$ प्रत्येक बिट. फिर यदि डिब्बे की संख्या है $m=2^{M}$ के लिए $M\leq w$:

$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}$.

गुणन की संख्या को आधा करना संभव है, जो व्यवहार में मोटे तौर पर दो गुना गति में बदल जाता है।एक सदिश के साथ हैश फ़ंक्शन को प्रारंभ करें ${\bar {a}}=(a_{0},\dots ,a_{k-1})$ यादृच्छिक विषम पूर्णांकों पर $2w$ प्रत्येक बिट. निम्नलिखित हैश परिवार सार्वभौमिक है:

$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}$.

यदि डबल-प्रिसिजन ऑपरेशन उपलब्ध नहीं हैं, तो कोई इनपुट को आधे-शब्दों के सदिश के रूप में व्याख्या कर सकता है ($w/2$-बिट पूर्णांक)। इसके बाद एल्गोरिदम का उपयोग किया जाएगा $\lceil k/2\rceil$ गुणन, कहाँ $k$ सदिश में आधे शब्दों की संख्या थी। इस प्रकार, एल्गोरिदम इनपुट के प्रति शब्द एक गुणन की दर से चलता है।

उसी योजना का उपयोग पूर्णांकों को हैश करने के लिए भी किया जा सकता है, उनके बिट्स को बाइट्स के वैक्टर के रूप में व्याख्या करके। इस संस्करण में, सदिश तकनीक को सारणीबद्ध हैशिंग के रूप में जाना जाता है और यह गुणन-आधारित सार्वभौमिक हैशिंग योजनाओं के लिए एक व्यावहारिक विकल्प प्रदान करता है। उच्च गति पर मजबूत सार्वभौमिकता भी संभव है। एक सदिश के साथ हैश फ़ंक्शन को प्रारंभ करें ${\bar {a}}=(a_{0},\dots ,a_{k})$ यादृच्छिक पूर्णांकों पर $2w$ बिट्स गणना करना

$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}$.

परिणाम दृढ़ता से सार्वभौमिक है $w$ बिट्स प्रायोगिक तौर पर, यह हाल के इंटेल प्रोसेसर पर 0.2 सीपीयू चक्र प्रति बाइट पर चलता हुआ पाया गया $w=32$.

हैशिंग स्ट्रिंग

यह मशीनी शब्दों के एक चर-आकार वाले सदिश को हैश करने को संदर्भित करता है। यदि स्ट्रिंग की लंबाई को एक छोटी संख्या से सीमित किया जा सकता है, तो ऊपर से सदिश समाधान का उपयोग करना सबसे अच्छा है (वैचारिक रूप से ऊपरी सीमा तक शून्य के साथ सदिश को पैडिंग करना)। आवश्यक स्थान स्ट्रिंग की अधिकतम लंबाई है, लेकिन मूल्यांकन करने का समय है $h(s)$ की लंबाई मात्र है $s$. जब तक स्ट्रिंग में शून्य वर्जित हैं, सार्वभौमिकता को प्रभावित किए बिना हैश फ़ंक्शन का मूल्यांकन करते समय शून्य-पैडिंग को अनदेखा किया जा सकता है।ध्यान दें कि यदि स्ट्रिंग में शून्य की अनुमति है, तो पैडिंग से पहले सभी स्ट्रिंग्स में एक काल्पनिक गैर-शून्य (उदाहरण के लिए, 1) वर्ण जोड़ना सबसे अच्छा हो सकता है: इससे यह सुनिश्चित होगा कि सार्वभौमिकता प्रभावित नहीं होती है।

अब मान लीजिए कि हम हैश करना चाहते हैं ${\bar {x}}=(x_{0},\dots ,x_{\ell })$, जहां पर एक अच्छा बंधन है $\ell$ एक प्राथमिकता ज्ञात नहीं है. द्वारा प्रस्तावित एक सार्वभौमिक परिवार स्ट्रिंग का इलाज करता है $x$ एक बहुपद मॉड्यूलो के गुणांक के रूप में एक बड़ा अभाज्य। अगर $x_{i}\in [u]$, होने देना $p\geq \max\{u,m\}$ एक प्रमुख बनें और परिभाषित करें:

$h_{a}({\bar {x}})=h_{\mathrm {int} }\left({\big (}\sum _{i=0}^{\ell }x_{i}\cdot a^{\ell -i}{\big )}{\bmod {~}}p\right)$, कहाँ $a\in [p]$ समान रूप से यादृच्छिक है और $h_{\mathrm {int} }$ यूनिवर्सल फ़ैमिली मैपिंग पूर्णांक डोमेन से यादृच्छिक रूप से चुना जाता है $[p]\mapsto [m]$.

मॉड्यूलर अंकगणित के गुणों का उपयोग करके, बड़े स्ट्रिंग के लिए बड़ी संख्या उत्पन्न किए बिना उपरोक्त गणना की जा सकती है:

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

यह रोलिंग हैश#राबिन-कार्प रोलिंग हैश|राबिन-कार्प रोलिंग हैश एक रैखिक सर्वांगसम जनरेटर पर आधारित है। उपरोक्त एल्गोरिदम को मल्टीप्लिकेटिव हैश फ़ंक्शन के रूप में भी जाना जाता है। व्यवहार में, मॉड ऑपरेटर और पैरामीटर पी को केवल पूर्णांक को ओवरफ्लो करने की अनुमति देकर पूरी तरह से टाला जा सकता है क्योंकि यह कई प्रोग्रामिंग भाषाओं में मॉड (मैक्स-इंट-वैल्यू + 1) के बराबर है। नीचे दी गई तालिका कुछ लोकप्रिय कार्यान्वयनों के लिए h और a को प्रारंभ करने के लिए चुने गए मान दिखाती है।

Implementation	INITIAL_VALUE	a
Bernstein's hash function djb2	5381	33
STLPort 4.6.2	0	5
Kernighan and Ritchie's hash function	0	31
java.lang.String.hashCode()	0	31

दो तारों पर विचार करें ${\bar {x}},{\bar {y}}$ और जाने $\ell$ लंबे समय तक की लंबाई हो; विश्लेषण के लिए, छोटी स्ट्रिंग को संकल्पनात्मक रूप से लंबाई तक शून्य के साथ गद्देदार किया गया है $\ell$. आवेदन करने से पहले टक्कर $h_{\mathrm {int} }$ इसका आशय है $a$ गुणांक वाले बहुपद का मूल है ${\bar {x}}-{\bar {y}}$. इस बहुपद में अधिकतम है $\ell$ जड़ें मॉड्यूलो $p$, इसलिए टकराव की संभावना अधिकतम है $\ell /p$. यादृच्छिक के माध्यम से टकराव की संभावना $h_{\mathrm {int} }$ कुल टकराव की संभावना लाता है ${\frac {1}{m}}+{\frac {\ell }{p}}$. इस प्रकार, यदि प्रधान $p$ हैशेड स्ट्रिंग्स की लंबाई की तुलना में पर्याप्त रूप से बड़ा है, परिवार सार्वभौमिक (सांख्यिकीय दूरी में) के बहुत करीब है।

अज्ञात-लंबाई स्ट्रिंग को निश्चित-लंबाई वाले हैश मानों में हैश करने के लिए उपयोग किए जाने वाले हैश फ़ंक्शंस के अन्य सार्वभौमिक परिवारों में राबिन फ़िंगरप्रिंट और बुजस शामिल हैं।

मॉड्यूलर अंकगणित से बचना

मॉड्यूलर अंकगणित के कम्प्यूटेशनल दंड को कम करने के लिए, व्यवहार में तीन युक्तियों का उपयोग किया जाता है:# कोई प्रधान चुनता है $p$ दो की घात के करीब होना, जैसे मेर्सन प्रीमियम यह अंकगणित मॉड्यूलो की अनुमति देता है $p$ विभाजन के बिना लागू किया जाना है (जोड़ और बदलाव जैसे तेज़ संचालन का उपयोग करके)। उदाहरण के लिए, आधुनिक आर्किटेक्चर पर कोई भी काम कर सकता है $p=2^{61}-1$, जबकि $x_{i}$के 32-बिट मान हैं.

1. कोई ब्लॉक पर सदिश हैशिंग लागू कर सकता है। उदाहरण के लिए, कोई स्ट्रिंग के प्रत्येक 16-शब्द ब्लॉक पर सदिश हैशिंग लागू करता है, और स्ट्रिंग हैशिंग को लागू करता है $\lceil k/16\rceil$ परिणाम। चूंकि धीमी स्ट्रिंग हैशिंग को काफी छोटे सदिश पर लागू किया जाता है, यह अनिवार्य रूप से सदिश हैशिंग जितना तेज़ होगा।
2. कोई व्यक्ति भाजक के रूप में दो की शक्ति को चुनता है, जिससे अंकगणित मॉड्यूलो की अनुमति मिलती है $2^{w}$ विभाजन के बिना लागू किया जाना है (बिट मास्किंग के तेज़ संचालन का उपयोग करके)। UMAC#NH हैश-फ़ंक्शन परिवार|NH हैश-फ़ंक्शन परिवार यह दृष्टिकोण अपनाता है।

यह भी देखें

• के-स्वतंत्र हैशिंग
• रोलिंग हैशिंग
• सारणीकरण हैशिंग
• न्यूनतम-वार स्वतंत्रता
• यूनिवर्सल वन-वे हैश फ़ंक्शन
• कम-विसंगति अनुक्रम
• उत्तम हैशिंग

अग्रिम पठन

• 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.

बाहरी संबंध

• Open Data Structures - Section 5.1.1 - Multiplicative Hashing, Pat Morin