হ্যাশ ফাংশন
এই বিভাগে, আমরা হ্যাশ ফাংশন সম্পর্কে আলোচনা করব যা নিম্নলিখিত ডেটা কাঠামোতে ডেটা আইটেমের সম্পর্কিত কী-এর হ্যাশ কোড কার্যকর করতে সাহায্য করে:
int হ্যাশআইটেম ( int চাবি ){
ফিরে চাবি % টেবিল আকার ;
}
একটি অ্যারের সূচক কার্যকর করার প্রক্রিয়াটিকে হ্যাশিং বলা হয়। কখনও কখনও, একই ধরনের কোড একই কী ব্যবহার করে একই সূচক তৈরি করতে কার্যকর করা হয় যাকে সংঘর্ষ বলা হয় যা বিভিন্ন চেইনিং (লিঙ্কযুক্ত তালিকা তৈরি) এবং ওপেন অ্যাড্রেসিং কৌশল বাস্তবায়নের মাধ্যমে পরিচালনা করা হয়।
C++ এ হ্যাশ টেবিলের কাজ
বাস্তব মান নির্দেশক হ্যাশ টেবিল রাখা হয়. এটি একটি অ্যারের সূচী অনুসন্ধান করতে একটি কী ব্যবহার করে যেখানে কীগুলির বিপরীতে মানগুলি একটি অ্যারেতে পছন্দসই অবস্থানে সংরক্ষণ করা প্রয়োজন। আমরা নিম্নলিখিত হিসাবে উল্লিখিত আকার 10 সহ হ্যাশ টেবিল নিয়েছি:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
আসুন আমরা এলোমেলোভাবে বিভিন্ন কীগুলির বিপরীতে যে কোনও ডেটা গ্রহণ করি এবং এই কীগুলিকে শুধুমাত্র সূচক গণনা করে একটি হ্যাশ টেবিলে সংরক্ষণ করি। সুতরাং, হ্যাশ ফাংশনের সাহায্যে গণনাকৃত সূচকে কীগুলির বিপরীতে ডেটা সংরক্ষণ করা হয়। ধরুন আমরা একটি ডেটা নিই = {14,25,42,55,63,84} এবং কী =[ 15,9,5,25,66,75]।
হ্যাশ ফাংশন ব্যবহার করে এই ডেটার সূচক গণনা করুন। সূচক মান নিম্নলিখিত উল্লেখ করা হয়:
| চাবি | পনের | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| সূচক গণনা করুন | 15%10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| ডেটা | 14 | 25 | 42 | 55 | 63 | 84 |
একটি অ্যারের সূচক তৈরি করার পরে, পূর্বে বর্ণিত অ্যারের সঠিক সূচকে কীটির বিপরীতে ডেটা রাখুন।
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
এর পরে, আমরা দেখতে পাচ্ছি যে দুটি বা ততোধিক কী একই হ্যাশ কোড থাকলে একটি সংঘর্ষ ঘটে যা অ্যারের উপাদানগুলির একই সূচকে পরিণত হয়। সংঘর্ষের সম্ভাবনা এড়াতে আমাদের কাছে একটি সমাধান রয়েছে: একটি ভাল হ্যাশ পদ্ধতি নির্বাচন করা এবং সঠিক কৌশলগুলি বাস্তবায়ন করা।
এখন, সঠিক উদাহরণের সাহায্যে বিভিন্ন বাস্তবায়ন কৌশল নিয়ে আলোচনা করা যাক।
উদাহরণ: একটি ওপেন হ্যাশিং টেকনিক ব্যবহার করে একটি হ্যাশ টেবিলে একটি ডেটা যোগ করুন
এই উদাহরণে, আমরা হ্যাশ টেবিলে সংঘর্ষ এড়াতে ওপেন হ্যাশিংয়ের মতো একটি বাস্তবায়ন কৌশল গ্রহণ করি। ওপেন হ্যাশিং বা চেইনিং-এ, আমরা হ্যাশ টেবিলের মান চেইন করার জন্য একটি লিঙ্কযুক্ত তালিকা তৈরি করি। এই উদাহরণের কোড স্নিপেট নিম্নলিখিতটিতে সংযুক্ত করা হয়েছে যা ওপেন হ্যাশিং কৌশল বর্ণনা করে:
# অন্তর্ভুক্ত করুন# অন্তর্ভুক্ত <তালিকা>
ক্লাস হ্যাশ টেবিল {
ব্যক্তিগত :
স্থির const int টেবিলের আকার = 10 ;
std :: তালিকা < int > টেবিল আছে [ টেবিলের আকার ] ;
int hashFunc ( int চাবি ) {
ফিরে চাবি % টেবিলের আকার ;
}
সর্বজনীন :
অকার্যকর সন্নিবেশ ( int চাবি ) {
int সূচক = hashFunc ( চাবি ) ;
টেবিল আছে [ সূচক ] . ফেরত পাঠাও ( চাবি ) ;
}
অকার্যকর ভিউ টেবিল ( ) {
জন্য ( int i = 0 ; i < টেবিলের আকার ; ++ i ) {
std :: cout << '[' << i << ']' ;
জন্য ( স্বয়ংক্রিয় এটা = টেবিল আছে [ i ] . শুরু ( ) ; এটা ! = টেবিল আছে [ i ] . শেষ ( ) ; ++ এটা ) {
std :: cout << ' -> ' << * এটা ;
}
std :: cout << std :: endl ;
}
}
} ;
int প্রধান ( ) {
HashTable hasTable ;
আছে টেবিল। সন্নিবেশ ( পনের ) ;
আছে টেবিল। সন্নিবেশ ( 33 ) ;
আছে টেবিল। সন্নিবেশ ( 23 ) ;
আছে টেবিল। সন্নিবেশ ( 65 ) ;
আছে টেবিল। সন্নিবেশ ( 3 ) ;
আছে টেবিল। ভিউ টেবিল ( ) ;
ফিরে 0 ;
}
এটি একটি খুব আকর্ষণীয় উদাহরণ: আমরা একটি লিঙ্কযুক্ত তালিকা তৈরি করি এবং হ্যাশ টেবিলে ডেটা সন্নিবেশ করি। প্রথমত, আমরা প্রোগ্রামের শুরুতে লাইব্রেরি সংজ্ঞায়িত করি। দ্য < তালিকা > লাইব্রেরি লিঙ্ক তালিকা বাস্তবায়নের জন্য ব্যবহৃত হয়। এর পরে, আমরা 'হ্যাশটেবল' নামে একটি ক্লাস তৈরি করি এবং 'প্রাইভেট:' কীওয়ার্ড ব্যবহার করে টেবিলের আকার এবং টেবিল অ্যারে হিসাবে ব্যক্তিগত ক্লাসের বৈশিষ্ট্যগুলি তৈরি করি। মনে রাখবেন যে ব্যক্তিগত বৈশিষ্ট্যগুলি ক্লাসের বাইরে ব্যবহারযোগ্য নয়। এখানে, আমরা টেবিলের আকারকে '10' হিসাবে নিই। আমরা এটি ব্যবহার করে হ্যাশ পদ্ধতি শুরু করি এবং হ্যাশ টেবিলের সূচক গণনা করি। হ্যাশ ফাংশনে, আমরা হ্যাশ টেবিলের কী এবং আকার পাস করি।
আমরা কয়েকটি প্রয়োজনীয় ফাংশন তৈরি করি এবং এই ফাংশনগুলিকে ক্লাসে সর্বজনীন করি। মনে রাখবেন যে সর্বজনীন ফাংশনগুলি ক্লাসের বাইরে যে কোনও জায়গায় ব্যবহারযোগ্য। আমরা ক্লাসের সর্বজনীন অংশ শুরু করতে 'পাবলিক:' কীওয়ার্ড ব্যবহার করি . যেহেতু আমরা হ্যাশ টেবিলে নতুন উপাদান যোগ করতে চাই, আমরা ফাংশনের আর্গুমেন্ট হিসেবে একটি কী দিয়ে 'InsertHash' নামে একটি ফাংশন তৈরি করি। 'ইনসার্ট' ফাংশনে, আমরা ইনডেক্স ভেরিয়েবল শুরু করি। আমরা সূচক ভেরিয়েবলে হ্যাশ ফাংশন পাস করি। এর পরে, টেবিলে একটি উপাদান সন্নিবেশ করার জন্য 'পুশ' পদ্ধতি ব্যবহার করে লিঙ্কযুক্ত তালিকা টেবিলে ইনডেক্স ভেরিয়েবলটি পাস করুন।
এর পরে, নতুন সন্নিবেশিত ডেটা দেখতে হ্যাশ টেবিলটি প্রদর্শন করতে আমরা একটি 'viewHashTab' ফাংশন তৈরি করি। এই ফাংশনে, আমরা একটি 'ফর' লুপ নিই যা হ্যাশ টেবিলের শেষ পর্যন্ত মানগুলি অনুসন্ধান করে। নিশ্চিত করুন যে মানগুলি একই সূচকে সংরক্ষণ করা হয়েছে যা হ্যাশ ফাংশন ব্যবহার করে বিকাশ করা হয়েছে। লুপে, আমরা তাদের নিজ নিজ সূচকে মান পাস করি এবং এখানে ক্লাস শেষ করি। 'প্রধান' ফাংশনে, আমরা 'hasTable' নামের একটি ক্লাসের অবজেক্ট নিই। এই ক্লাস অবজেক্টের সাহায্যে, আমরা পদ্ধতিতে কী পাস করে সন্নিবেশের পদ্ধতি অ্যাক্সেস করতে পারি। 'প্রধান' ফাংশনে যে কীটি আমরা পাস করেছি সেটি 'ইনসার্ট' ফাংশনে গণনা করা হয় যা হ্যাশ টেবিলে সূচকের অবস্থান প্রদান করে। আমরা একটি 'ক্লাস' অবজেক্টের সাহায্যে 'ভিউ' ফাংশনকে কল করে হ্যাশ টেবিলটি প্রদর্শন করেছি।
এই কোডের আউটপুট নিম্নলিখিত সংযুক্ত করা হয়েছে:
আমরা দেখতে পাচ্ছি, হ্যাশ টেবিলটি C++ এ লিঙ্ক করা তালিকা ব্যবহার করে সফলভাবে তৈরি করা হয়েছে। একই সূচকের সংঘর্ষ এড়াতে ওপেন চেইনিং ব্যবহার করা হয়।
উপসংহার
পরিশেষে, আমরা উপসংহারে পৌঁছেছি যে হ্যাশ টেবিল হল বিপুল পরিমাণ ডেটা দক্ষতার সাথে পরিচালনা করার জন্য মান জোড়া সহ কীগুলি সংরক্ষণ এবং পাওয়ার জন্য সবচেয়ে উদীয়মান কৌশল। হ্যাশ টেবিলে সংঘর্ষের সম্ভাবনা অনেক বেশি, ডেটা এবং এর স্টোরেজ নষ্ট হয়ে যায়। আমরা হ্যাশ টেবিল ব্যবস্থাপনার বিভিন্ন কৌশল ব্যবহার করে এই সংঘর্ষ কাটিয়ে উঠতে পারি। C++-এ হ্যাশ টেবিল তৈরি করে, ডেভেলপাররা হ্যাশ টেবিলে ডেটা সংরক্ষণ করার জন্য সর্বোত্তম উপযুক্ত কৌশল ব্যবহার করে কর্মক্ষমতা বাড়াতে পারে। আমরা আশা করি যে এই নিবন্ধটি হ্যাশ টেবিল সম্পর্কে আপনার বোঝার জন্য সহায়ক।