हैशिंग (Hashing)
जब हम तत्वों के संग्रह (collections) के साथ काम करते हैं—जैसे स्ट्रिंग्स की लिस्ट या ट्यूपल्स की लिस्ट—तो संग्रह में किसी तत्व की तलाश करना या यह जानना कि “क्या X नामक आइटम हमारे संग्रह में है?” जैसी क्वेरी का जवाब देना गणनात्मक रूप से काफी महंगा हो सकता है। वहीं, संख्याओं की तुलना करना बहुत तेज़ होता है, और हमारे कंप्यूटर विशेष रूप से संख्याओं की तुलना कुशलता से करने में माहिर हैं (स्ट्रिंग या ट्यूपल की तरह नहीं)। ऐसे में, यदि हम अपने पास मौजूद डेटा को किसी संख्यात्मक मान में परिवर्तित कर पाएँ, तो उसे खोजना या यह जाँचना कि वह संग्रह में मौजूद है या नहीं, काफी तेज़ हो जाएगा।
किसी भी आकार के डेटा को स्थाई आकार (fixed-size) के डेटा में बदलने की तकनीक को हैशिंग (hashing) कहते हैं। परिणामी संख्या (हैश) मूल डेटा के लिए एक अद्वितीय पहचानकर्ता का काम करती है। आम तौर पर हमारे पास एक हैश फ़ंक्शन (hash function) होता है, जो प्रारंभिक डेटा को एक निश्चित आकार के डेटा (जैसे किसी संख्या) में बदल सकता है।
उदाहरण के लिए, Python में एक इनबिल्ट (built-in)
hash फ़ंक्शन है, जो किसी भी अपरिवर्तनीय (immutable) ऑब्जेक्ट को, आम तौर पर रेंज के भीतर आने वाली किसी संख्या में बदल सकता है। ध्यान रहे, यह सिर्फ़ अपरिवर्तनीय ऑब्जेक्ट्स पर काम कर सकता है। इसलिए, किसी लिस्ट या डिक्शनरी (जो परिवर्तनीय यानी mutable होते हैं) को हैश करने की कोशिश करने पर निम्न त्रुटि आती है:print(hash(123)) # 123
print(hash('Anna')) # 2573300035916889866
print(hash('Bob')) # -2781086332262035333
print(hash((2, 'Simon'))) # -6551767300073204554
print(hash([1, 2])) # TypeError: unhashable type: 'list'चुनौती: दो पूर्णांकों का हैश बनाना
आइए एक कस्टम हैश फ़ंक्शन
h बनाएँ। यह फ़ंक्शन दो पूर्णांक लेगा और उनके लिए हैश मान लौटाएगा। इस फ़ंक्शन h को इस प्रकार परिभाषित किया गया है:इससे यह सुनिश्चित होगा कि हैश मान हमेशा [0; 5077) की सीमा में रहेगा।
इनपुट
इनपुट की एकमात्र पंक्ति में दो संख्याएँ
a और b ( ≤ a, b ≤ ) दी गई हैं।आउटपुट
प्रोग्राम को
(a, b) का हैश मान प्रदर्शित करना चाहिए।उदाहरण
Input | इनपुट |
4 5 | 2916 |
23452 5432 | 3751 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB