“हालांकि अधिकांश लोग प्रोग्रामिंग में सीधे तौर पर शामिल नहीं होंगे, लेकिन सभी लोग कंप्यूटरों से प्रभावित होते हैं, इसलिए एक शिक्षित व्यक्ति को यह समझना चाहिए कि कंप्यूटर हार्डवेयर, सॉफ्टवेयर और नेटवर्क कैसे काम करते हैं।”

$\quad$ — ब्रायन केर्निघन

6.1 परिचय

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

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

6.2 रैखिक खोज

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

$\mathrm{n}$ तत्वों की एक सूची numList और कुंजी मान K दिए गए हैं, एल्गोरिदम 6.1 एक रैखिक खोज एल्गोरिदम का उपयोग करता है ताकि numList में कुंजी K की स्थिति खोज सके।

एल्गोरिदम 6.1: रैखिक खोज

LinearSearch(numList, key, n)
चरण 1: SET index = 0
चरण 2: WHILE index < n, REPEAT Step 3
चरण 3: IF numlist[index]= key THEN
$\qquad$ PRINT “Element found at position”, index+1
$\qquad$ STOP
$\quad$ ELSE
$\qquad$ index = index+1
चरण 4: PRINT “Search unsuccessful”

गतिविधि 6.1

15 तत्वों की एक सूची पर विचार करें: L=[2,3,9,7, 6,11,12,17,45,23,29 31,-37,41,43]। यह निर्धारित करें कि लीनियर सर्च key = 1 को खोजने के लिए कितनी तुलनाएँ करता है

उदाहरण 6.1 मान लीजिए numList में सात तत्व हैं $[8,-4,7,17,0,2,19]$ इसलिए, $n=7$। हमें numList में कुंजी, मान लीजिए 17 को खोजना है। तालिका 6.1 दी गई सूची में तत्वों को उनके सूचकांक मानों के साथ दिखाती है।

तालिका 6.1 numList में तत्व सूचकांक मानों के साथ

एल्गोरिदम 6.1 का उपयोग करके लीनियर सर्च की चरणबद्ध प्रक्रिया तालिका 6.2 में दी गई है।

तालिका 6.2 तालिका 6.1 के numList में कुंजी 17 के लिए लीनियर सर्च

ध्यान दें कि चार तुलनाओं के बाद, एल्गोरिदम ने कुंजी 17 को खोज लिया और ‘Element found at position 4’ प्रदर्शित करेगा।

अब हम numList में तत्वों की एक और व्यवस्था मान लेते हैं $[17,8,-4,7,0,2,19]$ और numList में कुंजी $\mathrm{K}=17$ को खोजते हैं।

तालिका 6.3 numList में तत्व सूचकांक मानों के साथ

तालिका 6.4 तालिका 6.3 में दी गई numList में कुंजी 17 के लिए रैखिक खोज

तालिका 6.4 से स्पष्ट है कि ‘अवयव स्थिति 1 पर मिला’ प्रदर्शित करने के लिए एल्गोरिथ्म को केवल 1 तुलना करनी पड़ी। इस प्रकार, यदि खोजी जाने वाली कुंजी सूची का पहला अवयव है, तो रैखिक खोज एल्गोरिथ्म को हमेशा केवल 1 तुलना करनी पड़ेगी। यह न्यूनतम कार्य है जो रैखिक खोज एल्गोरिथ्म को करना पड़ेगा।

गतिविधि 6.2

सूची में : $\mathrm{L}=[7,-1$, $11,32,17,19,23,29,31$, 37,43]

यह निर्धारित करें कि कुंजी $=43$ खोजने के लिए रैखिक खोज कितनी तुलनाएँ करती है।

अब मान लीजिए numList में अवयवों की एक अन्य व्यवस्था है $[8,-4,7,0,2,19,17]$ और numList में कुंजी $\mathrm{K}=17$ खोजते हैं।

एक ड्राय रन पर, हम पता लगा सकते हैं कि लीनियर सर्च एल्गोरिद्म को ‘Element found at position 7’ दिखाने के लिए सूची के प्रत्येक तत्व की तुलना अंत तक करनी पड़ती है। इस प्रकार, यदि खोजा जाने वाला कुंजी सूची का अंतिम तत्व है, तो लीनियर सर्च एल्गोरिद्म को $\mathrm{n}$ तुलनाएँ करनी होंगी, जहाँ $\mathrm{n}$ सूची में तत्वों की संख्या है। यह वास्तव में अधिकतम कार्य है जो लीनियर सर्च एल्गोरिद्म को करना पड़ेगा।

आइए अब एक अन्य स्थिति मान लें, जहाँ खोजी जा रही कुंजी सूची में मौजूद नहीं है। उदाहरण के लिए, हम numList में कुंजी $=10$ खोज रहे हैं।

इस स्थिति में भी, एल्गोरिद्म को ‘Element is not found in the list’ दिखाने के लिए सूची के प्रत्येक तत्व की तुलना अंत तक करनी पड़ती है। इस प्रकार, यदि कुंजी सूची में मौजूद नहीं है, तो लीनियर सर्च एल्गोरिद्म को $\mathrm{n}$ तुलनाएँ करनी होंगी। यह फिर से एक ऐसी स्थिति है जहाँ अधिकतम कार्य किया जाता है। आइए अब लीनियर सर्च के प्रोग्राम को समझें। यह एक सूची के तत्वों और खोजी जाने वाली कुंजी को इनपुट के रूप में लेता है और या तो सूची में तत्व की स्थिति लौटाता है या दिखाता है कि कुंजी सूची में मौजूद नहीं है।

प्रोग्राम 6-1 लीनियर सर्च

def linearSearch(list, key): $\quad$ #फंक्शन सर्च करने के लिए
$\quad$ for index in range(0,len(list)):
$\qquad$ if list[index] == key: $\quad$ #कुंजी मौजूद है
$\hspace{1cm}$ return index+1 $\quad$ #सूची में कुंजी की स्थिति
$\quad$ return None $\quad$ #कुंजी सूची में नहीं है
#फंक्शन का अंत

list1 = [] $\quad$ #एक खाली सूची बनाएँ
maximum = int(input(“आपकी सूची में कितने तत्व हैं? “))
print(“प्रत्येक तत्व दर्ज करें और एंटर दबाएँ: “)
for i in range(0,maximum):
$\quad$ n = int(input())
$\quad$ list1.append(n) $\quad$ #सूची में तत्व जोड़ें
print(“सूची की सामग्री है:”, list1)

key = int(input(“खोजा जाने वाला नंबर दर्ज करें:”))
position = linearSearch(list1, key)
if position is None:
$\quad$ print(“नंबर”,key,“सूची में मौजूद नहीं है”)
else:
$\quad$ print(“नंबर”,key,“स्थिति”,position,“पर मौजूद है”)

आउटपुट

आपकी सूची में कितने तत्व हैं? 4
प्रत्येक तत्व दर्ज करें और एंटर दबाएँ:
12
23
3
-45
सूची की सामग्री है: [12, 23, 3, -45]
खोजा जाने वाला नंबर दर्ज करें:23
नंबर 23 स्थिति 2 पर मौजूद है

6.3 बाइनरी खोज

एक परिदृश्य पर विचार करें जहाँ हमें एक अंग्रेज़ी शब्दकोश में Zoology शब्द का अर्थ खोजना है। हम शब्दकोश में इसे कहाँ खोजेंगे?

1. पहले आधे में?
2. लगभग बीच में?
3. दूसरे आधे में?

निश्चित रूप से शब्दकोश के दूसरे आधे में शब्द को खोजना अधिक समझदारी है क्योंकि शब्द वर्णमाला ’ $Z$ ’ से शुरू होता है। दूसरी ओर, अगर हमें Biology शब्द का अर्थ खोजना होता, तो हम शब्दकोश के पहले आधे में खोजते।

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

बाइनरी खोज एक खोज तकनीक है जो सूची में तत्वों की क्रमबद्धता का उपयोग करते हुए किसी कुंजी को शीघ्रता से खोजती है। संख्यात्मक मानों के लिए, सूची के तत्वों को उनकी कुंजी मानों के आरोही या अवरोही क्रम में व्यवस्थित किया जा सकता है। पाठ्य आंकड़ों के लिए, इसे a से $z$ या $z$ से a तक वर्णानुक्रम में व्यवस्थित किया जा सकता है।

बाइनरी खोज में, जिस कुंजी को खोजना है उसकी तुलना क्रमबद्ध सूची के मध्य तत्व से की जाती है। इससे तीन संभावनाओं में से कोई एक परिणाम हो सकता है:

i) मध्य स्थिति का तत्व स्वयं कुंजी से मेल खाता है या

ii) मध्य स्थिति का तत्व कुंजी से बड़ा है या

iii) मध्य स्थिति का तत्व कुंजी से छोटा है

यदि मध्य स्थिति का तत्व कुंजी से मेल खाता है, तो हम खोज को सफल घोषित करते हैं और खोज प्रक्रिया समाप्त हो जाती है।

हम द्विआधारी खोज (binary search) में तुलना (comparison) की बजाय पुनरावृत्ति (iteration) शब्द का प्रयोग कर रहे हैं, क्योंकि हर असफल तुलना के बाद हम खोज क्षेत्र बदलते हैं और आगे की तुलनाएँ करने से पहले प्रथम, मध्य और अंतिम स्थान को पुनः परिभाषित करते हैं।

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

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

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

यदि खोजी जाने वाली सूची में सम संख्या में तत्व हैं, तो मध्य मान (mid) को फ़्लोर डिवीज़न (//) ऑपरेटर का उपयोग करके गणना की जाती है। यदि सूची में 10 तत्व हैं, तो मध्य स्थिति (mid) $=10 / / 2=5$ होगी। इसलिए, सूची में छठा तत्व मध्य तत्व माना जाता है क्योंकि हम जानते हैं कि सूची में पहले तत्व की सूचकांक मान 0 होती है। यदि आवश्यक हो, तो सूची को दो भागों में विभाजित किया जाता है जहाँ पहला भाग 5 तत्वों को और दूसरा भाग 4 तत्वों को समाहित करता है।

गतिविधि 6.3

numList [17,8,-4,7,0,2, 19] पर विचार करें। इसे Python की Lists के sort() फ़ंक्शन का उपयोग करके क्रमबद्ध करें। अब कुंजी 7 को खोजने के लिए बाइनरी सर्च लागू करें। आवश्यक पुनरावृत्तियों की संख्या निर्धारित करें।

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

$\mathrm{n}$ तत्वों की एक सूची numList और कुंजी मान $\mathrm{K}$ दी गई है, एल्गोरिद्म 6.2 बाइनरी सर्च एल्गोरिद्म का उपयोग करके numList में कुंजी $\mathrm{K}$ की स्थिति खोजने के लिए चरण दिखाता है।

गतिविधि 6.4

एक सूची [-4,0, 2, 7, 8, 17, 19] पर विचार करें। तत्व -4 खोजने के लिए द्विआधारी खोज लागू करें। आवश्यक कुंजी तुलनाओं की संख्या निर्धारित करें।

एल्गोरिदम 6.2: द्विआधारी खोज

BinarySearch(numList, key)
चरण 1: SET first = 0, last = n-1
चरण 2: Calculate mid = (first+last)//2
चरण 3: WHILE first <= last REPEAT Step 4
चरण 4: IF numList[mid] = key
$\qquad$ PRINT “Element found at position”,
$\qquad$ " mid+1
$\qquad$ STOP
$\quad$ ELSE
$\qquad$ IF numList[mid] > key, THEN last
$\qquad$ = mid-1
$\qquad$ ELSE first = mid + 1
चरण 5: PRINT “Search unsuccessful”

द्विआधारी खोज एल्गोरिदम सूची को नहीं बदलता है। बल्कि, एल्गोरिदम के प्रत्येक पास के बाद, खोज क्षेत्र आधा हो जाता है। अर्थात्, प्रत्येक पुनरावृत्ति में कुंजी से तुलना करने वाले तत्व का सूचकांक ही बदलता है।

उदाहरण 6.2 15 तत्वों वाली एक क्रमबद्ध सूची पर विचार करें: numList $=[2,3,5,7,10,11,12,17,19,23,29,31,3$ $7,41,43]$

हमें numList में कुंजी, मान लीजिए 17 खोजनी है। numList में पहचाने गए पहले, मध्य और अंतिम तत्व उनके सूचकांक मानों के साथ तालिका 6.5 में दिखाए गए हैं।

तालिका 6.5 क्रमबद्ध numList में तत्व उनके सूचकांक मान के साथ

Table 6.6 Algorithm 6.2 में दिए गए चरणों का उपयोग करके बाइनरी खोज का कार्य।

ध्यान दें कि एल्गोरिदम को ‘Element found at position 8’ प्रदर्शित करने के लिए केवल 1 पुनरावृत्ति करनी पड़ी। ऐसा इसलिए है क्योंकि खोजा जा रहा कुंजी सूची का मध्य तत्व है। इस प्रकार, जब खोजी जाने वाली कुंजी सूची में मध्य मान होती है, तो बाइनरी खोज को केवल 1 पुनरावृत्ति की आवश्यकता होती है। यह वह न्यूनतम कार्य है जो बाइनरी खोज को यह पुष्टि करने के लिए करना होगा कि कोई कुंजी सूची में मौजूद है।

अब आइए सूची में कुंजी 2 खोजें। numList $=[2,3,5,7,10,11,12,17,19,23,29,3$ $1,37,41,43]$

गतिविधि 6.5

$\mathrm{L}=[2,3,5,7,10,1$ $1,12,17,19,23,29,31$, $37,41,43]$ के लिए। दी गई कुंजी मानों $2,43,17$ और 9 के लिए तालिका 6.8 को भरें। तालिका 6.8 से आप दोनों एल्गोरिद्मों के प्रदर्शन के बारे में विभिन्न स्थितियों में क्या निष्कर्ष निकालते हैं?

पहली पुनरावृत्ति में, हमारे पास मध्य मान 17 है। चूँकि 2 मध्य मान (17) से छोटा है, हमें दूसरी पुनरावृत्ति में सूची के पहले आधे भाग में खोज करनी होगी। अब हम केवल 7 तत्वों पर विचार करते हैं। चूँकि 2 नए मध्य मान (7) से छोटा है, हमें तीसरी पुनरावृत्ति में शेष सूची के पहले आधे भाग में खोज करनी होगी। अब हम केवल 3 तत्वों पर विचार करते हैं। ध्यान दें कि numList में तत्वों की संख्या हर बार आधी हो जाती है। यह पुनरावृत्ति 1 में 15 तत्वों से घटकर पुनरावृत्ति 2 में 7 तत्वों और पुनरावृत्ति 3 में 3 तत्वों हो जाती है। तीसरी पुनरावृत्ति में, एल्गोरिद्म पाता है कि कुंजी 2 नए मध्य मान (3) से छोटी है, हमें शेष सूची के पहले आधे भाग में खोज करनी होगी। सूची में अब चौथी पुनरावृत्ति में केवल 1 तत्व है और तुलना पर पाया जाता है कि तत्व कुंजी के समान है। इस प्रकार, खोज सफलतापूर्वक समाप्त होती है और कुंजी की स्थिति लौटाती है। बाइनरी खोज के लिए अनुसरण किए गए चरण तालिका 6.7 में दिए गए हैं।

तालिका 6.7 numList में बाइनरी खोज का उपयोग करके कुंजी $=2$ की खोज

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

प्रोग्राम 6-2 बाइनरी खोज

def binarySearch(list, key):
$\quad$ first = 0
$\quad$ last = len(list) - 1
$\quad$ while(first <= last):
$\qquad$ mid = (first + last)//2
$\qquad$ if list[mid] == key:
$\hspace{1cm}$ return mid
$\qquad$ elif key > list[mid]:
$\hspace{1cm}$ first = mid + 1
$\qquad$ elif key < list[mid]:
$\hspace{1cm}$ last = mid - 1
$\quad$ return -1

_list1 = [] $\quad$ #एक खाली सूची बनाएँ
print (“आरोही क्रम में तत्व दर्ज करके एक सूची बनाएँ”)
print (“प्रत्येक तत्व के बाद एंटर दबाएँ, रोकने के लिए -999 दबाएँ”)
num = int(input())
while num!=-999:
$\quad$ list1.append(num)
$\quad$ num = int(input())
n = int(input(“खोजने के लिए कुंजी दर्ज करें: “))
pos = binarySearch(list1,n)
if(pos != -1):
$\quad$ print( n,“स्थिति पर मिला”, pos+1)
else:
$\quad$ print (n,“सूची में नहीं मिला”)

आउटपुट

आरोही क्रम में तत्व दर्ज करके एक सूची बनाएँ
प्रत्येक तत्व के बाद एंटर दबाएँ, रोकने के लिए -999 दबाएँ
1
3
4
5
-999
खोजने के लिए संख्या दर्ज करें: 4
4 स्थिति 3 पर मिला

प्रोग्राम का दूसरा रन भिन्न डेटा के साथ:
आरोही क्रम में तत्व दर्ज करके एक सूची बनाएँ
प्रत्येक तत्व के बाद एंटर दबाएँ, रोकने के लिए -999 दबाएँ
12
8
3
-999
खोजने के लिए संख्या दर्ज करें: 4
4 सूची में नहीं मिला

6.3.1 बाइनरी खोज के अनुप्रयोग

• बाइनरी खोज के असंख्य अनुप्रयोग हैं – शब्दकोश या टेलीफोन निर्देशिका में खोजना, किसी सॉर्टेड सूची में न्यूनतम या अधिकतम मान वाला तत्व खोजना आदि।
• संशोधित बाइनरी खोज तकनीकों की व्यापक अनुप्रयोग हैं जैसे डेटाबेस में अनुक्रमण, राउटर में रूटिंग टेबल लागू करना, डेटा संपीड़न कोड आदि।

6.4 हैशिंग द्वारा खोज

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

सोचिए और विचार कीजिए

मान लीजिए एक सूची में एक से अधिक ऐसे तत्व हैं जिनके मॉडulo विभाजन से एक ही शेषफल मान प्राप्त होता है। ऐसी स्थितियों में, किस प्रकार की हैशिंग उपयोगी हो सकती है?

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

एक सरल हैश फ़ंक्शन जो संख्यात्मक मानों के साथ काम करता है, उसे शेष विधि कहा जाता है। यह सूची से कोई तत्व लेता है और उसे हैश तालिका के आकार से विभाजित करता है। इससे उत्पन्न होने वाला शेषफल ही हैश मान कहलाता है।

h(element) = element % size(hash table)

हम आसानी से पायथन की सूची का उपयोग करके एक हैश तालिका लागू कर सकते हैं। आइए एक खाली हैश तालिका पर विचार करें जिसमें 10 स्थान हैं, जैसा कि तालिका 6.8 में दिखाया गया है:

तालिका 6.8 10 स्थानों वाली एक खाली हैश तालिका

आइए संख्याओं की एक सूची (34,16,2,93,80,77,51) पर विचार करें। हम पहले समझाए गए हैश फ़ंक्शन शेष विधि का उपयोग करके टेबल 6.9 में दिखाए अनुसार एक हैश तालिका बना सकते हैं।

टेबल 6.9 सूची के तत्वों पर लागू किया गया हैश फ़ंक्शन तत्व $% 10$

हैश मानों की गणना करने के बाद, प्रत्येक तत्व को टेबल 6.10 में दिखाई गई हैश तालिका में उसके निर्धारित स्थान पर डाला जाता है।

टेबल 6.10 टेबल 6.10 में दिए गए तत्वों के लिए उत्पन्न हैश तालिका}

अब, किसी कुंजी को खोजने के लिए, ह hashing फ़ंक्शन का उपयोग करके उसका सूचकांक गणना कर सकते हैं और उस सूचकांक पर मौजूद तत्व की तुलना कुंजी से करके यह घोषित कर सकते हैं कि तत्व सूची में मौजूद है या नहीं। यह खोज संक्रिया केवल एक तुलना शामिल करती है और इसलिए सूची के आकार की परवाह किए बिना किसी कुंजी को खोजने के लिए हमेशा समान समय की आवश्यकता होती है।

प्रोग्राम 6-3 दी गई सूची L में किसी कुंजी को खोजने के लिए हैशिंग का उपयोग

#Function to check if a key is present or not
def hashFind(key,hashTable):
$\quad$ if (hashTable[key % 10] == key): $\quad$ #key is present
$\qquad$ return ((key % 10)+1) $\quad$ #return the position
$\quad$ else:
$\qquad$ return None #key is not present
#end of function

#create hashTable with 10 empty positions
hashTable=[None, None, None, None, None, None, None, None, None, None]
print(“We have created a hashTable of 10 positions:”)
print(hashTable)

L = [34, 16, 2, 93, 80, 77, 51]
print(“The given list is”, L[::] )

#Apply hash function
for i in range(0,len(L)):
$\quad$ hashTable[L[i]%10] = L[i]
print(“The hash table contents are: " )
for i in range(0,len(hashTable)):
$\quad$ print(“hashindex=”, i,” , value =”, hashTable[i])

key = int(input(“Enter the number to be searched:”))

position = hashFind(key,hashTable)
if position is None:
$\quad$ print(“Number”,key,“is not present in the hash table”)
else:
$\quad$ print(“Number “,key,” present at “,position, " position”)

आउटपुट:

हमने 10 स्थानों की एक hashTable बनाई है:
[None, None, None, None, None, None, None, None, None, None]
दी गई सूची है [34, 16, 2, 93, 80, 77, 51]
हैश टेबल की सामग्री है:
hashindex= 0 , value = 80
hashindex= 1 , value = 51
hashindex= 2 , value = 2
hashindex= 3 , value = 93
hashindex= 4 , value = 34
hashindex= 5 , value = None
hashindex= 6 , value = 16
hashindex= 7 , value = 77
hashindex= 8 , value = None
hashindex= 9 , value = None
खोजे जाने वाले नंबर को दर्ज करें:16
संख्या 16 स्थान 7 पर मौजूद है_

6.4.1 टक्कर (COLLISION)

हैशिंग तकनीक तब तक ठीक काम करती है जब सूची का प्रत्येक अवयव हैश टेबल में किसी अद्वितीय स्थान पर मैप होता है। एक सूची $[34,16,2,26,80]$ पर विचार करें। हैश फ़ंक्शन, मान लीजिए list[i]%10, लगाते समय दो अवयव (16 और 26) का हैश मान 6 आएगा। यह एक समस्यात्मक स्थिति है, क्योंकि हमारी परिभाषा के अनुसार दो या अधिक अवयव सूची में एक ही स्थान पर नहीं हो सकते। इस स्थिति को हैशिंग में टक्कर (collision) कहा जाता है।

हमें एक तंत्र होना चाहिए जो समान हैश मान वाले अन्य आइटमों को हैश टेबल में रखे। इस प्रक्रिया को टक्कर समाधान (collision resolution) कहा जाता है। टक्कर को कई तरीकों से हल किया जा सकता है, लेकिन इस पुस्तक की सीमा के बाहर है टक्कर समाधान विधियों पर चर्चा करना।

यदि सूची का प्रत्येक आइटम हैश टेबल में किसी अद्वितीय सूचकांक पर मैप होता है, तो हैश फ़ंक्शन को एक पूर्ण हैश फ़ंक्शन (perfect hash function) कहा जाता है। यदि कोई हैश फ़ंक्शन पूर्ण है, तो टक्कर कभी नहीं होगी।

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

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

सारांश

• खोज का अर्थ है किसी विशेष तत्व को जिसे कुंजी कहा जाता है, तत्वों के संग्रह में ढूँढने का प्रयास करना। खोज यह निर्दिष्ट करती है कि वह कुंजी संग्रह में मौजूद है या नहीं। साथ ही, यदि कुंजी मौजूद है, तो यह दी गई संग्रह में उस कुंजी की स्थिति बताती है।
• रैखिक खोज सूची के तत्वों को एक-एक करके जाँचती है, कोई तत्व छोड़े बिना। यह उपयोगी होती है जब हमें किसी छोटी असorted सूची में कोई वस्तु खोजनी हो, लेकिन यह धीमी और समय लेने वाली होती है जब सूची में बड़ी संख्या में वस्तुएँ हों। सूची को खोजने में लगा समय सूची के आकार के साथ बढ़ता है।
• द्विआधारी खोज एक sorted/क्रमबद्ध सूची लेती है और उसे बीच से विभाजित करती है। फिर वह मध्य तत्व की तुलना खोजी जाने वाली कुंजी से करती है। यदि मध्य तत्व कुंजी से मेल खाता है, तो खोज को सफल घोषित किया जाता है और प्रोग्राम समाप्त होता है। यदि मध्य तत्व कुंजी से बड़ा है, तो खोज सूची के पहले आधे भाग में दोहराई जाती है। यदि मध्य तत्व कुंजी से छोटा है, तो खोज सूची के दूसरे आधे भाग में दोहराई जाती है।

यह विभाजन और सूची के आकार में कमी तब तक जारी रहती है जब तक कुंजी न मिल जाए या शेष सूची में केवल एक ही वस्तु बची रहे।

• बाइनरी सर्च में, वे तुलनाएँ जो कुंजी नहीं ढूँढ़ पातीं, फिर भी हमें यह अनुमान देती हैं कि कुंजी शायद कहाँ मिल सकती है! वे बताती हैं कि कुंजी सूची के वर्तमान मध्य स्थान से पहले है या बाद में, और हम इस जानकारी का उपयोग करके अपनी खोज को संकीर्ण या कम कर सकते हैं।
• हैश आधारित खोज में केवल एक कुंजी तुलना की आवश्यकता होती है ताकि किसी कुंजी की उपस्थिति या अनुपस्थिति का पता लगाया जा सके, बशर्ते प्रत्येक अवयव अपने निर्धारित स्थान पर हो जो एक हैश फंक्शन द्वारा तय किया गया हो। यह सूची में कुंजी का स्थान एक सूत्र जिसे हैश फंक्शन कहा जाता है और स्वयं कुंजी का उपयोग करके गणना करता है।
• जब दो अवयव हैश तालिका में एक ही स्लॉट पर मैप होते हैं, तो इसे टक्कर (collision) कहा जाता है।
• टक्कर की स्थिति में हैश तालिका में दूसरे और आगे के आइटमों के लिए स्लॉट की पहचान करने की प्रक्रिया को टक्कर समाधान (collision resolution) कहा जाता है।
• एक परिपूर्ण हैश फंक्शन प्रत्येक इनपुट कुंजी को हैश तालिका में एक अद्वितीय सूचकांक पर मैप करता है। यदि हैश फंक्शन परिपूर्ण है, तो टक्करें कभी नहीं होंगी।

अभ्यास

1. रैखिक खोज का उपयोग करके सूची में 8, 1, 99 और 44 की स्थिति निर्धारित करें:

[1,-2,32,8,17,19,42,13,0,44]

एक विस्तृत सारणी बनाएँ जिसमें प्रत्येक पास में चर के मान और लिए गए निर्णय दिखाएँ।

2. रैखिक खोज प्रोग्राम का उपयोग करके उस सूची में मान 8 वाली कुंजी खोजें जिसमें दोहराव वाले मान हैं जैसे [42, -2,32,8,17,19,42,13,8,44]। कौन-सी स्थिति लौटाई गई? इसका क्या अर्थ है?

3. एक ऐसा प्रोग्राम लिखिए जो इनपुट के रूप में 10 धनात्मक और ऋणात्मक संख्याओं के मिश्रण वाली एक सूची और एक कुंजी मान लेता है।
कुंजी उपस्थित है या नहीं, यह जानने के लिए लीनियर सर्च लागू करें। यदि कुंजी सूची में मौजूद है तो यह सूची में कुंजी की स्थिति दिखाए अन्यथा एक उपयुक्त संदेश प्रिंट करे। कम से कम 3 अलग-अलग कुंजियों के लिए प्रोग्राम चलाएं और परिणाम नोट करें।

4. एक ऐसा प्रोग्राम लिखिए जो इनपुट के रूप में 10 पूर्णांकों की एक सूची और एक कुंजी मान लेता है और यह जानने के लिए बाइनरी सर्च लागू करता है कि कुंजी सूची में मौजूद है या नहीं। यदि कुंजी मौजूद है तो यह सूची में कुंजी की स्थिति दिखाए अन्यथा एक उपयुक्त संदेश प्रिंट करे। कम से कम 3 अलग-अलग कुंजी मानों के लिए प्रोग्राम चलाएं और परिणाम नोट करें।

5. निम्नलिखित एक अनर्गल/अक्रमित संख्याओं की सूची है:

[50,31,21,28,72,41,73,93,68,43,45,78, $5,17,97,71,69,61,88,75,99,44,55,9]

• सूची में 1, 5, 55 और 99 की स्थिति ज्ञात करने के लिए लीनियर सर्च का प्रयोग करें। साथ ही प्रत्येक संख्या को खोजने के लिए आवश्यक कुंजी तुलनाओं की संख्या भी नोट करें।
• सूची को आरोही क्रम में सॉर्ट/व्यवस्थित करने के लिए एक Python फ़ंक्शन का प्रयोग करें।
• पुनः, सूची में 1, 5, 55 और 99 की स्थिति ज्ञात करने के लिए लीनियर सर्च का प्रयोग करें और इन संख्याओं को खोजने के लिए आवश्यक कुंजी तुलनाओं की संख्या नोट करें।
• सॉर्ट की गई सूची में 1, 5, 55 और 99 की स्थिति ज्ञात करने के लिए बाइनरी सर्च का प्रयोग करें। प्रत्येक स्थिति में आवश्यक इटरेशनों की संख्या रिकॉर्ड करें।

6. एक कार्यक्रम लिखें जो निम्नलिखित अवर्गीकृत अंग्रेज़ी शब्दों की सूची को इनपुट के रूप में ले:

[Perfect, Stupendous, Wondrous, Gorgeous, Awesome, Mirthful, Fabulous, Splendid, Incredible, outstanding, Propitious, Remarkable, Stellar, Unbelievable, Super, Amazing].

• Amazing, Perfect, Great और Wondrous की सूची में स्थिति खोजने के लिए रैखिक खोज (linear search) का प्रयोग करें। साथ ही इन शब्दों को खोजने के लिए आवश्यक कुंजी तुलनाओं (key comparisons) की संख्या भी नोट करें।
• सूची को क्रमबद्ध करने के लिए एक Python फ़ंक्शन का प्रयोग करें।
• पुनः Amazing, Perfect, Great और Wondrous की स्थिति ज्ञात करने के लिए रैखिक खोज का प्रयोग करें और इन शब्दों को खोजने के लिए आवश्यक कुंजी तुलनाओं की संख्या नोट करें।
• क्रमबद्ध सूची में Amazing, Perfect, Great और Wondrous की स्थिति ज्ञात करने के लिए द्विआधारी खोज (binary search) का प्रयोग करें। प्रत्येक स्थिति में आवश्यक पुनरावृत्तियों (iterations) की संख्या दर्ज करें।

7. अनुमान लगाएं कि यदि हमें 230 (1,073,741,824) रिकॉर्ड्स वाले क्रमबद्ध डेटाबेस में किसी व्यक्ति का विवरण खोजना है और खोजा जा रहा व्यक्ति डेटाबेस के मध्य स्थान पर स्थित है, तो द्विआधारी खोज और रैखिक खोज में कितनी कुंजी तुलनाओं की आवश्यकता होगी। आप अपने निष्कर्षों से क्या अर्थ निकालते हैं?

8. हैश फ़ंक्शन: h(element) = element % 11 का प्रयोग कर संख्याओं के संग्रह: [44,121,55$, $33,110,77,22,66] को एक हैश टेबल में संग्रहीत करें। बनाई गई हैश टेबल प्रदर्शित करें। जांचें कि क्या मान 11, 44, 88 और 121 हैश टेबल में मौजूद हैं और खोज परिणाम प्रदर्शित करें।

9. एक Python प्रोग्राम लिखिए जिसमें देशों और उनकी राजधानियों की सूची का मानचित्र इस प्रकार माना गया है:

CountryCapital= {‘India’:‘New Delhi’,‘UK’:‘London’,‘France’:‘Paris’,‘Switzerland’: ‘Berne’,‘Australia’: ‘Canberra’}

मान लीजिए कि हमारा हैश फ़ंक्शन देश के नाम की लंबाई है। उपयुक्त आकार की दो सूचियाँ लीजिए: एक कुंजियों (देश) के लिए और एक मानों (राजधानी) के लिए। एक तत्व को हैश टेबल में डालने के लिए, देश के अक्षरों की संख्या गिनकर उसका हैश कोड निकालिए, फिर कुंजी और मान को दोनों सूचियों में संगत इंडेक्स पर रखिए। उदाहरण के लिए, India का हैश कोड 5 है। इसलिए हम India को 5वें स्थान (इंडेक्स 4) पर कुंजियों की सूची में रखते हैं, और New Delhi को 5वें स्थान (इंडेक्स 4) पर मानों की सूची में रखते हैं, और इसी तरह। इससे हमें निम्न परिणाम मिलता है:

अब हैश टेबल में India, France और USA की राजधानी खोजिए और अपना परिणाम प्रदर्शित कीजिए।