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

হ্যাশ ফাংশন (Hash Functions)

যেকোনো নাম বা ডেটাকে মুহূর্তের মধ্যে একটা নির্দিষ্ট নম্বরে বদলে ফেলা

hash compute: O(k), যেখানে k = চাবির (key) দৈর্ঘ্যlookup avg: O(1)lookup worst: O(n)space: O(n)

ধরুন আপনি জিমের লকার রুমে আছেন, যেখানে ১০০টা নম্বর দেওয়া লকার আছে। আপনার জিনিসপত্র কোন লকারে রাখবেন, সেটা ঠিক করার জন্য সব লকার খুঁজে দেখার কোনো দরকার নেই। আপনার কাছে একটা ম্যাজিক ফর্মুলা আছে — আপনার নাম বললেই ফর্মুলাটা বলে দেয় ঠিক কত নম্বর লকারটা আপনার। এই ম্যাজিক ফর্মুলাটাকেই বলা হয় হ্যাশ ফাংশন (Hash Function)।

একটা হ্যাশ ফাংশন যেকোনো কি (Key)—হোক সেটা কোনো নাম (string), নম্বর বা কোনো অবজেক্ট—তাকে নিয়ে অ্যারের একটা নির্দিষ্ট নম্বর বা ইনডেক্সে (Index) বদলে দেয়। এর আসল টার্গেট হলো: সব কি বা ডেটাকে পুরো অ্যারে বা লকারগুলো জুড়ে সমানভাবে ছড়িয়ে দেওয়া, যাতে পরে খোঁজার সময় চোখের পলকে বা O(1) সময়েই খুঁজে পাওয়া যায়।

ভালো হ্যাশ ফাংশন আসলে কী?

ডিটারমিনিস্টিক (Deterministic) — একই নাম বা ডেটা দিলে সবসময় একই নম্বর বা রেজাল্ট দেবে।
সমানভাবে ছড়ানো (Uniform distribution) — সব জায়গায় ডেটা মোটামুটি সমানভাবে বসাবে, কোনো নির্দিষ্ট লকারে বেশি ভিড় করবে না।
সুপার ফাস্ট (Fast to compute) — হিসাব করতে বেশি সময় নিলে তো এর আসল স্পিডই কমে গেল।
বরফধস ইফেক্ট (Avalanche effect) — ইনপুটে একটুখানি বদল করলেই আউটপুট বা লকার নম্বর আকাশ-পাতাল বদলে যাবে।

স্ট্রিং বা নামের জন্য খুব সাদামাটা একটা হ্যাশ ফাংশন হতে পারে এমন: নামের সব অক্ষরের (ASCII) মান যোগ করে তাকে লকারের সংখ্যা দিয়ে ভাগশেষ (modulo) বের করা। অর্থাৎ hash = (অক্ষরগুলোর যোগফল) % লকার সংখ্যা। এটা বেশ সোজা, কিন্তু এতে একটা সমস্যা আছে: 'rat' আর 'tar' এর মতো শব্দগুলো একই লকারে গিয়ে জটলা পাকাবে। তাই djb2 বা FNV-1a এর মতো উন্নত ফাংশনগুলো বিট (bits) নিয়ে একটু বেশি ঘাঁটাঘাঁটি করে ডেটাগুলোকে দারুণভাবে ছড়িয়ে দেয়।

◈ হ্যাশ ফাংশনের ম্যাজিক দেখুন

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

কলিশন বা সংঘর্ষ — যখন দু'জন একই লকারে ঢুকতে চায়

আপনার হ্যাশ ফাংশন যত ভালো আর দামিই হোক না কেন, অনেক বেশি মানুষ বা ডেটা আসলে কলিশন হবেই — অর্থাৎ দুটো আলাদা জিনিস একই লকার নম্বর পেয়ে যাবে। এটা এড়ানোর কোনো উপায় নেই (একে পিজনহোল প্রিন্সিপাল বলে: আপনার লকারের চেয়ে যদি জিনিস বেশি থাকে, তবে কোনো না কোনো লকারে দুই বা তার বেশি জিনিস রাখতে হবেই)।

এই সংঘর্ষ সামলানোর দুটো দারুণ উপায় আছে:

চেইনিং (Chaining) — প্রতিটা লকারের ভেতরে একটা করে লিংকড লিস্ট (Linked List) থাকে; একই লকার নম্বর পেলে জিনিসগুলো একটা আরেকটার পেছনের লিস্টে যোগ হয়ে যায়।
ওপেন অ্যাড্রেসিং (Open Addressing) — যদি দেখে নিজের লকারে আগে থেকেই কেউ বসে আছে, তখন সে আশপাশের খালি জায়গা খুঁজতে থাকে (লিনিয়ার প্রোবিং, কোয়াড্র্যাটিক প্রোবিং বা ডাবল হ্যাশিংয়ের মাধ্যমে)।

লোড ফ্যাক্টর (Load Factor)

লোড ফ্যাক্টর α = n / capacity (এখানে n = মোট রাখা জিনিসের সংখ্যা)। এটা দিয়ে মাপা হয় আপনার টেবিল বা লকারগুলো কতটা ভরে গেছে। α-এর মান যখন অনেক বেড়ে যায়:

চেইনিংয়ের ক্ষেত্রে পেছনের লাইন বা চেইন অনেক লম্বা হয়ে যায়।
ওপেন অ্যাড্রেসিংয়ের ক্ষেত্রে ডেটার বড় বড় জটলা পেকে যায়।
এর ফলে খোঁজার স্পিড O(1) থেকে ধীরে ধীরে O(n)-এর দিকে যেতে থাকে।

বেশিরভাগ ক্ষেত্রেই যখন α-এর মান চেইনিংয়ের জন্য ০.৭৫ (0.75) বা ওপেন অ্যাড্রেসিংয়ের জন্য ০.৫ (0.5) পেরিয়ে যায়, তখন টেবিলের সাইজ ডাবল করে নতুন করে সব ডেটাকে আবার ছড়ানো হয় (যাকে বলে রিহ্যাশিং বা Rehashing)। এই রিহ্যাশিংয়ের কাজে একবার O(n) সময় লাগে বটে, কিন্তু এই একটু আয়েশ করে নেওয়ার ফলে এরপর থেকে আবার স্পিড সেই রকেটের মতোই (O(1)) পাওয়া যায় — ঠিক ডায়নামিক অ্যারে ডাবলিংয়ের মতোই।

দ্রষ্টব্য: সবচেয়ে খারাপ অবস্থা (Worst-case) বা O(n) খোঁজার সময় তখনই লাগে, যখন আপনার হ্যাশ ফাংশন বাজে হওয়ায় সব ডেটা গিয়ে একটা লকারেই ভিড় করে। একটা ভালো হ্যাশ ফাংশন আর ঠিকঠাক লোড ফ্যাক্টর থাকলে বাস্তব জীবনে এমনটা প্রায় কখনোই ঘটে না।