K-इंडिपेंडेंट हैशिंग

कंप्यूटर विज्ञान में, हैश फ़ंक्शन के समूह को k-इंडिपेंडेंट, k-वाइज इंडिपेंडेंट या k-यूनिवर्सल कहा जाता है। यदि समूह से रैंडम रूप से किसी फ़ंक्शन का चयन करना निश्चितता प्रदान करता है कि किसी भी डेसिग्नेटेड k कुंजी के हैश कोड इंडिपेंडेंट रैंडम वेरिएबल हैं (नीचे सही गणितीय परिभाषाये देखना हैं)। ऐसे समूह रैंडम एल्गोरिदम या डेटा संरचनाओं में अच्छे औसत स्थीतीओ के प्रदर्शन की अनुमति देते हैं, यद्यपि ही इनपुट डेटा किसी एडवेर्सरी द्वारा चुना गया हो। इंडिपेंडेंस की डिग्री और हैश फ़ंक्शन के मूल्यांकन की दक्षता के बीच ट्रेड-ऑफ का अच्छी तरह से अध्ययन किया गया है, और कई k-इंडिपेंडेंट समूहों का प्रस्ताव किया गया है।

पृष्ठभूमि

See also: हैश फंक्शन

हैशिंग का लक्ष्य साधारण तौर पर कुछ बड़े डोमेन (यूनिवर्स) $U$ से छोटी रेंज में जैसे $m$ बिन्स (लेबल्ड $[m]=\{0,\dots ,m-1\}$ कुंजियों को मैप करना होता है। रैंडम एल्गोरिदम और डेटा संरचनाओं के विश्लेषण में, विभिन्न कुंजियों के हैश कोड का यादृच्छिक रूप से व्यवहार करना प्रायः वांछनीय होता है। उदाहरण के लिए, यदि प्रत्येक कुंजी का हैश कोड इंडिपेंडेंस रैंडम विकल्प $[m]$ था, चेर्नॉफ़ बाउंड का उपयोग करके प्रति बिन कुंजियों की संख्या का विश्लेषण किया जा सकता है। नियतात्मक हैश फ़ंक्शन किसी एडवेर्सिअल सेटिंग में ऐसी कोई निश्चितता नहीं दे सकता है, क्योंकि प्रतिद्वंद्वी बिन की सही प्रीइमेज के लिए कुंजियाँ चुन सकता है। इसके अतिरिक्त, नियतात्मक हैश फ़ंक्शन रीहैशिंग की अनुमति नहीं देता है: कभी-कभी इनपुट डेटा हैश फ़ंक्शन के लिए खराब हो जाता है (उदाहरण के लिए बहुत अधिक टकराव होते हैं), इसलिए कोई हैश फ़ंक्शन को परिवर्तित करना नहीं चाहता हैं।

इन समस्याओं का समाधान हैश फ़ंक्शंस के बड़े समूह से रैंडम रूप से फ़ंक्शन चुनना है। हैश फ़ंक्शन को चुनने में रैंडम का उपयोग रुचि की किसी भी कुंजी के हैश कोड के कुछ डिजायर्ड रैंडम बिहैवियर की निश्चितता के लिए किया जा सकता है। इन पंक्तियों के साथ पहली परिभाषा यूनिवर्सल हैशिंग थी, जो किन्हीं दो निर्दिष्ट कुंजियों के लिए कम टकराव की संभावना की निश्चितता देती है। इसकी अवधारणा $k$-इंडिपेंडेंट हैशिंग, 1981 में वेगमैन और कार्टर द्वारा प्रारम्भ की गई, k- समूहों के लिए रैंडम बिहैवियर की निश्चितता को मजबूत करता है $k$ निर्दिष्ट कुंजियाँ, और हैश कोड के समान वितरण पर निश्चितता जोड़ता है।

परिभाषाएँ

सबसे दृढ परिभाषा, वेगमैन और कार्टर द्वारा प्रस्तुत की गईदृढ़ता से 'यूनिवर्सल$_{k}$' के अनुसार हैश समूह'', निम्नलिखित है। हैश फ़ंक्शंस का समूह $H=\{h:U\to [m]\}$ है $k$-इंडिपेंडेंट यदि किसी के लिए $k$ विशिष्ट कुंजियाँ $(x_{1},\dots ,x_{k})\in U^{k}$ और कोई भी $k$ हैश कोड (आवश्यक नहीं कि अलग हो) $(y_{1},\dots ,y_{k})\in [m]^{k}$ होता हैं, हमारे पास:

$\Pr _{h\in H}\left[h(x_{1})=y_{1}\land \cdots \land h(x_{k})=y_{k}\right]=m^{-k}$

यह परिभाषा निम्नलिखित दो स्थितियों के बराबर है:

1. किसी भी निश्चित के लिए $x\in U$, जैसा $h$ से रैंडम रूप से $H$, $h(x)$ से निर्वासित किया जाता है जो समान रूप से $[m]$ से वितरित किया जाता है।
2. किसी भी निश्चित, विशिष्ट कुंजी $x_{1},\dots ,x_{k}\in U$ के लिए, जैसा $h$ से रैंडम रूप से $H$, $h(x_{1}),\dots ,h(x_{k})$ निर्वासित किया जाता है इंडिपेंडेंट रैंडम वेरिएबल्स हैं।

प्रायः राउंडिंग इश्यूज के कारण सही संयुक्त संभावना $m^{-k}$ प्राप्त करना असुविधाजनक होता है। निम्न, कोई $(\mu ,k)$ से इंडिपेंडेंट समुह को संतुष्ट करने के लिए परिभाषित कर सकता है:

$\forall$ अलग $(x_{1},\dots ,x_{k})\in U^{k}$ और $\forall (y_{1},\dots ,y_{k})\in [m]^{k}$, $~~\Pr _{h\in H}\left[h(x_{1})=y_{1}\land \cdots \land h(x_{k})=y_{k}\right]\leq \mu /m^{k}$

उस पर ध्यान दे, यद्यपि ही $\mu$ 1 के निकट है, $h(x_{i})$ अब इंडिपेंडेंट रैंडम वेरिएबल्स नहीं हैं, जो प्रायः रैंडम एल्गोरिदम के विश्लेषण में समस्या है। इसलिए, राउंडिंग इश्यूज से निवारण का अधिक सामान्य विकल्प यह सिद्ध करना है कि हैश समूह सांख्यिकीय दूरी $k$-इंडिपेंडेंट समूह के निकट है, जो इंडिपेंडेंस गुणों के ब्लैक-बॉक्स उपयोग की अनुमति देता है।

तकनीक

रैंडम गुणांक वाले बहुपद

निर्माण की मूल तकनीक k-कार्टर और वेगमैन द्वारा दिए गए इंडिपेंडेंट हैश फ़ंक्शन, बड़ी अभाज्य संख्या p का चयन करना था, k रैंडम संख्या मॉड्यूलो p को चुनना होता हैं, और इन संख्याओं को डिग्री के बहुपद के गुणांक k − 1 के रूप में उपयोग करें जिनके मान मॉड्यूलो p हैं उसका उपयोग हैश फ़ंक्शन के मान के रूप में किया जाता है। दी गई डिग्री मापांक के सभी बहुपद p समान रूप से संभावित हैं, और कोई भी बहुपद किसी के द्वारा विशिष्ट रूप से निर्धारित होता है k-ट्यूपल आर्गुमेंट के साथ आर्गुमेंट-मूल्य जोड़े का समूह, जिससे यह किसी k-ट्यूपल आर्गुमेंट के समूह को किसी में भी मैप किए जाने की समान रूप से संभावना k-हैश मानों का टुपल का अनुसरण करता है।

सामान्य तौर पर बहुपद किसी भी परिमित क्षेत्र में बहुपद मूल्यांकन हो सकता है। मॉड्यूलो प्राइम फ़ील्ड के अतिरिक्त, प्रसिद्ध विकल्प आकार $2^{n}$ का फ़ील्ड है, जो आधुनिक कंप्यूटरों पर तेज़ परिमित क्षेत्र अरिथमेटिक का समर्थन करता है। यह सीएल हैश के लिए डेनियल लेमायर और ओवेन कैसर द्वारा अपनाया गया कार्य था।

टैब्युलेशन हैशिंग

Main article: टैब्युलेशन हैशिंग

सारणीकरण हैशिंग प्रत्येक कुंजी को बाइट में विभाजित करके, प्रत्येक बाइट को सूचकांक के रूप में रैंडम संख्याओं की तालिका में (प्रत्येक बाइट स्थिति के लिए एक अलग तालिका के साथ) उपयोग करके, और इन तालिका लुकअप एक बिटवाइज़ एक्सक्लूसिव ऑपरेशन के परिणामों को जोड़कर हैश मानों की मैपिंग की तकनीक है। इस प्रकार, इसके आरंभीकरण में बहुपद विधि की तुलना में अधिक रैंडम की आवश्यकता होती है, लेकिन संभावित रूप से धीमी गुणन संक्रियाओं से बचा जाता है। यह 3-इंडिपेंडेंस है लेकिन 4-इंडिपेंडेंस नहीं है। टैब्युलेशन हैशिंग की विविधताएं इनपुट कुंजी से बिट्स के ओवरलैपिंग संयोजनों के आधार पर तालिका लुकअप निष्पादित करके, या सरल सारणीबद्ध हैशिंग को पुनरावृत्त रूप से क्रियान्वित करके स्वतंत्रता की उच्च डिग्री प्राप्त कर सकती हैं।

विभिन्न प्रकार के टकराव समाधान के लिए इंडिपेंडेंस की आवश्यकता

प्रति ऑपरेशन निरंतर अपेक्षित समय की निश्चितता के लिए आवश्यक इंडिपेंडेंस के स्तर के अनुसार, k-इंडिपेंडेंस की धारणा का उपयोग हैशटेबल्स में विभिन्न के बीच अंतर करने के लिए किया जा सकता है।

उदाहरण के लिए, हैश चेनिंग हैश फ़ंक्शंस के '2-इंडिपेंडेंट' समूहों के साथ भी निरंतर अपेक्षित समय लेती है, क्योंकि किसी दी गई कुंजी की खोज करने का अपेक्षित समय उन टकरावों की अपेक्षित संख्या से सीमित होता है जिनमें कुंजी सम्मलित होती है। अपेक्षा की रैखिकता, यह अपेक्षित संख्या हैश तालिका में अन्य सभी कुंजियों के योग के बराबर होती है, इस संभावना की दी गई कुंजी और दूसरी कुंजी टकराती है। क्योंकि इस योग की टर्म्स में केवल दो कुंजियों से जुड़ी संभाव्य घटनाएं सम्मलित हैं, 2-इंडिपेंडेंट यह सुनिश्चित करने के लिए पर्याप्त है कि इस योग का वही मूल्य है जो वास्तव में रैंडम हैश फ़ंक्शन के लिए होता हैं।

डबल हैशिंग, हैशिंग की एक और विधि है जिसके लिए कम स्तर की स्वतंत्रता की आवश्यकता होती है। यह ओपन एड्रेसिंग का एक रूप है जो दो हैश फ़ंक्शन का उपयोग करता है: एक प्रोब सीक्वेंस की प्रारम्भ निर्धारित करने के लिए, और दूसरा प्रोब सीक्वेंस में स्थितियों के बीच चरण आकार निर्धारित करने के लिए होता हैं। जब तक ये दोनों 2-इंडिपेंडेंट हैं, यह विधि प्रति ऑपरेशन निरंतर अपेक्षित समय देती है।

दूसरी ओर, रैखिक जांच, ओपन एड्रेसिंग का सरल रूप जहां चरण का आकार हमेशा एक होता है, 5-इंडिपेंडेंट हैश फ़ंक्शन के साथ प्रति ऑपरेशन निरंतर अपेक्षित समय में काम करने की निश्चितता दी जा सकती है, और 4-इंडिपेंडेंट हैश फ़ंक्शंस उपस्थित हैं जिनके लिए प्रति ऑपरेशन लॉगरिदमिक समय लगता है।

कुक्कू हैशिंग के लिए आवश्यक k-इंडिपेंडेंस 2021 तक ज्ञात नहीं है। 2009 में इसे दिखाया गया था वह $O(\log n)$-इंडिपेंडेंस पर्याप्त है, और कम से कम 6-इंडिपेंडेंस की आवश्यकता है। एक अन्य दृष्टिकोण टेब्यूलेशन हैशिंग का उपयोग करना है, जो 6-इंडिपेंडेंट नहीं है, लेकिन 2012 में दिखाया गया था। कुक्कू हैशिंग के लिए पर्याप्त अन्य गुण होता हैं। 2014 से तीसरा प्रयास कुक्कू हैशटेबल को तथाकथित स्टैश के साथ थोड़ा संशोधित करना है, जो 2-इंडिपेंडेंट हैश फ़ंक्शंस से अधिक कुछ भी उपयोग करना संभव नहीं बनाता है।

अन्य अनुप्रयोग

केन (गणितज्ञ), नेल्सन और डेविड वुड्रफ ने 2010 में विशिष्ट एलिमेंट्स समस्या के लिए फ्लैजोलेट-मार्टिन एल्गोरिदम में सुधार किया था। एक $\varepsilon$ सही उत्तर के अप्प्रोक्सिमशन के लिए, उन्हें एक ${\tfrac {\log 1/\varepsilon }{\log \log 1/\varepsilon }}$ इंडिपेंडेंट हैश फ़ंक्शन देने की आवश्यकता है।

डाइमेंसनलिटी में कमी के लिए काउंट स्केच एल्गोरिदम को दो हैश फ़ंक्शन 2-इंडिपेंडेंट और 4-इंडिपेंडेंट की आवश्यकता होती है।

एम्एएक्स-3एसएटी समस्या के लिए कार्लॉफ़-ज़्विक एल्गोरिदम को 3-इंडिपेंडेंट रैंडम वेरिएबल्स के साथ कार्यान्वित किया जा सकता है।

मिनहैश एल्गोरिदम का $\log {\tfrac {1}{\epsilon }}$-इंडिपेंडेंट हैश फंक्शन्स उपयोग करके कार्यान्वित किया जा सकता है जैसा कि 1999 में पीटर इंडीक द्वारा सिद्ध किया गया था।

अग्रिम पठन

• Motwani, Rajeev; Raghavan, Prabhakar (1995). Randomized Algorithms. Cambridge University Press. p. 221. ISBN 978-0-521-47465-8.