আগের পোস্টের সমস্যাটি হলো- দুটি ভিন্ন ভিন্ন স্ট্রিং হ্যাশ ফাংশনে দিলে যদি একই ভ্যালু পাওয়া যায় তাহলে কী হবে? উত্তরটির জন্য পুরো আর্টিক্যাল পড়তে হবে।

এখন শুরুতে আমি একটি প্রশ্ন করি, দুটি ভিন্ন স্ট্রিংয়ের জন্য হ্যাশ ফাংশন কি একই ভ্যালু রিটার্ন করতে পারে? উত্তরটি নির্ভর করে তোমার হ্যাশ ফাংশনের উপর। তুমি কীভাবে সেটি ইমপ্লিমেন্ট করছো তার ওপর। তবে বাস্তবে কোনো হ্যাশ ফাংশনই শতভাগ এই নিশ্চয়তা দেয় না যে, সে সবসময়ই ভিন্ন ভিন্ন স্ট্রিংয়ের জন্য ভিন্ন ভিন্ন ভ্যালু রিটার্ন করবে।

আরো গভীরে যাওয়ার আগে সমস্যাটা নিয়ে আরো একটু আলোচনা করি। মনে করো, তোমার হ্যাশ ফাংশনটি খুবই সাধারণ। এটি অ্যারেতে উপাদানগুলো বর্ণানুক্রমে স্থান দেয়। তোমার পণ্যগুলো যথাক্রমে আদা, রসুন, পেঁপে, কলা ইত্যাদি হয় এবং তোমার অ্যারের সাইজ যদি 10।

ওপরের ছবি দুটি থেকে দেখতে পাচ্ছো, আদা, কলা, পেঁপে, রসুন এবং মরিচ এগুলোর হ্যাশ ভ্যালু যথাক্রমে ১,২,৩ ও ৭, ৮। সুতরাং এগুলো অ্যারের ০,১,২ ও ৬,৭ নম্বর ইন্ডেক্সে বসনো হয়েছে। কিন্তু জীবন তো আর পুষ্পশয্যা নয়। একটু পরেই এসেছে আম। আর তোমার হ্যাশ ফাংশন এর জন্যে ভ্যালু রিটার্ন করেছে ১।

সমস্যাটি নিশ্চয় বুঝতে পারছো। এই সমস্যাকে বলা হয় কলিশন (collision)। এখন তুমি যদি অ্যারের ১ নম্বর ইনডেক্সে আমের দাম রাখো, তাহলে আগের আদার দামের সাথে এটি রিপ্লেস হয়ে যাবে। এতে করে তুমি যদি পরবর্তীতে আদার দাম দাও, তোমার হ্যাশটেবিল আমের দাম দিয়ে দিবে যা হওয়া উচিৎ নয়।

কলিশন সমাধানের উপায় কী হতে পারে? এ সমস্যা সমাধানের আসলে অনেকগুলো উপায় হতে পারে। তবে সবচেয়ে সহজ উপায় হলো, যে সব পণ্যের হ্যাশ ভ্যালু একই সেগুলোকে একই স্লটে রাখা এবং এজন্যে লিংকডলিস্ট ব্যবহার করা।

লিংকডলিস্টের নাম নিশ্চয় শুনেছো এবং আমার ধারণা প্রত্যেকেই ইমপ্লিমেন্ট করেছো। লিংকডলিস্ট হচ্ছে ট্রেনের মতো। একটির পেছনে আরেকটি বগি জোড়া লাগিয়ে তাতে ভ্যালু রাখা।

তবে এতেও একটি সমস্যা আছে। তোমার মুদির দোকানের সবগুলো পণ্য যদি একটি নির্দিষ্ট বর্ণ দিয়ে শুরু হয় তাহলে প্রথম স্লটে একটি বিশাল চেইন হবে। এক্ষেত্রে হ্যাশ টেবিল থেকে কোন পণ্যের দাম খুঁজে আনার সময় আর O(1) থাকবে না বরং সেটি হয়ে যাবে O(n)। কারণ তখন তোমাকে লিংকডলিস্ট থেকে উপাদানটি খুঁজতে হবে। লিংকডলিস্ট থেকে কোন উপাদান খুঁজে বের করতে সময় লাগে O(n)।

ওপরের ছবি থেকে নিশ্চয় দেখতে পাচ্ছো সমস্যাটি কোথায়? তোমার অ্যারের বাকি স্লটগুলো প্রায় খালি রয়ে গেছে।
তাহলে এখান থেকে দুটি বিষয় জানা গেলো –
১. হ্যাশ ফাংশন অনেক গুরুত্বপুর্ণ। এটি খুব সিম্পল হলে সমস্যা।
২. প্রত্যেকটি স্লটেই যদি অনেক বড় লিংকলিস্ট থাকে, তাহলে কনস্ট্যান্ট টাইম অর্থাৎ O(‌1) সময়ে তুমি উপাদান খুঁজে বের করতে পারছো না।
এখন যদি তুমি একটি ভালো হ্যাশ ফাংশন লিখতে পারো, এবং প্রত্যেক স্লটেই যাতে বিশাল লিংকডলিস্টের চেইন না হয় তা নিশ্চিত করতে পারো তাহলেই O(‌1) সময়ে হ্যাশ টেবিল থেকে ভ্যালু পড়তে পারবে।

এবার Load Factor বলে একটা টার্ম আছে, এটি নিয়ে একটু বলি তোমাদের। একটি হ্যাশটেবিলের লোড ফ্যাক্টর খুব সহজেই বের করা যায়।

Load Factor = Number of items in the hash table / Total slot in the array

তাহলে তোমার অ্যারেতে যদি স্লট হয় 10 এবং উপাদানের সংখ্যা যদি হয় ৭ তাহলে লোড ফ্যাক্টর হবে- 0.7। এটি দিয়ে একটি হ্যাশটেবলি কতগুলো স্লট ফাকা আছে তা বের করা যায়। একটি হ্যাশটেবিলের লোড ফ্যাক্টর যদি 1 হয় তাহলে এর বোঝায়, এর প্রত্যেকটি স্লটে একটি করে উপাদান রয়েছে। লোড ফ্যাক্টর একের অধিক থাকার অর্থ হলো, টেবিলের কোন স্লটে একাধিক উপাদান রয়েছে।

কনস্ট্যান্ট টাইম অর্থাৎ O(1) সময়ে কোন উপাদান খুঁজে পাওয়া নিশ্চিত করতে চাইলে লোড ফ্যাক্টর সবসময় একের নিচে রাখতে হবে। এটি করার জন্যে যখনই লোড ফ্যাক্টর ১ এর বেশি হবে তখনই টেবিলকে রিসাইজ করে আবার প্রত্যেকটি উপাদানের হ্যাশ ক্যালকুলেট করে বিভিন্ন স্লটে বসাতে হবে। এই অপারেশনটি মোটামুটি এক্সপেনসিভ। তবে তুমি কনস্ট্যান্ট টাইম উপাদানগুলো খুঁজে পাচ্ছো টেবিলের সাইজ যতোই হোক না কেনো।

তাহলে উপরের আলোচনা থেকে নিশ্চয় বুঝতে পারছো যে, যদিও কনস্ট্যান্ট টাইমে আমরা উপাদান খুঁজে বের করতে চাচ্ছি, কিন্তু সবসময় তা সম্ভব নয়। তবে best case এটি অবশ্যই O(1) হবে এবং worst case-এ এটি O(n) হতে পারে।