algorithm
हैश फंक्शंस
खोज…
हैश कार्यों का परिचय
हैश फंक्शन h() एक मनमाना फंक्शन है जो निश्चित आकार के y = h(x) : y ∈ Y को मान देने के लिए मनमाने आकार के डेटा x ∈ X का मैप करता है: y = h(x) । अच्छे हैश कार्यों में प्रतिबंध हैं:
हैश फ़ंक्शन एक समान वितरण पसंद करता है
हैश फ़ंक्शन नियतात्मक है।
h(x)को हमेशा दिए गएxलिए समान मान लौटाना चाहिएतेजी से गणना (रनटाइम ओ (1) है)
सामान्य रूप से हैश फ़ंक्शन का आकार कम है तो इनपुट डेटा का आकार: |y| < |x| । हैश फ़ंक्शन प्रतिवर्ती नहीं हैं या दूसरे शब्दों में यह टकराव हो सकता है: ∃ x1, x2 ∈ X, x1 ≠ x2: h(x1) = h(x2) । X परिमित या अनंत सेट हो सकता है और Y परिमित सेट है।
कंप्यूटर विज्ञान के बहुत सारे हिस्सों में हैश फ़ंक्शंस का उपयोग किया जाता है, उदाहरण के लिए सॉफ़्टवेयर इंजीनियरिंग, क्रिप्टोग्राफ़ी, डेटाबेस, नेटवर्क, मशीन लर्निंग और इतने पर। डोमेन विशिष्ट गुणों के साथ कई अलग-अलग प्रकार के हैश फ़ंक्शन हैं।
अक्सर हैश एक पूर्णांक मान होता है। हैश गणना के लिए प्रोग्रामिंग भाषाओं में विशेष तरीके हैं। उदाहरण के लिए, C# GetHashCode() पद्धति में सभी प्रकार के रिटर्न के लिए Int32 मान (32 बिट पूर्णांक संख्या)। Java हर वर्ग hashCode() विधि प्रदान करता है जो int लौटता है। प्रत्येक डेटा प्रकार के पास स्वयं या उपयोगकर्ता परिभाषित कार्यान्वयन हैं।
हैश के तरीके
नियतांक हैश फ़ंक्शन के लिए कई दृष्टिकोण हैं। सामान्यता की हानि के बिना, x ∈ X = {z ∈ ℤ: z ≥ 0} को सकारात्मक पूर्णांक संख्या देता है। अक्सर m प्राइम होता है (2 की सटीक शक्ति के बहुत करीब नहीं)।
| तरीका | हैश फंकशन |
|---|---|
| विभाजन विधि | h(x) = x mod m |
| गुणन विधि | h(x) = ⌊m (xA mod 1)⌋, A ∈ {z ∈ ℝ: 0 < z < 1} |
हैश टेबल
हैश फ़ंक्शन का उपयोग स्लॉट्स की एक सरणी में सूचकांक की गणना के लिए हैश तालिकाओं में किया जाता है। हैश तालिका शब्दकोशों (कुंजी-मूल्य संरचना) को लागू करने के लिए डेटा संरचना है। अगले कार्यों के लिए अच्छा कार्यान्वित हैश टेबल में O (1) समय है: कुंजी द्वारा डेटा डालें, खोजें और हटाएं। एक से अधिक कुंजियाँ एक ही स्लॉट में हैश कर सकती हैं। टकराव को हल करने के दो तरीके हैं:
चेनिंग: लिंक की गई सूची का उपयोग स्लॉट में समान हैश मान वाले तत्वों को संग्रहीत करने के लिए किया जाता है
ओपन एड्रेसिंग: प्रत्येक स्लॉट में शून्य या एक तत्व संग्रहीत होता है
अगले तरीकों का उपयोग खुले पते के लिए आवश्यक जांच अनुक्रम की गणना करने के लिए किया जाता है
| तरीका | सूत्र |
|---|---|
| रैखिक जांच | h(x, i) = (h'(x) + i) mod m |
| द्विघात जांच | h(x, i) = (h'(x) + c1*i + c2*i^2) mod m |
| डबल हैशिंग | h(x, i) = (h1(x) + i*h2(x)) mod m |
जहाँ i ∈ {0, 1, ..., m-1} , h'(x), h1(x), h2(x) सहायक हैश फ़ंक्शन हैं, c1, c2 सकारात्मक सहायक स्थिरांक हैं।
उदाहरण
x ∈ U{1, 1000}, h = x mod m । अगली तालिका में अभाज्य और अभाज्य नहीं होने की स्थिति में हैश के मानों को दिखाया गया है। बोल्ड किया गया पाठ समान हैश मूल्यों को इंगित करता है।
| एक्स | m = 100 (अभाज्य नहीं) | m = 101 (प्राइम) |
|---|---|---|
| 723 | 23 | 16 |
| 103 | 3 | 2 |
| 738 | 38 | 31 |
| 292 | 92 | 90 |
| 61 | 61 | 61 |
| 87 | 87 | 87 |
| 995 | 95 | 86 |
| 549 | 49 | 44 |
| 991 | 91 | 82 |
| 757 | 57 | 50 |
| 920 | 20 | 1 1 |
| 626 | 26 | 20 |
| 557 | 57 | 52 |
| 831 | 31 | 23 |
| 619 | 19 | 13 |
लिंक
थॉमस एच। कोरमेन, चार्ल्स ई। लिसेरसन, रोनाल्ड एल। रिवेस्ट, क्लिफोर्ड स्टीन। एल्गोरिदम का परिचय।
C # में सामान्य प्रकारों के लिए हैश कोड
GetHashCode() द्वारा निर्मित और System नामस्थान से सामान्य C # प्रकार के लिए निर्मित हैश कोड नीचे दिखाए गए हैं।
बूलियन
1 यदि मान सत्य है, तो अन्यथा।
बाइट , UInt16 , Int32 , UInt32 , सिंगल
मान (यदि आवश्यक हो तो इंट 32 पर डाला गया)।
SByte
((int)m_value ^ (int)m_value << 8);
चार
(int)m_value ^ ((int)m_value << 16);
int16
((int)((ushort)m_value) ^ (((int)m_value) << 16));
Int64 , डबल
64 बिट संख्या के निचले और ऊपरी 32 बिट्स के बीच Xor
(unchecked((int)((long)m_value)) ^ (int)(m_value >> 32));
UInt64 , DateTime , TimeSpan
((int)m_value) ^ (int)(m_value >> 32);
दशमलव
((((int *)&dbl)[0]) & 0xFFFFFFF0) ^ ((int *)&dbl)[1];
वस्तु
RuntimeHelpers.GetHashCode(this);
डिफ़ॉल्ट कार्यान्वयन सिंक ब्लॉक इंडेक्स का उपयोग किया जाता है।
तार
हैश कोड अभिकलन प्लेटफ़ॉर्म प्रकार (Win32 या Win64) पर निर्भर करता है, यादृच्छिक स्ट्रिंग हैशिंग, डीबग / रिलीज़ मोड का उपयोग करने की सुविधा। Win64 प्लेटफॉर्म के मामले में:
int hash1 = 5381;
int hash2 = hash1;
int c;
char *s = src;
while ((c = s[0]) != 0) {
hash1 = ((hash1 << 5) + hash1) ^ c;
c = s[1];
if (c == 0)
break;
hash2 = ((hash2 << 5) + hash2) ^ c;
s += 2;
}
return hash1 + (hash2 * 1566083941);
मान प्रकार
पहले गैर-स्थैतिक क्षेत्र की तलाश है और इसे हैशकोड प्राप्त करें। यदि प्रकार में कोई गैर-स्थिर फ़ील्ड नहीं है, तो प्रकार का हैशकोड लौटाता है। स्थिर सदस्य का हैशकोड नहीं लिया जा सकता है क्योंकि यदि वह सदस्य मूल प्रकार के समान है, तो गणना एक अनंत लूप में समाप्त होती है।
नल <टी>
return hasValue ? value.GetHashCode() : 0;
सरणी
int ret = 0;
for (int i = (Length >= 8 ? Length - 8 : 0); i < Length; i++)
{
ret = ((ret << 5) + ret) ^ comparer.GetHashCode(GetValue(i));
}