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

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

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

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

অ্যালগরিদম

ঢোকানোর জন্য:

ফাংশন সন্নিবেশ ঘোষণা করা শুরু করুন ) বা 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] =নতুন HashTable(k, v) অন্য ht[hash_val] =নতুন HashTable(k, v) if(init !=hash_val) if (ht[hash_val] !=DelNode::getNode()) if (ht[hash_val] !=NULL) যদি (ht[hash_val]->k==k) ht[hash_val]->v =v অন্য ht[hash_val] =নতুন HashTable(k, v)End।

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

 শুরু করুন সার্চকি (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(hash_val + 1) যদি (ht[hash_val] ==NULL বা hash_val ==init) রিটার্ন - অন্য 1 ফেরত ht[hash_val]->vEnd.

মোছার জন্য:

 শুরু করুন ডিক্লেয়ার ফাংশন রিমুভ (int k) int hash_val =HashFunc(k) initialize 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 মুছুন [হ্যাশ_ভাল] 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; }

আউটপুট