C++ এ ওপেন অ্যাড্রেসিং লিনিয়ার প্রোবিং সহ নিজস্ব হ্যাশ টেবিল বাস্তবায়ন করা

একটি হ্যাশ টেবিল হল একটি ডেটা স্ট্রাকচার যা কী-মান জোড়া সংরক্ষণ করতে ব্যবহৃত হয়। হ্যাশ ফাংশন হ্যাশ টেবিল দ্বারা একটি অ্যারেতে একটি সূচক গণনা করতে ব্যবহৃত হয় যেখানে একটি উপাদান সন্নিবেশ করা হবে বা অনুসন্ধান করা হবে৷

লিনিয়ার প্রোবিং হল ওপেন অ্যাড্রেসড হ্যাশ টেবিলে সংঘর্ষের সমাধান করার কৌশল। এই পদ্ধতিতে, একটি হ্যাশ টেবিলের প্রতিটি কক্ষ একটি একক কী-মান জোড়া সংরক্ষণ করে। হ্যাশ টেবিলের একটি ঘরে একটি নতুন কী ম্যাপ করার মাধ্যমে একটি সংঘর্ষ ঘটে যা ইতিমধ্যেই অন্য কী দ্বারা দখল করা হয়েছে। এই পদ্ধতিটি নিম্নোক্ত নিকটতম বিনামূল্যে অবস্থানের জন্য টেবিল অনুসন্ধান করে এবং সেখানে নতুন কী সন্নিবেশ করায়।

এটি লিনিয়ার প্রোবিং সহ হ্যাশ টেবিল বাস্তবায়নের জন্য একটি C++ প্রোগ্রাম।

অ্যালগরিদম

 শুরু করুন ঘোষণা ফাংশন সন্নিবেশ (int k, int v) পূর্ণসংখ্যা পয়েন্টারে hash_val, init, delindex ঘোষণা করুন। hash_val =HashFunc(k) initialize init =-1 intialize delindex =-1 যখন (hash_val !=init এবং (ht[hash_val] ==DelNode::getNode() বা ht[hash_val] !=NULL এবং ht[hash_val] ->k !=k)) if (init ==-1) init =hash_val if (ht[hash_val] ==DelNode::getNode()) delindex =hash_val hash_val =HashFunc(hash_val + 1) if (ht[hash_val] ] ==NULL বা hash_val ==init) if(delindex !=-1) ht[delindex] =new HashTable(k, v) অন্য ht[hash_val] =নতুন HashTable(k, v) if(init !=hash_val) if (ht[hash_val] !=DelNode::getNode()) if (ht[hash_val] !=NULL) if (ht[hash_val]->k==k) ht[hash_val]->v =v অন্য ht[ hash_val] =নতুন HashTable(k, v)End।

একটি মূল মান অনুসন্ধানের জন্য:

বিগিন ডিক্লেয়ার ফাংশন SearchKey(int k) হ্যাশ_ভাল ঘোষণা করুন, পূর্ণসংখ্যা ডেটাটাইপের ইনিট। hash_val =HashFunc(k) ইনিশিয়ালাইজ করুন init =-1 যখন (hash_val !=init এবং (ht[hash_val] ==DelNode::getNode() বা ht[hash_val] !=NULL এবং ht[hash_val]->k!=k if (init ==-1) init =hash_val hash_val =HashFunc(hash_val + 1) if (ht[hash_val] ==NULL বা hash_val ==init) রিটার্ন -1 অন্য ফেরত ht[hash_val]->vEnd. 

 মোছার জন্য: 
 
বিগিন ডিক্লেয়ার ফাংশন রিমুভ(int k) হ্যাশ_ভাল ঘোষণা করুন, ইন্টিজার ডেটাটাইপের ইনিট। hash_val =HashFunc(k) আরম্ভ করুন init =-1 যখন (hash_val !=init এবং (ht[hash_val] ==DelNode::getNode() বা ht[hash_val] !=NULL এবং ht[hash_val] ->k!=k)) if (init ==-1) init =hash_val hash_val =HashFunc(hash_val + 1) if (hash_val !=init এবং ht[hash_val] !=NULL) ht[hash_val] ht[hash_val] =DelNode::getNode()End.
 
উদাহরণ কোড
 
#include #include #include নেমস্পেস ব্যবহার করে std;const int T_S =5;class HashTable { public:int k; int v; হ্যাশটেবল(int k, int v) { this->k =k; this->v =v; }};ক্লাস ডেলনোড:পাবলিক হ্যাশটেবল { ব্যক্তিগত:স্ট্যাটিক ডেলনোড *en; DelNode():HashTable(-1, -1) {} সর্বজনীন:স্ট্যাটিক DelNode *getNode() { if (en ==NULL) en =new DelNode(); ফেরত en; }};DelNode *DelNode::en =NULL;class HashMapTable { ব্যক্তিগত:HashTable **ht; সর্বজনীন:HashMapTable() { ht =নতুন হ্যাশটেবল* [T_S]; জন্য (int i =0; i k !=k)) { if (init ==-1 ) init =hash_val; যদি (ht[hash_val] ==DelNode::getNode()) delindex =hash_val; hash_val =HashFunc(হ্যাশ_ভাল + 1); } if (ht[hash_val] ==NULL || hash_val ==init) { if(delindex !=-1) ht[delindex] =new HashTable(k, v); অন্য ht[hash_val] =নতুন HashTable(k, v); } if(init !=hash_val) { if (ht[hash_val] !=DelNode::getNode()) { if (ht[hash_val] !=NULL) { if (ht[hash_val]->k==k) ht [হ্যাশ_ভাল]->v =v; } } অন্য ht[hash_val] =নতুন হ্যাশটেবল(k, v); } } int SearchKey(int k) { int hash_val =HashFunc(k); int init =-1; যখন (hash_val !=init &&(ht[hash_val] ==DelNode::getNode() || ht[hash_val] !=NULL &&ht[hash_val]->k!=k)) { if (init ==-1 ) init =hash_val; hash_val =HashFunc(হ্যাশ_ভাল + 1); } if (ht[hash_val] ==NULL || hash_val ==init) রিটার্ন -1; অন্যথায় ht[hash_val]->v ফেরত দিন; } void সরান(int k) { int hash_val =HashFunc(k); int init =-1; যখন (hash_val !=init &&(ht[hash_val] ==DelNode::getNode() || ht[hash_val] !=NULL &&ht[hash_val]->k!=k)) { if (init ==-1 ) init =hash_val; hash_val =HashFunc(হ্যাশ_ভাল + 1); } যদি (hash_val !=init &&ht[hash_val] !=NULL) { মুছুন ht[hash_val]; ht[hash_val] =DelNode::getNode(); } } ~ HashMapTable() { delete[] ht; }};int main() { HashMapTable হ্যাশ; int k, v; int c; while(1) { cout<<"1. টেবিলে উপাদান সন্নিবেশ করান"<>c; switch(c) { কেস 1:cout<<"এলিমেন্ট ঢোকাতে হবে:"; cin>>v; cout<<"কোন উপাদানে সন্নিবেশ করা হবে তা লিখুন:"; cin>>k; hash.Insert(k, v); বিরতি কেস 2:cout<<"অনুসন্ধান করা উপাদানটির কী লিখুন:"; cin>>k; if(hash.SearchKey(k) ==-1) { cout<<"কীতে কোনো উপাদান পাওয়া যায়নি "<>k; hash.Remove(k); বিরতি কেস 4:প্রস্থান (1); ডিফল্ট:cout<<"\nসঠিক বিকল্প লিখুন\n"; } } রিটার্ন 0; }
 
আউটপুট
 
1.টেবিলে উপাদান ঢোকান2.কী থেকে উপাদান অনুসন্ধান করুন3.একটি কী-তে উপাদান মুছুন4.আপনার পছন্দের প্রস্থান করুন:1প্রবেশ করার উপাদানটি প্রবেশ করান:10কোন উপাদানে সন্নিবেশ করা হবে তা প্রবেশ করান:21.টেবিলে উপাদান ঢোকান2৷ কী থেকে উপাদান অনুসন্ধান করুন3.একটি কী-এ উপাদান মুছুন4.প্রস্থান করুন আপনার পছন্দের প্রবেশ করুন:1প্রবেশ করার জন্য উপাদানটি প্রবেশ করান:7কোন উপাদানটিতে কী প্রবেশ করানো হবে:61.টেবিলটিতে উপাদান সন্নিবেশ করান2.কী থেকে উপাদান অনুসন্ধান করুন3.একটি কী থেকে উপাদান মুছুন4 .প্রস্থান করুন আপনার পছন্দ লিখুন:1 সন্নিবেশ করার উপাদানটি প্রবেশ করান:4 কোন উপাদানটিতে সন্নিবেশ করা হবে তা প্রবেশ করান:51.টেবিলে উপাদান সন্নিবেশ করুন2.কী থেকে উপাদান অনুসন্ধান করুন3. একটি কী থেকে উপাদান মুছুন4.প্রস্থান করুন আপনার পছন্দটি প্রবেশ করুন:1প্রবেশ করাতে উপাদানটি প্রবেশ করান:12কোন উপাদানে ঢোকানো হবে তা লিখুন:31.টেবিলে উপাদান সন্নিবেশ করুন2.কী থেকে উপাদান অনুসন্ধান করুন3.একটি কী-এ উপাদান মুছুন4.প্রস্থান করুন আপনার পছন্দটি প্রবেশ করুন:15সঠিক বিকল্পটি প্রবেশ করান1.টেবিলে উপাদান সন্নিবেশ করুন2.কী থেকে উপাদান অনুসন্ধান করুন3.মুছুন একটি কী 4 এ উপাদান। আপনার পছন্দের প্রস্থান করুন:1 এন্টার উপাদান সন্নিবেশ করাতে হবে:15 কোন উপাদানটি সন্নিবেশ করা হবে তা লিখুন:81. সারণীতে উপাদান সন্নিবেশ করুন2. কী থেকে উপাদান অনুসন্ধান করুন3. একটি কী থেকে উপাদান মুছুন4. আপনার পছন্দের প্রস্থান করুন:2 অনুসন্ধান করা উপাদানটির কী প্রবেশ করান:6 কী-এ উপাদানটি প্রবেশ করান 6 :71.টেবিলে উপাদান ঢোকান2.কী থেকে উপাদান অনুসন্ধান করুন3.একটি কী থেকে উপাদান মুছুন4.আপনার পছন্দের প্রস্থান করুন:3মুছে ফেলার উপাদানটির কী প্রবেশ করান:21.টেবিলে উপাদান সন্নিবেশ করুন2.কী থেকে উপাদান অনুসন্ধান করুন3.মুছুন একটি কী-তে উপাদান4.প্রস্থান করুন আপনার পছন্দের উপাদানটি প্রবেশ করুন:2অনুসন্ধান করার জন্য উপাদানটির কী প্রবেশ করান:2কীতে কোনো উপাদান পাওয়া যায়নি 21.টেবিলে উপাদান সন্নিবেশ করান2.কী থেকে উপাদান অনুসন্ধান করুন3.একটি কী থেকে উপাদান মুছুন4.প্রস্থান করুন আপনার পছন্দটি লিখুন:4