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

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

परिचय

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$ को $a\neq 0$ के साथ यादृच्छिक रूप से चुने गए पूर्णांक सापेक्ष $p$ हैं। (यह रैखिक सर्वांगसम जनरेटर की एकल पुनरावृत्ति है।)

यह देखने के लिए कि $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}}$.

$a$ के लिए $p-1$ संभावित विकल्प हैं (चूंकि $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$

केवल लगभग यूनिवर्सल है- सभी $x\neq y$ के लिए $\Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m$। इसके अतिरिक्त, यह विश्लेषण लगभग दृढ़ है कार्टर और वेगमैन दिखाते हैं कि $\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}$ में समान उच्चतम-क्रम वाले 'M' बिट्स हैं, तो $a(x-y){\bmod {2}}^{w}$ के उच्चतम क्रम M बिट्स के रूप में या तो सभी 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}$ के उच्च-क्रम M बिट्स में 0 और 1 दोनों सम्मिलित हैं, इसलिए यह निश्चित है कि $h(x)\neq h(y)$। अंत में, यदि $c=M$ है तो $a(x-y){\bmod {2}}^{w}$ का बिट $w-M$ 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$-बिट अहस्ताक्षरित पूर्णांकों पर अंकगणित करने की आवश्यकता है। गुणा-स्थानांतरण का यह संस्करण डिट्ज़फेलबिंगर के कारण है, और बाद में वोल्फ़ेल द्वारा इसका अधिक सटीक विश्लेषण किया गया।

हैशिंग वेक्टर

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

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

यदि $m$ दो की घात है, तो योग को अपवर्जित या से प्रतिस्थापित किया जा सकता है।

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

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

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

$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$ वेक्टर में आधे शब्दों की संख्या थी। इस प्रकार, एल्गोरिदम इनपुट के प्रति शब्द गुणन की "दर" पर चलता है।

उसी योजना का उपयोग पूर्णांकों के बिट्स को बाइट्स के वेक्टर के रूप में व्याख्या करके, हैशिंग पूर्णांकों के लिए भी किया जा सकता है। इस प्रकार में, वेक्टर तकनीक को सारणीकरण हैशिंग के रूप में जाना जाता है और यह गुणन-आधारित यूनिवर्सल हैशिंग योजनाओं के लिए व्यावहारिक विकल्प प्रदान करता है।

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

$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$ बिट्स पर दृढ़ता से यूनिवर्सल है। प्रायोगिक तौर पर, यह हाल के इंटेल प्रोसेसर पर $w=32$ के लिए 0.2 सीपीयू (CPU) चक्र प्रति बाइट पर रन हुआ पाया गया।

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

यह मशीनी शब्दों के एक चर-आकार वाले वेक्टर को हैश करने को संदर्भित करता है। यदि स्ट्रिंग की लंबाई को एक छोटी संख्या से सीमित किया जा सकता है, तो ऊपर से वेक्टर समाधान का उपयोग करना सबसे अच्छा है (वैचारिक रूप से ऊपरी सीमा तक शून्य के साथ वेक्टर को पैडिंग करना)। आवश्यक स्थान स्ट्रिंग की अधिकतम लंबाई है, लेकिन मूल्यांकन करने का समय है $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