लगभग 70 साल पहले, आईबीएम में हंस पीटर लुहान नामक एक इंजीनियर ने चुपचाप कंप्यूटर विज्ञान के पाठ्यक्रम को बदल दिया। लुहान के पास पहले से ही कई पेटेंट हैं, जिनमें से एक ऐसे उपकरण के लिए है जो कपड़े के धागों की संख्या को माप सकता है और दूसरा उस गाइड के लिए है जो यह निर्धारित करता है कि आप अपनी रसोई में सामग्री से कौन सा मिश्रित पेय बना सकते हैं। लेकिन 1953 के आंतरिक आईबीएम पेपर में, उन्होंने जानकारी संग्रहीत करने और पुनर्प्राप्त करने के लिए एक नई तकनीक का प्रस्ताव रखा जो अब लगभग सभी कम्प्यूटेशनल प्रणालियों में बनाई गई है: हैश तालिका।

हैश टेबल डेटा संरचनाओं का एक प्रमुख वर्ग है। वे विशाल डेटाबेस में जानकारी तक पहुँचने और उसे बदलने के लिए एक विशेष रूप से सुविधाजनक तरीका प्रदान करते हैं। लेकिन यह तकनीक एक अपरिहार्य व्यापार-बंद के साथ आती है।

एक 1957 काग़ज़ में प्रकाशित आईबीएम जर्नल ऑफ रिसर्च एंड डेवलपमेंट, डब्लू. वेस्ले पीटरसन ने हैश तालिकाओं के सामने आने वाली मुख्य तकनीकी चुनौती की पहचान की: उन्हें तेज़ होने की आवश्यकता है, जिसका अर्थ है कि वे आवश्यक जानकारी जल्दी से प्राप्त कर सकते हैं। लेकिन उन्हें यथासंभव कम मेमोरी का उपयोग करते हुए कॉम्पैक्ट होने की भी आवश्यकता है। ये दोनों उद्देश्य मूलतः एक दूसरे से भिन्न हैं। जब हैश तालिका में अधिक मेमोरी हो तो डेटाबेस तक पहुंच और संशोधन अधिक तेज़ी से किया जा सकता है; और कम स्थान का उपयोग करने वाली हैश तालिकाओं में संचालन धीमा हो जाता है। जब से पीटरसन ने यह चुनौती रखी, शोधकर्ताओं ने समय और स्थान के बीच सर्वोत्तम संतुलन खोजने की कोशिश की है।

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

उन्होंने कहा, "मैं निश्चित रूप से कहूंगा कि यह एक बड़ी बात है।" रासमस पाघ, कोपेनहेगन विश्वविद्यालय में एक कंप्यूटर वैज्ञानिक। “बहुत से लोगों ने इस समस्या पर काम किया है, यह देखने की कोशिश की है कि आप समय-कुशल संचालन के साथ-साथ कितनी जगह निचोड़ सकते हैं। यही वह समस्या है जिसे मैं हल करना पसंद करूंगा।''

इसका हैश बनाना

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

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

एक अत्यंत सरलीकृत उदाहरण लेने के लिए, ऑक्सफोर्ड इंग्लिश डिक्शनरी पर विचार करें, जिसमें 600,000 से अधिक शब्दों की परिभाषाएँ हैं। यदि कोई डिजिटल संस्करण हैश तालिका पर निर्भर करता है, तो आप किसी दिए गए शब्द को कुंजी के रूप में उपयोग कर सकते हैं और सीधे परिभाषा पर आगे बढ़ सकते हैं। हैश तालिका के बिना, शब्दकोश संभवतः अनुरोधित परिभाषा पर अंततः अभिसरण करने के लिए उन्मूलन की प्रक्रिया का उपयोग करके बहुत धीमी खोज तंत्र पर निर्भर होगा। और जबकि एक हैश तालिका किसी भी शब्द को निरंतर समय (आमतौर पर एक सेकंड का एक छोटा सा अंश) में ढूंढ सकती है, शब्दकोश में शब्दों की संख्या बढ़ने पर अन्य तरीकों के लिए खोज का समय बढ़ सकता है। हैश तालिका एक अन्य लाभ भी प्रदान करती है: यह शब्दकोश को गतिशील बनाए रख सकती है, जिससे नए शब्दों को सम्मिलित करना और पुराने शब्दों को हटाना आसान हो जाता है।

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

डेटा फेरबदल

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

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

ट्रेड-ऑफ़ वक्र का विश्लेषण करके, शोधकर्ता एक हैश तालिका के लिए सबसे तेज़ संभव समय का पता लगा सकते हैं जो एक निश्चित मात्रा में स्थान का उपयोग करती है। वे किसी दिए गए ऑपरेशन समय के लिए सबसे छोटी संभव जगह का पता लगाने के लिए प्रश्न को पलट भी सकते हैं। आमतौर पर, एक चर में एक छोटा सा परिवर्तन दूसरे में एक छोटा सा परिवर्तन ला देगा, ऐसा कहा गया विलियम कुस्ज़मॉल, हार्वर्ड में एक सैद्धांतिक कंप्यूटर वैज्ञानिक और 2022 पेपर के सह-लेखक। "यदि आप समय दोगुना कर देते हैं, तो शायद आप प्रति कुंजी बर्बाद बिट्स की संख्या आधी कर देंगे।"

लेकिन उनके द्वारा डिज़ाइन की गई हैश तालिका के मामले में ऐसा नहीं है। "यदि आप समय को थोड़ा सा बढ़ाते हैं, तो प्रति कुंजी बर्बाद बिट्स तेजी से कम हो जाते हैं," कुज़्ज़मौल ने कहा। व्यापार-बंद वक्र इतना तीव्र था कि यह सचमुच चार्ट से बाहर हो गया था।

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

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

यदि आइटम अपने 100वें सर्वश्रेष्ठ स्थान पर है, तो द्वितीयक डेटा संरचना संख्या 100 संलग्न करती है। और क्योंकि सिस्टम बाइनरी का उपयोग करता है, यह संख्या 100 को 1100100 के रूप में दर्शाता है। निश्चित रूप से, संख्या 1100100 को संग्रहीत करने के लिए 1 की तुलना में अधिक मेमोरी की आवश्यकता होती है। — किसी आइटम को तब दिया गया नंबर जब वह सर्वोत्तम स्थान पर हो। इस तरह के अंतर महत्वपूर्ण हो जाते हैं यदि आप, मान लीजिए, दस लाख वस्तुओं का भंडारण कर रहे हैं।

तो टीम को एहसास हुआ कि यदि आप लगातार प्राथमिक डेटा संरचना में आइटम को उनके अधिक पसंदीदा स्थानों में स्थानांतरित करते हैं, तो आप क्वेरी समय को बढ़ाए बिना द्वितीयक संरचना द्वारा खपत की गई मेमोरी को काफी कम कर सकते हैं।

पाघ ने कहा, "इस काम से पहले, किसी को भी एहसास नहीं हुआ था कि आप जानकारी को इधर-उधर घुमाकर डेटा संरचना को और संपीड़ित कर सकते हैं।" "यह बेंडर पेपर की बड़ी अंतर्दृष्टि थी।"

लेखकों ने दिखाया कि उनके आविष्कार ने सबसे कुशल हैश तालिकाओं के लिए एक नई ऊपरी सीमा स्थापित की है, जिसका अर्थ है कि यह समय और स्थान दक्षता दोनों के संदर्भ में अब तक तैयार की गई सबसे अच्छी डेटा संरचना थी। लेकिन संभावना बनी रही कि कोई और इससे भी बेहतर कर सकता है.

सफल होने के लिए बाध्य

अगले वर्ष, के नेतृत्व में एक टीम हुआचेंग यूप्रिंसटन विश्वविद्यालय के एक कंप्यूटर वैज्ञानिक ने बेंडर टीम की हैश तालिका को बेहतर बनाने का प्रयास किया। “हमने वास्तव में कड़ी मेहनत की और ऐसा नहीं कर सके,” उन्होंने कहा रेनफेई झोउ, बीजिंग में सिंघुआ विश्वविद्यालय में एक छात्र और यू की टीम का सदस्य। "तभी हमें संदेह हुआ कि उनकी ऊपरी सीमा भी निचली सीमा थी" - सबसे अच्छा जो संभवतः हासिल किया जा सकता है। "जब ऊपरी सीमा निचली सीमा के बराबर होती है, तो खेल खत्म हो जाता है, और आपके पास अपना उत्तर होता है।" चाहे आप कितने भी चतुर क्यों न हों, कोई भी हैश टेबल इससे बेहतर काम नहीं कर सकती।

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

लेकिन अगर उन्हें हैश टेबल के बारे में कुछ भी नहीं पता था (सिवाय इसके कि यह स्थान-कुशल था), तो शोधकर्ता मेमोरी तक पहुंचने के लिए आवश्यक न्यूनतम संख्या का पता कैसे लगा सकते थे? उन्होंने इसे पूरी तरह से सिद्धांत से प्राप्त किया, संचार जटिलता के सिद्धांत नामक एक प्रतीत होता है असंबंधित क्षेत्र का उपयोग करते हुए, जो अध्ययन करता है कि दो पक्षों के बीच जानकारी देने के लिए कितने बिट्स की आवश्यकता होती है। अंततः, टीम सफल हुई: उन्होंने यह पता लगाया कि किसी डेटा संरचना को प्रति ऑपरेशन कितनी बार अपनी मेमोरी तक पहुंच प्राप्त करनी चाहिए।

यह उनकी प्रमुख उपलब्धि थी. फिर वे किसी भी स्थान-कुशल हैश तालिका के लिए रनटाइम पर निचली सीमा स्थापित करने में सक्षम थे। और उन्होंने देखा कि यह बिल्कुल बेंडर हैश टेबल से मेल खाता है। झोउ ने कहा, "हमने सोचा कि [पहले] इसमें सुधार किया जा सकता है।" "यह पता चला कि हम गलत थे।" बदले में, इसका मतलब यह था कि पीटरसन की समस्या अंततः हल हो गई थी।

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

भविष्य में हैशिंग

नई हैश तालिका की अभूतपूर्व दक्षता के बावजूद, निकट भविष्य में कोई भी इसे बनाने का प्रयास नहीं करेगा। इसका निर्माण करना बहुत जटिल है। झोउ ने कहा, "एक एल्गोरिदम जो सिद्धांत में तेज़ है, जरूरी नहीं कि वह व्यवहार में भी तेज़ हो।"

कुज़्ज़मॉल ने कहा, सिद्धांत और व्यवहार के बीच इस तरह के अंतराल का लंबे समय तक बने रहना असामान्य नहीं है, क्योंकि सिद्धांतकार निरंतर कारकों को अनदेखा करते हैं। किसी ऑपरेशन को करने में लगने वाला समय आम तौर पर एक संख्या, कुछ स्थिरांक से गुणा किया जाता है जिसका सटीक मान सैद्धांतिक दृष्टिकोण से महत्वहीन हो सकता है। "लेकिन व्यवहार में, स्थिरांक वास्तव में मायने रखते हैं," उन्होंने कहा। "वास्तविक दुनिया में, 10 का कारक एक गेम एंडर है।"

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

मिटज़ेनमाकर को उम्मीद है कि 2023 का परिणाम जल्द ही एक और प्रकार का लाभ दे सकता है: "जब भी आपको एक नई निचली सीमा मिलती है - विशेष रूप से वह जिसमें कुछ नई तकनीकें शामिल होती हैं - तो हमेशा उम्मीद रहती है कि आप उनका उपयोग कर सकते हैं ... संबंधित समस्याओं के लिए।"

कंप्यूटर वैज्ञानिक ने कहा, यह जानने से बौद्धिक संतुष्टि भी मिलती है कि आपने एक कठिन और लंबे समय से चली आ रही समस्या का समाधान कर लिया है पियोट्र इंडिक मैसाचुसेट्स इंस्टीट्यूट ऑफ टेक्नोलॉजी के. "एक बार जब आप आश्वस्त हो जाएं कि कुछ डेटा संरचनाओं में सुधार नहीं किया जा सकता है, तो यह शोध प्रयास पर ध्यान केंद्रित करने में मदद कर सकता है।" अंत में, डेटा शोधकर्ता पीटरसन की चुनौती से अपना ध्यान हटाकर सैद्धांतिक कंप्यूटर विज्ञान में नई समस्याओं पर ध्यान केंद्रित कर सकते हैं, जिनमें कोई कमी नहीं है।