हैश सारणियाँ

एक हैश सारणी (hash table) एक हैश फ़ंक्शन (hash function) का उपयोग करके कुंजियों (keys) को सरणी (array) स्थितियों में मैप करके एक शब्दकोश (dictionary) को लागू करती है, जो टकरावों (collisions) को अच्छी तरह से प्रबंधित करने पर अपेक्षित स्थिर-समय प्रविष्टि (insertion), विलोपन (deletion) और लुकअप (lookup) का समर्थन करती है।

Definition

एक हैश सारणी एक डेटा संरचना है जो एक सरणी में कुंजी-मूल्य जोड़े (key-value pairs) को संग्रहीत करती है, जिसमें प्रत्येक कुंजी से सरणी में एक सूचकांक (index) की गणना करने के लिए एक हैश फ़ंक्शन का उपयोग किया जाता है, और एक टकराव-समाधान योजना (collision-resolution scheme) होती है जो उन अलग-अलग कुंजियों को संभालती है जो एक ही सूचकांक पर हैश होती हैं।

Scope

यह विषय हैशिंग-आधारित शब्दकोशों को शामिल करता है: हैश फ़ंक्शन और उनके वांछनीय गुण, टकराव-समाधान रणनीतियाँ (अलग श्रृंखलाकरण (separate chaining) और खुला पताकरण (open addressing)), लोड फ़ैक्टर (load factor) और आकार बदलना (resizing), सार्वभौमिक (universal) और पूर्ण हैशिंग (perfect hashing) फ़्रेमवर्क जो सिद्ध करने योग्य गारंटी देते हैं, और ब्लूम फ़िल्टर (Bloom filters) जैसी संबंधित संभाव्य संरचनाएँ। इसमें क्रमबद्ध शब्दकोश संरचनाएँ शामिल नहीं हैं, जिन्हें सर्च ट्री (search trees) के तहत कवर किया गया है।

Core questions

• एक हैश फ़ंक्शन को क्या अच्छा बनाता है, और कुंजियों को समान रूप से फैलाने के लिए इसे कैसे चुना जाता है?
• श्रृंखलाकरण (chaining) या खुले पताकरण (open addressing) द्वारा टकरावों को कैसे हल किया जाता है, और वे लागत को कैसे प्रभावित करते हैं?
• लोड फ़ैक्टर (load factor) अपेक्षित संचालन समय को कैसे नियंत्रित करता है और आकार बदलने को कैसे ट्रिगर करता है?
• सार्वभौमिक (universal) और पूर्ण हैशिंग (perfect hashing) सिद्ध करने योग्य प्रदर्शन गारंटी कैसे प्रदान करते हैं?
• एक ब्लूम फ़िल्टर जैसी अंतरिक्ष-कुशल संभाव्य संरचना एक सटीक सारणी की तुलना में कब बेहतर होती है?

Key concepts

• हैश फ़ंक्शन
• अलग श्रृंखलाकरण
• खुला पताकरण
• लोड फ़ैक्टर
• पुनः हैशिंग और आकार बदलना
• सार्वभौमिक हैशिंग
• पूर्ण हैशिंग
• ब्लूम फ़िल्टर

Key theories

सार्वभौमिक हैशिंग

एक सावधानीपूर्वक डिज़ाइन किए गए (सार्वभौमिक) परिवार से यादृच्छिक रूप से हैश फ़ंक्शन का चयन करके, कुंजियों के किसी भी निश्चित सेट के लिए टकरावों की कम अपेक्षित संख्या की गारंटी दी जा सकती है, जिससे सबसे खराब स्थिति वाले प्रतिकूल इनपुट (adversarial inputs) की संभावना कम हो जाती है।

टकराव समाधान और लोड फ़ैक्टर

अलग श्रृंखलाकरण (separate chaining) प्रति स्लॉट (slot) सूचियों में टकराने वाली कुंजियों को संग्रहीत करता है, जबकि खुला पताकरण (open addressing) वैकल्पिक स्लॉट की जाँच करता है; अपेक्षित संचालन समय लोड फ़ैक्टर (प्रति स्लॉट प्रविष्टियाँ) द्वारा नियंत्रित होता है, और इसे सीमित रखने के लिए तालिकाओं का आकार बदला जाता है।

Clinical relevance

हैश सारणियाँ कंप्यूटिंग में सबसे अधिक उपयोग की जाने वाली डेटा संरचनाओं में से हैं: वे मानक पुस्तकालयों में शब्दकोशों और सेटों को लागू करती हैं, डेटाबेस अनुक्रमण (database indexing) और इन-मेमोरी कैश (in-memory caches) को शक्ति प्रदान करती हैं, कंपाइलरों में प्रतीक तालिकाओं (symbol tables) का समर्थन करती हैं, और डुप्लिकेशन हटाने (deduplication) और सदस्यता परीक्षणों (membership tests) का आधार बनती हैं। ब्लूम फ़िल्टर डेटाबेस और नेटवर्किंग में सदस्यता प्रश्नों को स्केल करते हैं जहाँ सटीक भंडारण अव्यावहारिक होता है।

History

हैशिंग की उत्पत्ति 1950 के दशक में आईबीएम में हंस पीटर लुहन (Hans Peter Luhn) के काम से हुई। बर्टन ब्लूम (Burton Bloom) ने 1970 में अंतरिक्ष-कुशल ब्लूम फ़िल्टर पेश किया। कार्टर (Carter) और वेगमान (Wegman) ने 1970 के दशक के अंत और 1980 के दशक की शुरुआत में सार्वभौमिक और बाद में दृढ़ता से सार्वभौमिक हैशिंग को औपचारिक रूप दिया, जिससे हैशिंग को इसकी कठोर सैद्धांतिक नींव मिली।

Key figures

• Hans Peter Luhn
• J. Lawrence Carter
• Mark Wegman
• Burton H. Bloom

Seminal works

• bloom1970
• carter1981
• cormen2009

Frequently asked questions

हैश सारणी संचालन को अपेक्षित O(1) के रूप में क्यों वर्णित किया जाता है न कि गारंटीकृत O(1) के रूप में?

यदि कई कुंजियाँ टकराती हैं, तो संचालन O(n) की ओर बिगड़ सकता है। एक अच्छे हैश फ़ंक्शन और सीमित लोड फ़ैक्टर के तहत अपेक्षित रूप से स्थिर समय बना रहता है; सार्वभौमिक हैशिंग एक खराब स्थिति को असंभव बनाती है, लेकिन सबसे खराब स्थिति की गारंटी के लिए पूर्ण हैशिंग या अन्य तकनीकों की आवश्यकता होती है।

ब्लूम फ़िल्टर क्या है और यह हैश सारणी से कैसे भिन्न है?

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