हैश तालिका

इस ट्यूटोरियल में, आप सीखेंगे कि हैश टेबल क्या है। इसके अलावा, आपको C, C ++, जावा और पायथन में हैश टेबल संचालन के काम के उदाहरण मिलेंगे।

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

डेटा को कुंजी की जोड़ी में कुंजी की मदद से दर्शाया गया है जैसा कि नीचे दिए गए चित्र में दिखाया गया है। प्रत्येक डेटा एक कुंजी के साथ जुड़ा हुआ है। कुंजी एक पूर्णांक है जो डेटा को इंगित करता है।

1. डायरेक्ट एड्रेस टेबल

प्रत्यक्ष पता तालिका का उपयोग तब किया जाता है जब तालिका द्वारा उपयोग की जाने वाली जगह की मात्रा कार्यक्रम के लिए कोई समस्या नहीं है। यहाँ, हम यह मानते हैं

  • चाबियाँ छोटे पूर्णांक हैं
  • चाबियों की संख्या बहुत बड़ी नहीं है, और
  • कोई भी दो डेटा एक ही कुंजी नहीं है

पूर्णांक के एक पूल को ब्रह्मांड कहा जाता है U = (0, 1,… ., n-1)।
प्रत्यक्ष पता तालिका के प्रत्येक स्लॉट में T(0… n-1)उस तत्व का एक संकेतक होता है जो डेटा से मेल खाता है।
सरणी Tका सूचकांक स्वयं कुंजी है और सामग्री Tसेट के लिए एक संकेतक है (key, element)। यदि कुंजी के लिए कोई तत्व नहीं है, तो इसे छोड़ दिया जाता है NULL।

कभी-कभी, कुंजी ही डेटा है।

संचालन के लिए स्यूडोकोड

 directAddressSearch(T, k) return T(k) directAddressInsert(T, x) T(x.key) = x directAddressDelete(T, x) T(x.key) = NIL

एक डायरेक्ट एड्रेस टेबल की सीमाएं

  • कुंजी का मूल्य छोटा होना चाहिए।
  • कुंजियों की संख्या पर्याप्त रूप से छोटी होनी चाहिए ताकि यह किसी सरणी के आकार की सीमा को पार न करे।

2. हैश टेबल

एक हैश तालिका में, कुंजी को एक नया सूचकांक बनाने के लिए संसाधित किया जाता है जो आवश्यक तत्व के लिए मैप करता है। इस प्रक्रिया को हैशिंग कहते हैं।

आज्ञा h(x)देना एक हैश समारोह और kएक कुंजी हो।
h(k)गणना की जाती है और इसका उपयोग तत्व के लिए एक सूचकांक के रूप में किया जाता है।

एक हैश टेबल की सीमाएँ

  • यदि एक ही सूचकांक कई कुंजियों के लिए हैश फ़ंक्शन द्वारा निर्मित होता है, तो विरोध उत्पन्न होता है। इस स्थिति को टकराव कहा जाता है।
    इससे बचने के लिए, एक उपयुक्त हैश फ़ंक्शन चुना जाता है। लेकिन, सभी अद्वितीय कुंजियों का उत्पादन करना असंभव है क्योंकि |U|>m। इस प्रकार एक अच्छा हैश फ़ंक्शन टकराव को पूरी तरह से रोक नहीं सकता है लेकिन यह टकराव की संख्या को कम कर सकता है।

हालांकि, हमारे पास टकराव को हल करने के लिए अन्य तकनीकें हैं।

प्रत्यक्ष पता तालिका पर हैश तालिका के लाभ:

प्रत्यक्ष पता तालिका के साथ मुख्य मुद्दे सरणी के आकार और एक कुंजी के संभवतः बड़े मूल्य हैं। हैश फ़ंक्शन इंडेक्स की सीमा को कम कर देता है और इस प्रकार सरणी का आकार भी कम हो जाता है।
उदाहरण के लिए, यदि k = 9845648451321, तब h(k) = 11(कुछ हैश फ़ंक्शन का उपयोग करके)। यह 9845648451321एरे के इंडेक्स को प्रदान करते समय बर्बाद हुई मेमोरी को बचाने में मदद करता है

जंजीर से टकराव का संकल्प

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

यदि jकई तत्वों के लिए स्लॉट है, तो इसमें तत्वों की सूची के प्रमुख के लिए एक सूचक शामिल है। यदि कोई तत्व मौजूद नहीं है, तो jइसमें शामिल है NIL।

संचालन के लिए स्यूडोकोड

 chainedHashSearch(T, k) return T(h(k)) chainedHashInsert(T, x) T(h(x.key)) = x //insert at the head chainedHashDelete(T, x) T(h(x.key)) = NIL

पायथन, जावा, सी और सी ++ कार्यान्वयन

पायथन जावा सी सी ++ 
 # Python program to demonstrate working of HashTable hashTable = ((),) * 10 def checkPrime(n): if n == 1 or n == 0: return 0 for i in range(2, n//2): if n % i == 0: return 0 return 1 def getPrime(n): if n % 2 == 0: n = n + 1 while not checkPrime(n): n += 2 return n def hashFunction(key): capacity = getPrime(10) return key % capacity def insertData(key, data): index = hashFunction(key) hashTable(index) = (key, data) def removeData(key): index = hashFunction(key) hashTable(index) = 0 insertData(123, "apple") insertData(432, "mango") insertData(213, "banana") insertData(654, "guava") print(hashTable) removeData(123) print(hashTable) 
 // Java program to demonstrate working of HashTable import java.util.*; class HashTable ( public static void main(String args()) ( Hashtable ht = new Hashtable(); ht.put(123, 432); ht.put(12, 2345); ht.put(15, 5643); ht.put(3, 321); ht.remove(12); System.out.println(ht); ) ) 
 // Implementing hash table in C #include #include struct set ( int key; int data; ); struct set *array; int capacity = 10; int size = 0; int hashFunction(int key) ( return (key % capacity); ) int checkPrime(int n) ( int i; if (n == 1 || n == 0) ( return 0; ) for (i = 2; i < n / 2; i++) ( if (n % i == 0) ( return 0; ) ) return 1; ) int getPrime(int n) ( if (n % 2 == 0) ( n++; ) while (!checkPrime(n)) ( n += 2; ) return n; ) void init_array() ( capacity = getPrime(capacity); array = (struct set *)malloc(capacity * sizeof(struct set)); for (int i = 0; i < capacity; i++) ( array(i).key = 0; array(i).data = 0; ) ) void insert(int key, int data) ( int index = hashFunction(key); if (array(index).data == 0) ( array(index).key = key; array(index).data = data; size++; printf(" Key (%d) has been inserted ", key); ) else if (array(index).key == key) ( array(index).data = data; ) else ( printf(" Collision occured "); ) ) void remove_element(int key) ( int index = hashFunction(key); if (array(index).data == 0) ( printf(" This key does not exist "); ) else ( array(index).key = 0; array(index).data = 0; size--; printf(" Key (%d) has been removed ", key); ) ) void display() ( int i; for (i = 0; i < capacity; i++) ( if (array(i).data == 0) ( printf(" array(%d): / ", i); ) else ( printf(" key: %d array(%d): %d ", array(i).key, i, array(i).data); ) ) ) int size_of_hashtable() ( return size; ) int main() ( int choice, key, data, n; int c = 0; init_array(); do ( printf("1.Insert item in the Hash Table" "2.Remove item from the Hash Table" "3.Check the size of Hash Table" "4.Display a Hash Table" " Please enter your choice: "); scanf("%d", &choice); switch (choice) ( case 1: printf("Enter key -: "); scanf("%d", &key); printf("Enter data -: "); scanf("%d", &data); insert(key, data); break; case 2: printf("Enter the key to delete-:"); scanf("%d", &key); remove_element(key); break; case 3: n = size_of_hashtable(); printf("Size of Hash Table is-:%d", n); break; case 4: display(); break; default: printf("Invalid Input"); ) printf("Do you want to continue (press 1 for yes): "); scanf("%d", &c); ) while (c == 1); )
 // Implementing hash table in C++ #include #include using namespace std; class HashTable ( int capacity; list *table; public: HashTable(int V); void insertItem(int key, int data); void deleteItem(int key); int checkPrime(int n) ( int i; if (n == 1 || n == 0) ( return 0; ) for (i = 2; i  capacity = size; table = new list(capacity); ) void HashTable::insertItem(int key, int data) ( int index = hashFunction(key); table(index).push_back(data); ) void HashTable::deleteItem(int key) ( int index = hashFunction(key); list::iterator i; for (i = table(index).begin(); i != table(index).end(); i++) ( if (*i == key) break; ) if (i != table(index).end()) table(index).erase(i); ) void HashTable::displayHash() ( for (int i = 0; i < capacity; i++) ( cout << "table(" << i << ")"; for (auto x : table(i)) cout < " << x; cout << endl; ) ) int main() ( int key() = (231, 321, 212, 321, 433, 262); int data() = (123, 432, 523, 43, 423, 111); int size = sizeof(key) / sizeof(key(0)); HashTable h(size); for (int i = 0; i < n; i++) h.insertItem(key(i), data(i)); h.deleteItem(12); h.displayHash(); )

अच्छा हैश फंक्शंस

एक अच्छे हैश फ़ंक्शन की निम्नलिखित विशेषताएं हैं।

  1. यह उन कुंजियों को उत्पन्न नहीं करना चाहिए जो बहुत बड़ी हैं और बाल्टी का स्थान छोटा है। अंतरिक्ष बर्बाद हो गया है।
  2. उत्पन्न चाबियाँ न तो बहुत करीब होनी चाहिए और न ही बहुत दूर तक होनी चाहिए।
  3. टकराव को यथासंभव कम से कम किया जाना चाहिए।

हैशिंग के लिए उपयोग की जाने वाली कुछ विधियाँ हैं:

प्रभाग विधि

यदि kएक कुंजी है और mहैश तालिका का आकार है, तो हैश फ़ंक्शन h()की गणना इस प्रकार की जाती है:

h(k) = k mod m

उदाहरण के लिए, यदि हैश तालिका का आकार है 10और k = 112फिर h(k) = 112मॉड है 10 = 2। का मान mहोना आवश्यक नहीं है 2। ऐसा इसलिए है क्योंकि 2द्विआधारी प्रारूप की शक्तियां हैं 10, 100, 1000,… । जब हम पाते हैं k mod m, हम हमेशा निचले क्रम के पी-बिट प्राप्त करेंगे।

 यदि m = 22, k = 17, तो h (k) = 17 mod 22 = 10001 mod 100 = 01 यदि m = 23, k = 17, तो h (k) = 17 mod 22 = 10001 mod 100 = 001 यदि m = 24, k = 17, तब h (k) = 17 mod 22 = 10001 mod 100 = 0001 यदि m = 2p, तो h (k) = p कम बिट्स m

गुणन विधि

h(k) = ⌊m(kA mod 1)⌋
कहां है,

  • kA mod 1आंशिक भाग देता है kA,
  • ⌊ ⌋ मंजिल मूल्य देता है
  • Aकोई स्थिर है नूथ द्वारा A0 और 1 के बीच झूठ का मूल्य , एक इष्टतम विकल्प ≈ (√5-1)/2सुझाया जाएगा ।

यूनिवर्सल हैशिंग

यूनिवर्सल हैशिंग में हैश फ़ंक्शन को यादृच्छिक स्वतंत्र रूप से कुंजी के लिए चुना जाता है।

खुला पता

एक सामान्य हैश तालिका में एकल स्लॉट में एकाधिक मान संग्रहीत किए जा सकते हैं।

खुले पते का उपयोग करके, प्रत्येक स्लॉट को या तो एक कुंजी से भर दिया जाता है या छोड़ दिया जाता है NIL। सभी तत्व हैश तालिका में ही संग्रहीत हैं।

जंजीर के विपरीत, कई तत्वों को एक ही स्लॉट में फिट नहीं किया जा सकता है।

ओपन एड्रेसिंग मूल रूप से एक टकराने वाली तकनीक है। खुले पते द्वारा उपयोग की जाने वाली कुछ विधियाँ हैं:

रैखिक जांच

रैखिक जांच में, टकराव अगले स्लॉट की जाँच करके हल किया जाता है।
h(k, i) = (h'(k) + i) mod m
कहां है,

  • i = (0, 1,… .)
  • h'(k) एक नया हैश फ़ंक्शन है

यदि कोई टक्कर होती है h(k, 0), तो h(k, 1)जाँच की जाती है। इस तरह, का मूल्य iरैखिक रूप से बढ़ाया जाता है।
रैखिक जांच के साथ समस्या यह है कि आसन्न स्लॉट का एक क्लस्टर भरा हुआ है। नया तत्व सम्मिलित करते समय, पूरे क्लस्टर का पता लगाया जाना चाहिए। यह हैश तालिका पर संचालन करने के लिए आवश्यक समय को जोड़ता है।

द्विघात जांच

द्विघात जांच में, निम्नलिखित संबंध का उपयोग करके स्लॉट के बीच रिक्ति को बढ़ाया जाता है (एक से अधिक)। कहां है,
h(k, i) = (h'(k) + c1i + c2i2) mod m

  • c1और सकारात्मक सहायक स्थिरांक हैं,c2
  • i = (0, 1,… .)

डबल हैशिंग

यदि हैश फ़ंक्शन को लागू करने के बाद टकराव होता है h(k), तो अगले स्लॉट को खोजने के लिए एक और हैश फ़ंक्शन की गणना की जाती है।
h(k, i) = (h1(k) + ih2(k)) mod m

हैश टेबल एप्लीकेशन

हैश टेबल को जहां लागू किया जाता है

  • निरंतर समय की खोज और सम्मिलन की आवश्यकता है
  • क्रिप्टोग्राफ़िक अनुप्रयोग
  • अनुक्रमण डेटा की आवश्यकता है

दिलचस्प लेख...