এখানে আমরা বিভাজনের সাথে হ্যাশিং সম্পর্কে আলোচনা করব। এর জন্য আমরা হ্যাশ ফাংশন −
ব্যবহার করিℎ(𝑥) = 𝑥 𝑚𝑜𝑑 𝑚
এই হ্যাশ ফাংশনটি ব্যবহার করার জন্য আমরা একটি অ্যারে A[0, … m – 1] বজায় রাখি। যেখানে অ্যারের প্রতিটি উপাদান লিঙ্ক করা তালিকার মাথার একটি পয়েন্টার। লিংকড লিস্ট লি অ্যারে এলিমেন্টের দিকে নির্দেশ করা হয়েছে A[i] সমস্ত উপাদান x ধারণ করে যেমন h(x) =i। এই কৌশলটি চেইনিং দ্বারা হ্যাশিং নামে পরিচিত।
এই ধরনের হ্যাশ টেবিলে, যদি আমরা একটি এলিমেন্ট x বাড়াতে চাই, তাহলে O(1) সময় লাগবে। আমরা সূচক i =h(x) গণনা করি। তারপর লিস্টে x যোগ করুন বা প্রিপেন্ড করুন। আমরা যদি একটি উপাদান অনুসন্ধান বা মুছে ফেলতে চাই, সেই প্রক্রিয়াটি এত সহজ নয়। আমাদের সূচক i =h(x) খুঁজে বের করতে হবে। তারপর ট্রাভার্স লিস্ট লি. যতক্ষণ না আমরা পছন্দসই মূল্যে পৌঁছাই বা তালিকাটি শেষ না হয়। এই ক্রিয়াকলাপটি Li তালিকার আকারের সাথে সামঞ্জস্যপূর্ণ সময় নিচ্ছে৷ . যদি আমাদের সেট S-এ 0, m, 2m, 3m, ...., nm উপাদান থাকে, তাহলে L0 তে সংরক্ষিত সমস্ত উপাদান অনুসন্ধান এবং মুছে ফেলতে রৈখিক সময় নেবে।
এই ধরনের পরিস্থিতি খুবই বিরল৷ উদাহরণস্বরূপ, যদি S সার্বজনীন সেট U-এ সমানভাবে এবং স্বাধীনভাবে বিতরণ করা হয় এবং u m-এর গুণিতক হয়, তাহলে প্রতিটি তালিকার প্রত্যাশিত আকার Li মাত্র n/m. এই ক্ষেত্রে অনুসন্ধান এবং মুছে ফেলার জন্য O লাগে৷ (1 + α) সময়ের পরিমাণ। উল্লিখিত দৃশ্যকল্প এড়াতে, আমাদের বিজ্ঞতার সাথে m নির্বাচন করতে হবে। সাধারণত, আমরা m কে 2 এর শক্তি হিসাবে এড়িয়ে চলে। m কে প্রাইম হিসাবে নেওয়া যা 2 এর পাওয়ারের খুব কাছাকাছি নয়।
