হ্যাশ টেবিলপড়তে ৫ মিনিট লাগবে

চেইনিং (Chaining)

লকারে জায়গা নেই? কোনো ব্যাপার না, একটার পেছনে আরেকটা ঝুলিয়ে দিন

lookup avg: O(1 + α)insert avg: O(1)delete avg: O(1 + α)space: O(n + m)

হ্যাশ টেবিলের একেকটা লকারকে পুরো একটা আলমারি না ভেবে, দেয়ালের কোট হ্যাঙ্গারের আংটা হিসেবে ভাবুন। আপনি চাইলে একটা আংটায় একটার ওপর আরেকটা করে অনেকগুলো শার্ট বা কোট ঝোলাতে পারেন—জাস্ট একটা শেকল বা চেইনের মতো নিচের দিকে ঝুলতে থাকবে। সেপারেট চেইনিং (Separate Chaining) ঠিক এই কাজটাই করে: এখানকার প্রতিটা আংটা বা বাকেট হলো একটা লিংকড লিস্টের মাথা (head), আর যে জিনিসগুলোর হ্যাশ নম্বর একই আসে, সেগুলোকে এই লিস্টের একদম পেছনে একটা একটা করে ঝুলিয়ে দেওয়া হয়।

যখন আপনি কোনো জিনিস খুঁজতে যান, আপনি প্রথমে হ্যাশ করে সঠিক আংটাটায় পৌঁছান (যাতে O(1) সময় লাগে), তারপর সেই আংটায় ঝোলানো চেইন বা লিস্ট ধরে একটা একটা করে দেখতে থাকেন, যতক্ষণ না আপনার দরকারি জিনিসটা মেলাতে পারেন। যদি এই চেইনগুলো ছোট হয়—আর লোড ফ্যাক্টর কম থাকলে ছোটই হবে—তাহলে খোঁজার স্পিড প্রায় O(1)-এর মতোই ফাস্ট থাকে।

চেইনিং বনাম ওপেন অ্যাড্রেসিং

চেইনিংয়ের সুবিধা:

বানানো বা ইমপ্লিমেন্ট করা অনেক সহজ।
টেবিল প্রায় ফুল হয়ে গেলেও সমস্যা নেই—চেইনগুলো শুধু একটু লম্বা হতে থাকে।
ডিলিট করা বা মুছে ফেলা খুব সোজা (জাস্ট লিস্ট থেকে নোডটা খুলে ফেলা)।
প্রতিটা চেইনের জন্য আপনি অন্য যেকোনো ডেটা স্ট্রাকচার (যেমন সর্টেড লিস্ট, BST বা এমনকী আরেকটা হ্যাশ টেবিলও) ব্যবহার করতে পারেন।

ওপেন অ্যাড্রেসিংয়ের সুবিধা:

সবকিছু একটা অ্যারের ভেতরেই থাকে, ছড়ানো-ছিটানো থাকে না—তাই প্রসেসরের ক্যাশ (Cache) মেমোরিতে স্পিড বেশি পাওয়া যায়।
পয়েন্টারের জন্য কোনো ফাউ মেমোরি নষ্ট হয় না।
টেবিল অর্ধেকের বেশি (০.৫) না ভরলে এটা চেইনিংয়ের চেয়েও ভালো পারফর্ম করে।

জাভার HashMap চেইনিং ব্যবহার করে। আবার পাইথনের dict ব্যবহার করে ওপেন অ্যাড্রেসিং। দুটোই দারুণ কাজ করে—তবে তফাতটা মূলত মেমোরি খরচ করা বনাম ক্যাশ পারফরম্যান্সের মাঝে।

◈ Explore hash chaining

← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন

কখন সাইজ বাড়াতে হবে (Resize)

চেইনিংয়ের ক্ষেত্রে, লোড ফ্যাক্টর α = n / m (n মানে মোট জিনিস, m মানে মোট বাকেট)। এটা দেখলেই বোঝা যায় গড়ে চেইনগুলো কত লম্বা হবে। α = 1 মানে হলো, গড়ে প্রতিটা আংটায় একটাই জিনিস ঝুলছে—এটা একদম ঠিক আছে। α = 3 মানে প্রতি আংটায় গড়ে ৩টা করে জিনিস—তখনও ঠিক আছে, তবে স্পিড একটু কমতে শুরু করবে।

চেইনিংয়ের ক্ষেত্রে সাইজ বাড়ানোর সাধারণ নিয়ম হলো α > ০.৭৫ (৭৫% ফুল হলে)। তখন টেবিল তার বাকেটের সংখ্যা ডাবল করে ফেলে এবং সব জিনিসপত্র বা ডেটাকে নতুন বড় সাইজের অ্যারেতে আবার হ্যাশ করে নতুন আংটায় জায়গা দেয়। এই কাজে একবার O(n) সময় লাগলেও গড়ে প্রতিটা ইনসার্টের সময় হিসাব করলে সেটা O(1)-ই থাকে (যাকে Amortized O(1) বলে)।

সাইজ ডাবল করার পর α-এর মান কমে গিয়ে ০.৩৭৫ (০.৭৫-এর অর্ধেক) হয়ে যায়, ফলে আবার টেবিল ভরে যানয়ার আগে মনের সুখে স্পিড পাওয়া যায়।

লম্বা চেইনকে গাছে (Tree) বদলে ফেলা (Java 8+)

জাভার HashMap-এ একটা দারুণ ট্রিক আছে: যদি কোনো একটা চেইন অতিরিক্ত লম্বা হয়ে ৮টা নোড পার হয়ে যায়, তখন জাভা অটোমেটিকভাবে পুরো চেইনটাকে একটা রেড-ব্ল্যাক ট্রি (Red-Black Tree) বানিয়ে ফেলে। এর ফলে ওই বাকেটে সাধারণ খোঁজার সময় O(n) থেকে কমে রকেটের স্পিডে O(log n) হয়ে যায়—যেটা মূলত কেউ যদি হ্যাশ নিয়ে দুষ্টুমি বা অ্যাটাক (Adversarial input) করে একটা বাকেটেই সব ডেটা ভরে দিতে চায়, তার হাত থেকে বাঁচার একটা দারুণ সেফটি নেট!

দ্রষ্টব্য: গড়ে একেকটা বাকেটে বা আংটায় কয়টা জিনিস থাকবে, সেটাই হলো লোড ফ্যাক্টর বা α। একটা ভালো হ্যাশ ফাংশন ব্যবহার করে α-এর মান ১.০-এর নিচে রাখতে পারলে আপনি নিশ্চিত থাকতে পারেন যে আপনার সিস্টেম গড়ে O(1) পারফরম্যান্সই পাবে।