Hash Table Explained

Hash Table Explained

সহজ ভাষায় হ্যাশটেবিল

·

2 min read

একটা প্লেইন অ্যারের সাথে একটা ফাংশনের কম্বিনেশন ঘটিয়ে চমৎকার একটা ডেটাস্ট্রাকচার তৈরি করা যায়। যেখানে অ্যারেতে ডেটা ইনসার্ট, ডিলিট বা সার্চ করতে O(n) পরিমাণ সময় লাগে, সেখানে শুধু একটা এক্সট্রা ফাংশন ব্যবহার করার মাধ্যমে টাইম কমপ্লেক্সিটি হয়ে যায় O(1) বা কন্সট্যান্ট টাইম। মজার বিষয় হচ্ছে দুই ক্ষেত্রেই আমরা ডেটা রাখার জন্য ব্যবহার করছি অ্যারে।

তাহলে এত টুকু বোঝাই যাচ্ছে যে অ্যারে এখানে মূখ্য বিষয় না, মূখ্য বিষয় হচ্ছে ওই ফাংশন। এই ফাংশনকে আমরা বলি হ্যাশ ফাংশন। কারণ এটা প্রতিটা এলিমেন্টের জন্য একটা ইউনিক হ্যাশ জেনারেট করে। এই ইউনিক হ্যাশকে অ্যারে লেন্থ দিয়ে মড করলে পাওয়া যায় ওই ডেটার জন্য বরাদ্ধকৃত ইন্ডেক্স। আর কোনো ভাবে যদি আপনি অ্যারে ইন্ডেক্স জানতে পারেন তাহলে কন্সট্যান্ট টাইমেই ডেটা বের করে আনতে পারবেন।

হ্যাশ ফাংশন তৈরির ক্ষেত্রে দুইটা জিনিস মাথায় রাখতে হয়। প্রথমত একটা নির্দিষ্ট ইনপুটের হ্যাশ যেন সব সময় একই হয়। উদাহরণ স্বরূপ বলা যায়, হ্যাশ ফাংশনে ‘HM Nayem’ ইনপুট দিলে এটা যদি ৪২ জেনারেট করে তাহলে সব সময়ের জন্যই ‘HM Nayem’ ইনপুট দিলে ৪২ জেনারেট করতে হবে। আর দ্বিতীয়ত যেন সব সময় হ্যাশটা ইউনিক হয়। আপনার হ্যাশ ফাংশন যত ভালো হবে, আপনার স্ট্রাকচার তত ভালো পার্ফরম করবে।

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

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

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