হ্যাশটেবিল (Hashtable)

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

  • Insertion
  • Look-up or Search
  • Delete or Update

আমরা এ্যারেতে র‍্যান্ডমলি ডাটা রেখে সেখান থেকে ইনডেক্স ধরে ডাটা নিয়ে আসতে পারি। যদিও সেটার Worst case complexity হয় O(n) । আবার ডাটাগুলো যদি ক্রমানুসারে থাকে তাহলে বাইনারী সার্চ করে কমপ্লেক্সিটি O(logn) এ কমিয়ে আনতে পারি। আচ্ছা কেমন হয় যদি আমরা এই কমপ্লেক্সিটি O(1) এ নিয়ে আসতে পারি? অর্থাৎ একটা সিঙ্গেল অপারেশনেই আমাদের ডাটা সার্চ করে নিয়ে আসতে পারি? হুম, হ্যাশটেবিল(Hash Table) তেমনই একটা চমৎকার ডাটা স্ট্রাকচার যেটার কমপ্লেক্সিটি O(1)।

কিভাবে হ্যাশটেবিল কাজ করে?

এটা বোঝার আগে একটু চিন্তা করি এ্যারে কিভাবে কাজ করে? এ্যারেতে 0 থেকে n-1 পর্যন্ত ইনডেক্স থাকে এবং সেই ইনডেক্সগুলোতে আমরা একটা একটা করে পর পর ভ্যালু রাখতে পারি।

array01

তারমানে প্রতিবার একেকটা খালি স্লটে ডাটা রাখতে আমাদের O(1) কমপ্লেক্সিটি লাগে। আর আমরা যদি খুঁজতে যাই কোনো একটা ভ্যালু x এ্যারেতে আছে কিনা তাহলে আমাদের সবোর্চ্চ n টা ইনডেক্স খুঁজে দেখতে হবে। মানে Worst case complexity হবে O(n)। আবার কোনো একটা ভ্যালু তার ইনডেক্স থেকে মুছে ফেলতে চাইলে আগে সেই ভ্যালু খুঁজে বের করতে হবে, O (n) কমপ্লেক্সিটিতে, এবং তারপর সেটাকে ডিলিট করতে হবে, O(1) কমপ্লেক্সিটিতে। তারমানে দেখা যাচ্ছে মূলত ভ্যালুটা এ্যারের কোথায় আছে সেটার কমপ্লেক্সিটিই সবচেয়ে বেশী সময় নিচ্ছে। আমরা যদি এই খুঁজে বের করার সময়টা কমাতে পারি তাহলেই এফিসিয়েন্সি বেড়ে যাবে। বাইনারী সার্চে খুঁজে বের করার কমপ্লেক্সিটি আমরা O(logn) এ কমিয়ে আনতে পারি বলেই সেটা কিছুটা এফিসিয়েন্ট। কিন্তু একটা ব্যাপার কি খেয়াল করেছেন, আমরা এ্যারেতে কি ভ্যালু রাখছি সেটার সাথে এ্যারের ইনডেক্সের কোনো সম্পর্ক নেই। এটার জন্যই কিন্তু আমাদের সময় বেশী লাগছে ইনডেক্স ধরে ভ্যালু খুঁজে বের করতে।

আচ্ছা যদি এমন হয় আমাদেরকে বলে দেয়া হলো ১০ টা সংখ্যা আমাদের দেয়া হবে এবং সেগুলো ১ থেকে ১০ এর মধ্যেই হবে। তাহলে আমরা কি করতাম? আমরা যদি একটু বুদ্ধি খাটাই তাহলে আমরা কাজটা এভাবে করতে পারি যে, যেই ভ্যালুটা দেয়া হবে সেটাকে ঠিক সেই নাম্বার ইনডেক্সে আমরা রাখবো। মানে এরকম-

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

হ্যাশটেবিলের জন্য আমরা এ্যারেকেই ব্যবহার করবো কারণ এ্যারের 0 to n-1 ক্রমানুসারে সাজানো ইনডেক্সিংটা বেশ কাজের আর এটা প্রোগ্রামিং ল্যাংগুয়েজগুলোতে বিল্ট-ইন। আর হ্যাশটেবিলে ডাটা রাখার জন্য আমরা যেই কাজটা করবো সেটা হলো একটা ফাংশন বানাবো যেটাকে বলা হবে হ্যাশ ফাংশন (Hash Function) বা ম্যাপিং ফাংশন (mapping function)। এই ফাংশনের কাজ হবে তাকে একটা ভ্যালু দেয়া হলে সে সেটা থেকে হিসেব করে একটা এ্যারের ইনডেক্স রিটার্ন করবে অর্থাৎ এ্যারের ইনডেক্সে ম্যাপ করবে। এবং আগের হ্যাশ এবং হ্যাশিং পোস্টে যেমন বলেছিলাম একই ভ্যালুর জন্য হ্যাশ ভ্যালু সবসময় একই হবে, এখানেও সেটা ফলো করা হবে। অর্থাৎ একই ভ্যালুর জন্য হ্যাশ ফাংশন সবসময় একই ইনডেক্স রিটার্ণ করবে। চটপট একটা এক্সাম্পল দিয়ে ফেলি।

মনে করি আমাদের এ্যারেতে কিছু স্ট্রিং রাখতে হবে। আমরা হ্যাশিং ফাংশনটা এমনভাবে লিখবো যাতে করে যেই স্ট্রিংটা দেয়া হবে সেটার প্রথম অক্ষর দিয়ে আমরা সেটার ইনডেক্স নাম্বার বের করতে পারি। তাহলে আমাদের ফাংশনটা হতে পারে এরকম-

int hash_function(char* key)
{
    //hash on first letter of string
    int hash = toupper(key[0])-‘A’;
    return hash%size; //size is the size of the array
}

এখন এই হ্যাশ ফাংশন ব্যবহার করে আমরা যদি ‘apple’ স্ট্রিংটাকে এ্যারেতে রাখতে চাই তাহলে সেটা এরকম হবে-

hash-0

যেহেতু স্ট্রিংটার প্রথম অক্ষর ‘a’ এবং আমাদের হ্যাশ ফাংশন এটার জন্য 0 রিটার্ণ করেছে সুতরাং স্ট্রিংটা 0 নাম্বার ইনডেক্সে স্টোর হবে। একইভাবে ‘banana’, ‘cat’ এই ইনপুট গুলোর জন্য আমাদের টেবিলটা কেমন হবে সেটা নিশ্চয়ই বোঝা যাচ্ছে-

hash-11

sha-12

কেউ কেউ হয়তো বুঝে ফেলেছেন এই হ্যাশ ফাংশন নিয়ে আমরা একটু ঝামেলাতেই পড়তে যাচ্ছি। কি হবে যখন আরেকটা স্ট্রিং এ্যারেতে রাখার দরকার পড়বে যেটার শুরু ও ‘a’ দিয়ে। সেটার জন্যও তো হ্যাশ ফাংশন 0 ই রিটার্ণ করবে। কিন্তু 0 ইনডেক্সে তো আমরা অলরেডি একটা ভ্যালু রেখেছি।

hash-13

এই সমস্যার সমাধান কি হতে পারে সেটা নিয়ে একটু পরে বলছি। এতক্ষণে নিশ্চয়ই বোঝা গেছে কেনো হ্যাশ ফাংশন O(1) এ কাজ করে? আমাদের যখনই কোনো ডাটা স্টোর করা লাগছে আমরা শুধুমাত্র হ্যাশ ফাংশনে একটা সিঙ্গেল অপারেশন করে সেটা কোন ইনডেক্সে বসবে সেটা বের করে নিচ্ছি। যেহেতু কনস্ট্যান্ট অপারেশন সুতরাং কমপ্লেক্সিটি O(1)। সার্চ করার সময় কি হবে? মনে করি আমরা দেখতে চাই আমাদের এ্যারেতে ‘banana’ আছে কিনা। আমরা হ্যাশ ফাংশনে যদি ‘banana’ পাঠাই তাহলে হ্যাশ ফাংশন কিন্তু আমাদের ইনডেক্স হিসেবে 1 ই রিটার্ণ করবে। এর মানে হচ্ছে হ্যাশ ফাংশন আমাদের বলছে, “এই স্ট্রিংটা যদি থেকেই থাকে তাহলে আমি ওকে এই ইনডেক্সেই রেখেছি, যদি ওখানে না পাও তার মানে এটা এখানে কোথাও নেই”।  সুতরাং ব্যাপারটা সহজ হয়ে গেলো, আমরা শুধু হ্যাশ ফাংশনের রিটার্ণ করা ইনডেক্সেই ভ্যালুটা খুঁজে দেখবো, তারমানে কমপ্লেক্সিটি O(1)। যদি কোনো ভ্যালু ডিলিট করতে হয় সেই একই ব্যাপার, O(1) কমপ্লেক্সিটিতে সেই ভ্যালুর ইনডেক্স বের করে O(1) এ সেটাকে ডিলিট করে দেয়া যাবে।

এবার আসি আমরা একটু আগে ‘একই ইনডেক্সে একাধিক ভ্যালু’ রাখার যেই সমস্যায় পড়েছি সেটায়। এই সমস্যাটাকে বলা হয় ‘collision‘। আমরা এখানে ইনডেক্সিংয়ের জন্য যেই হ্যাশ ফাংশনটা ব্যবহার করেছি সেটা একেবারেই সাধারণ একটা হ্যাশ ফাংশন এবং মোটেও এফিসিয়েন্ট না। এই হ্যাশ ফাংশনটা অন্যভাবেও লেখা যায়। আসলে অন্য অনেকভাবেই লেখা যায়। কিন্তু মূলত একটা হ্যাশ ফাংশন কেমন হওয়া উচিত? আমরা একটু সাধারণ লজিক খাটালেই বুঝতে পারি যদি আমাদের হ্যাশ ফাংশনটা প্রতিটা ইনপুটের জন্য ইউনিক(Unique) ইনডেক্স রিটার্ণ করতে পারে তাহলেই সেটাকে আমরা ‘পারফেক্ট হ্যাশ ফাংশন (Perfect Hash Function)‘ বলতে পারি, অর্থাৎ সেখানে কোনো collision হবে না। যদি আমরা শুরুতেই জানতে পারি আমাদের কি কি ভ্যালু রাখতে হতে পারে, এবং সেই সেটটা (set of values) যদি খুব বেশী বড় না হয়, এবং যদি আমাদের কাছে সেই সেটের সমান বা বড় সংখ্যক ইনডেক্স থাকে ভ্যালুগুলো রাখার জন্য তাহলে অবশ্যই এমন একটা হ্যাশ ফাংশন বানানো সম্ভব যেটা প্রত্যেকটা ভ্যালুর জন্য ইউনিক ইনডেক্স ম্যাপ করতে পারবে। কিন্তু বাস্তবে সবসময় এমনটা হয় না। কারণ সাধারণত আমাদের অনেক বড় রেঞ্জের সেটের ভ্যালু স্টোর করতে হয় আর ‘pigeonhole principle’ অনুযায়ী আমরা জানি স্টোর ক্যাপাসিটি থেকে এলিমেন্ট বেশী হলে অবশ্যই একটা গর্তে একের বেশি pigeon থাকবে। সুতরাং আমাদের দেখতে হবে collision হলে আমরা কিভাবে এটা হ্যান্ডেল করতে পারি।

 collision হ্যান্ডেল করার পপুলার দুটো মেথড হলোঃ

  • Open Hashing or Separate Chaining
  • Closed Hashing or Open addressing

Open Addressing এর আইডিয়াটা খুব বেশী এফিসিয়েন্ট না তাই সংক্ষেপে বলি এটায় কি করা হয়। এই পদ্ধতিতে যখনই কোনো একটা ঘরে একের বেশী ভ্যালু রাখার দরকার পড়ে তখন দেখা হয় ঠিক পরে কোন ঘরটা খালি আছে, সেখানে ঐ ভ্যালুটা রেখে দেয়া হয়।

linear probing

এই ছবিটা থেকে ব্যাপারটা বোঝা যায়। ‘ant’ এর জন্য হ্যাশ ফাংশন 0 রিটার্ণ করার পর আমরা দেখতে পাই সেখানে ইতিমধ্যেই ‘apple’ রাখা আছে। সেজন্য আমরা খুঁজে বের করি পরের কোন ঘরটা ফাঁকা আছে। পরের 3 নাম্বার ইনডেক্স ফাঁকা আছে তাই আমরা সেখানে ‘ant’ রাখবো। বোঝাই যাচ্ছে এই পদ্ধতিতে পরবর্তীতে collision এর সম্ভাবনা আরো বাড়বে এবং এটায় স্বাভাবিকভাবেই কমপ্লেক্সিটি আরো বাড়বে। সুতরাং এটাকে খুব একটা কাজের বলা যায় না।

ইন্টারেস্টিং আইডিয়াটা হচ্ছে Separate Chaining. এখানে প্রতিটা ইনডেক্সে একটা ভ্যালু না রেখে একটা লিংকড লিস্ট রাখা হয়। সুতরাং একের বেশী ভ্যালু একই ইনডেক্সে রাখার দরকার পড়লে সেটা লিংকড লিস্টে যুক্ত হয়ে যাবে। নীচের ছবির মত করে-

separate chaining

এভাবে যদি আমরা ভ্যালুগুলো রাখি তাহলে আমাদের আর collision এর ঝামেলাটা হবে না। কিন্তু এতে কি হ্যাশটেবিল আগের মতই O(1) এ সব অপারেশন করতে পারবে?
ভ্যালু insertion এর সময় ইনডেক্স খুঁজে বের করে লিংকড লিস্টে সেটা যোগ করতে আগের মতই O(1) ই লাগবে। খুঁজে বের করার সময় আমরা হ্যাশ ফাংশন ব্যবহার করে O(1) এ ইনডেক্স খুঁজে বের করে লিংকড লিস্টে সার্চ করতে হবে। সেক্ষেত্রে লিংকড লিস্টের সাইজ যদি k হয় তাহলে সার্চের কমপ্লেক্সিটি হবে O(k) । এখন worst case এ এমন হতে পারে আমাদের যোগ করা সবগুলো ভ্যালুই অর্থাৎ n টা ভ্যালুই হ্যাশ টেবিলের একই পজিশনে লিংকড লিস্টে আছে। তাহলে সার্চিংয়ের কমপ্লেক্সিটি দাঁড়ায় O(n) যেটা কিনা সাধারণভাবে একটা লিংকড লিস্টে লিনিয়ার সার্চের কমপ্লেক্সিটির সমান। যদিও ব্যাপারটা থিওরেটিক্যালি এরকম কিন্তু বাস্তবে আমরা যদি একটা এফিসিয়েন্ট হ্যাশ ফাংশন ব্যবহার করতে পারি আর হ্যাশ টেবিলে পর্যাপ্ত জায়গা থাকে তাহলে একই ইনডেক্সে অনেক বেশী ভ্যালু থাকার প্রোবাবিলিটি অনেক কমে যাবে। সেক্ষেত্রে সার্চিংয়ের কমপ্লেক্সিটিও অনেক কমে যাবে।

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

যদিও যেসব জায়গায় হ্যাশটেবিল ব্যবহার করা যায় তার অনেকগুলোই বাইনারী সার্চ ট্রি দিয়েও সলভ করা যায় তারপরও Dictionary কিংবা map, associative array (Key=> value pair) টাইপ কোনো কিছু ইমপ্লিমেন্টেশনের জন্য হ্যাশটেবিল বেশ ভালো একটা অপশন।

হ্যাশটেবিল কি সব জায়গায় ব্যবহার করা সম্ভব? না। কারণ হ্যাশটেবিলেরও বেশ কিছু অসুবিধা আছে। যেমন Insertion, searching, deletion এর মত অপারেশনগুলো আপনি হ্যাশটেবিলে বেশ সহজে করতে পারলেও sorting, comparison of values, highest/lowest values in a range টাইপ কাজ গুলো আপনি হ্যাশটেবিরে এফিসিয়েন্টলি করতে পারবেন না। সেক্ষেত্রে সিম্পল এ্যারে বা অন্য ডাটা স্ট্রাকচার তুলনামূলক সুবিধাজনক। যেমনটা আগেই বলেছি কি ধরনের ডাটা হ্যান্ডেল করতে হবে আর ডাটার উপর কি ধরনের অপারেশন চালানো হবে সেটার উপরই নির্ভর করে আপনি কোন ডাটা স্ট্রাকচারটা ব্যবহার করবেন।

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

Want to like or share?:
0

31 comments

    1. খুব কি কঠিন করে লেখা? দুই একবার পড়লেই যাতে বোঝা যায় সেভাবেই তো লেখার চেষ্টা করেছি। 🙂

  1. Wow vaiya! wonderfully expalined. Eivabe apni jodi aro kichu kothin topics sohoje bujhiye diten amra onekei upokrito hotam. Many thanks vaiya.

    1. আপনাকেও ধন্যবাদ। আমি নিজেই তো সব কঠিন কঠিন টপিকস বুঝি না। 😛 যেগুলো বুঝি বা নতুন শিখছি সেগুলো নিয়ে লেখার চেষ্টা করবো। 🙂

  2. ভালো লেগেছে। ধন্যবাদ ;
    পরের লেখার জন্য অপেক্ষা করছি….

  3. as usual সুন্দর হইছে 😛 সো বার বার সেইম কথা বলে বোর করার দরকার নাই 😛 স্ট্রিং হাশিংএর উপর টিউটোরিয়ালটা চাই তারাতারি 😛 আর practice এর জন্য কিছু প্রবলেম লিংক পাওয়া গেলে ভাল হত 🙂

    1. ধন্যবাদ। বার বার ভালো হইছে শুনতে খারাপ লাগে না। 😛 স্ট্রিং হ্যাশিংয়েরটা লিখে ফেলবো শিগগিরি। ঐটার সাথে প্রাকটিস প্রবলেমের লিংক দিবো। 🙂

  4. খুব ভাল লাগলো। সহজেই বুঝতে পেরেছি। ধন্যবাদ।

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

  6. অনেক সুন্দর করে লিখার জন্য ধন্যবাদ… একবারেই খুব বেশি বুঝতে পারিনা আমি কিন্তু অনেকটাই বুঝতে পেরেছি ভাই 🙂

  7. আজ এক দারুন জিনিস শিখলাম।খুব ভালো লাগলো।।অসংখ্য ধন্যবাদ আপনাকে।এরকম আরো কিছু নতুন জিনিস শেখালে ভালো হয়।।

  8. hash table is better or map is more better?
    why i will use my hash function/hash table instead of map?
    why not map?
    plz clear me…i can’t understand why i use hash table ..i can use map
    plz clear the situation when i could’t use map in cpp,,i need to use hash table

    1. Before comparing hash table and map you may need to know something. STL std::map of C++ is basically an ‘ordered_map’, which is implemented based on balanced binary search tree(usually Red-Black Tree). But there is another thing called ‘unordered_map’ or ‘hash_map’ which is not standard in C++ (But now available in C++11 as std::unordered_map) is implemented by hash table. From the name you can guess that the keys are ordered in ‘map’ or ‘ordered_map’ which requires some extra overhead on insertion and deletion operation on it. So the ‘unorderd_map’ or ‘hash_map’ will have slightly better performance on insertion and deletion operation. On the other hand, ‘ordered_map’ will give better performance on searching, as the keys are stored in sorted order. Now the question is do you really need to compare hash table and map? I don’t think so. You can use map every time you need. But there may be some situation where you may need to know the concept behind the hash table.

  9. Bro, it would be better if you added some related problem links adopted from different OJ’s. Specially, it helps the beginners like me. 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *