ডেটা স্ট্রাকচারে বিভাজন পদ্ধতিতে হ্যাশিং

এখানে আমরা বিভাজন পদ্ধতিতে হ্যাশিং নিয়ে আলোচনা করব। এর জন্য হ্যাশ ফাংশন:

h(x) = x mod m

এই হ্যাশ ফাংশন ব্যবহার করার জন্য আমরা একটি অ্যারে A[0, …, m-1] বজায় রাখি। অ্যারের প্রতিটি উপাদান একটি লিঙ্কড লিস্টের হেডের পয়েন্টার। লিঙ্কড লিস্ট Li যেটি অ্যারে উপাদান A[i]-এর দ্বারা নির্দেশিত, সেটি उन সব x কে ধারণ করে যাতে h(x) = i। এই কৌশলকে চেইনিং দ্বারা হ্যাশিং বলা হয়।

এই ধরনের হ্যাশ টেবিলে, একটি উপাদান x যোগ করতে O(1) সময় লাগে। আমরা ইনডেক্স i = h(x) গণনা করি। তারপর x কে লিস্ট Li-তে যুক্ত করি। যদি আমরা কোনো উপাদান খুঁজতে বা মুছতে চাই, তবে প্রক্রিয়াটি তত সহজ নয়। আমরা ইনডেক্স i = h(x) খুঁজে বের করি। তারপর লিস্ট Li-তে ট্রাভার্স করি। যতক্ষণ না আমরা পছন্দের মান পাই অথবা লিস্টটি শেষ হয়। এই অপারেশনটি লিস্ট Li-এর আকারের সাথে অনুপাতিক সময় নেয়। যদি আমাদের সেট S-তে 0, m, 2m, 3m, …, nm উপাদান থাকে, তবে সব উপাদান L0-তে সংরক্ষিত থাকবে এবং সেগুলি খুঁজে বের করতে এবং মুছতে লিনিয়ার সময় লাগবে।

এই ধরনের পরিস্থিতি খুব কম ঘটে। উদাহরণস্বরূপ, যদি S യূনিভার্সেল সেট U-তে সমানভাবে ও স্বাধীনভাবে বিতরণ করা থাকে, এবং u, m-এর গুণিতক হয়, তবে প্রতিটি লিস্ট Li-এর প্রত্যাশিত আকার শুধু n/m। এই ক্ষেত্রে খুঁজে বের করা এবং মুছে ফেলা O(1 + α) সময় নেয়। উল্লিখিত পরিস্থিতি এড়াতে, আমাদের m বুদ্ধিমানভাবে বেছে নিতে হবে। সাধারণত m কে 2-এর ঘাত হিসেবে এড়ানো হয়। 2-এর ঘাতের খুব কাছাকাছি না এমন একটি মৌলিক সংখ্যা m হিসেবে নেওয়া সুপারিশ করা হয়।