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

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

परिचय

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]$ मानों के साथ एक समान रूप से वितरित यादृच्छिक स्थिरांक जोड़कर एक जोड़ीदार स्वतंत्र या दृढ़ता से सार्वभौमिक हैश परिवार का उत्पादन कर सकता है।

, जो टकरावों को गिनता है। एकसमान अंतर गुण अधिक मजबूत होता है।

(इसी प्रकार, एक सार्वभौमिक परिवार XOR सार्वभौमिक हो सकता है यदि , मूल्य में समान रूप से वितरित किया जाता है कहाँ बिटवाइज़ एक्सक्लूसिव या ऑपरेशन है। यह तभी संभव है जब दो की शक्ति है।)

एक और भी मजबूत स्थिति जोड़ीवार स्वतंत्र है: हमारे पास यह संपत्ति कब है हमें इसकी संभावना है हैश मानों के किसी भी जोड़े को हैश कर देगा ऐसा लगता है मानो वे बिल्कुल यादृच्छिक थे: . जोड़ीवार स्वतंत्रता को कभी-कभी मजबूत सार्वभौमिकता कहा जाता है।

एक अन्य गुण है एकरूपता. हम कहते हैं कि एक परिवार एक समान है यदि सभी हैश मान समान रूप से संभावित हैं: किसी भी हैश मान के लिए . सार्वभौमिकता का अर्थ एकरूपता नहीं है। हालाँकि, मजबूत सार्वभौमिकता का तात्पर्य एकरूपता से है।

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

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

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

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

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

1. किसी भी निश्चित के लिए $x$ में $S$, बिन में चाबियों की अपेक्षित संख्या $h(x)$ है $n/m$. अलग-अलग चेनिंग द्वारा हैश तालिकाओं को लागू करते समय, यह संख्या कुंजी से जुड़े ऑपरेशन के अपेक्षित चलने के समय के समानुपाती होती है $x$ (उदाहरण के लिए कोई क्वेरी, सम्मिलन या विलोपन)।
2. चाबियों के जोड़े की अपेक्षित संख्या $x,y$ में $S$ साथ $x\neq 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