মডিউল ২৩-৪ঃ map কি?

এবার আমরা দেখব সি++ এর ম্যাপ। ম্যাপ বুঝার আগে আমরা একটু এরের ব্যাসিকটা আরেকবার মনে করি। এরেতে আমরা যেকোন ডাটা টাইপের ভেলু রাখতে পারতাম। এরেতে ইন্ডেক্স থাকতো, যা ০ থেকে শুরু হয়ে এরের সাইজ - ১ পর্যন্ত হতো। এক্ষেত্রে এরে সাইজ ম্যাক্স 10^5 পর্যন্ত হতে পারত। এখানে প্রবলেম হচ্ছে, আমাদের যদি কখনো 10^5 এর বেশি ইনডেক্স প্রয়োজন হয়, তখন আমরা কি করতে পারি? অথবা আমাদের যদি ইন্ডেক্সে ইন্টিজার ছাড়া অন্য কিছু রাখতে চাই তখন কি করতে পারি? এরেতে আমরা যেকোন ডাটা টাইপের ভেলু রাখতে পারলেও ইনডেক্স কিন্তু ফিক্সড ইন্টিজার টাইপের থাকে। তাই আমাদের যদি কখনো ইন্ডেক্সে ইন্টিজার ছাড়া অন্য কোন ডাটা টাইপ রাখার প্রয়োজন হয় তখন আমরা ম্যাপ ব্যাবহার করতে পারি। এছাড়াও 10^5 এর বড় ইন্টিজার ভেলু ইন্ডেক্স হিসেবে প্রয়োজন হলেও ম্যাপ ব্যাবহার করতে পারি। এরে হচ্ছে ইন্ডেক্স ভেলু পেয়ার [যেখানে ইন্ডেক্স ইন্টিজার ডাটা টাইপের] । ম্যাপ হচ্ছে কি ভেলু পেয়ার [যেখানে কি যেকোন ডাটা টাইপের হতে পারে]।

আমরা একটি উদাহরন দিয়ে ম্যাপ এর ব্যাবহার দেখে নিতে পারি। মনে করি, কিছু স্টুডেন্ট এর নাম দেওয়া আছে। কার নাম কয়বার আছে তা কাউন্ট করতে হবে। sakib rakib sakib akib rakib akib sakib sakib rakib

এই কাজটি আমরা নেস্টেড লুপ দিয়ে করতে পারব কিন্ত সেক্ষেত্রে কমপ্লেক্সিটি হয়ে যাবে O(N*N) আমরা কাউন্টিং এরে বা ফ্রিকুয়েন্সি এরে দিয়ে O(N) এ করতে পারতাম যদি ইন্টিজার ভেলু হতো। কিন্তু এক্ষেত্রে কাউন্ট করার প্রতিটি ভেলু স্ট্রিং হওয়ায় ফ্রিকুয়েন্সি এরে ব্যবহার করা যাচ্ছে না। তাই এখানে আমরা ম্যাপ ব্যবহার করতে পারি। সবগুলো ভেলু কাউন্ট করে ম্যাপ এ স্টোর করার পর ম্যাপটি দেখতে এমন হবে। map["sakib"] = 4; map["rakib"] = 3; map["akib"] = 2; ^ | key

ম্যাপ এভাবে কাজ করে। ম্যাপ এর এই টেকনিকটিকে বলে হ্যাশিং। এক্ষেত্রে লক্ষণীয় হলো, খুব বেশি কি হলে ম্যাপ ঠিকঠাক কাজ করে না। তাই ম্যাপ আমরা তখনি ব্যবহার করব যখন আমাদের আর কোন ওয়ে নেই ম্যাপ ব্যবহার করা ছাড়া।