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

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

पृष्ठभूमि

See also: Hash function

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

इन समस्याओं का समाधान हैश फ़ंक्शंस के एक बड़े परिवार से यादृच्छिक रूप से एक फ़ंक्शन चुनना है। हैश फ़ंक्शन को चुनने में यादृच्छिकता का उपयोग रुचि की किसी भी कुंजी के हैश कोड के कुछ वांछित यादृच्छिक व्यवहार की गारंटी के लिए किया जा सकता है। इन पंक्तियों के साथ पहली परिभाषा सार्वभौमिक हैशिंग थी, जो किन्हीं दो निर्दिष्ट कुंजियों के लिए कम टकराव की संभावना की गारंटी देती है। इसकी अवधारणा $k$-स्वतंत्र हैशिंग, 1981 में वेगमैन और कार्टर द्वारा शुरू की गई, के परिवारों के लिए यादृच्छिक व्यवहार की गारंटी को मजबूत करता है $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}$ गोलाई संबंधी मुद्दों के कारण. अगले, कोई परिभाषित कर सकता है a $(\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}$, जो आधुनिक कंप्यूटरों पर तेज़ परिमित क्षेत्र अंकगणित का समर्थन करता है। यह CLHash के लिए डेनियल लेमायर और ओवेन कैसर द्वारा अपनाया गया दृष्टिकोण था।

सारणीबद्ध हैशिंग

Main article: Tabulation hashing

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

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

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

उदाहरण के लिए, हैश_टेबल#सेपरेट_चेनिंग हैश फ़ंक्शंस के '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-स्वतंत्र।

MAX-3SAT समस्या के लिए कार्लॉफ़-ज़्विक एल्गोरिदम को 3-स्वतंत्र यादृच्छिक चर के साथ कार्यान्वित किया जा सकता है।

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

अग्रिम पठन

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