String Hashing

হ্যাশিং: হ্যাশিং একটা টেকনিক যার মাধ্যমে একটা কী(Key) ভ্যালুকে অন্য একটা ভ্যালুতে রূপান্তর করা যায়।
হ্যাশ ফাংশন: নতুন ভ্যালু বের করার যে গাণিতিক পদ্ধতি ব্যবহার করা হয় তাকে হ্যাশ ফাংশন বলে। হ্যাশ ফাংশন থেকে প্রাপ্ত ভ্যালুকে হ্যাশ ভ্যালু/হ্যাশ বলে। ভালো হ্যাশ ফাংশনে নিচের বৈশিষ্টগুলো থাকে-

• ধরি, $X$ এবং $Y$ দুইটি কী(Key) ভ্যালু এবং $F()$ একটি হ্যাশ ফাংশন। এখন $F(X)=F(Y)$ হবে যদি $X=Y$ হয় এবং $X\neq Y$ হলে $F(X)\neq F(Y)$ হবে।
• ব্যবহারিক অর্থে হ্যাশ ভ্যালুর সাইজ যথেষ্ট ছোট হতে হবে।
• হ্যাশ ফাংশন সহজ ও সরল হতে হবে যাতে সহজে হ্যাশ ভ্যালু বের করা যায়।
• হ্যাশ ফাংশন এমন হতে হবে যাতে কলিশন(Collision) হওয়ার সম্ভাবনা কম থাকে।
• একমুখী হ্যাশিং ব্যবহার করতে হবে যাতে নতুন হ্যাশ ভ্যালু থেকে কী(Key) ভ্যালুতে রূপান্তর না করা যায়।

কলিশন: দুইটি ভিন্ন কী(Key) এর জন্য যদি একই হ্যাশ ভ্যালু বের হয়।

ধরি, আমরা এখন একটি স্ট্রিং $S=``ADC"$ এর জন্য হ্যাশ ভ্যালু বের করবো। যেখানে হ্যাশ ফাংশন- $$F(S)= \sum_{i=1}^{N} X_i$$ এখানে $X_i= i$th অ্যালফাবেটের পজিশন এবং অ্যালফাবেট $A,B,C,...,Z$ এর পজিশন যথাক্রমে $1,2,3,...,26$।
$$\therefore F(S) = 1 + 4 + 3 = 8$$ এখন বলতে হবে এই হ্যাশ ফাংশনটি কি ভালো? একটু চিন্তা করলেই বলা যাচ্ছে যে এই হ্যাশ ফাংশনটি ভালো না। কারণ এর কলিশন হওয়ার সম্ভাবনা অনেক বেশি। উক্ত হ্যাশ ফাংশনটি $``ADC"$ এবং $``ACD"$ এর জন্য একই হ্যাশ ভ্যালু দিবে।

অনেক পদ্ধতির হ্যাশ ফাংশন হতে পারে। আমরা নিচে একটি পদ্ধতি নিয়ে কাজ করবো। পদ্ধতিটি হচ্ছে-
ধরি, $N$ সাইজের একটি স্ট্রিং $S = S_1 S_2 ... S_N$ দেওয়া আছে। এখন হ্যাশ ফাংশন-
$$F(S) = \sum_{i=1}^{N} X_i.P^{N-i}$$ এখানে $X_i= i$th অ্যালফাবেটের পজিশন এবং $P=$ বেস ভ্যালু (সাধারণত ব্যবহারিত অ্যালফাবেট সংখ্যার চাইতে বড় একটা প্রাইম নাম্বার নেওয়া হয়)। ধরি, $P=27$, তাহলে $F(``ADC") = 840$ এবং $F(``ACD") = 814$.
কিন্তু এখন প্রব্লেম হচ্ছে যদি স্ট্রিং এর সাইজ অনেক বড় হয় তবে হ্যাশ ভ্যালুও অনেক বড় হয়ে যাবে। ভালো হ্যাশ ফাংশন বানানোর জন্য হ্যাশ ভ্যালু বড় হতে দেওয়া যাবে না। তাই এই প্রব্লেম এর সমাধান হিসেবে আমরা একটা কাজ করতে পারি...হ্যাশ ভ্যালুকে একটা নাম্বার দিয়ে মড করতে পারি। এখন যেকোনো নাম্বার দিয়ে মড করাটা কি Feasible?!
উত্তরটি হচ্ছে 'না'। তাহলে নাম্বারটি কেমন নিবো? এর উত্তর হচ্ছে একটা বড় প্রাইম নাম্বার নিবো। প্রাইম নাম্বার কেন নিবো? Modular Arithmetic নিয়ে আইডিয়া থাকলে এটা খুব সহজেই বুঝা যাবে। আর প্রাইমটা বড় কেন নিবো এবং কত বড় নিবো? - এই দুইটা প্রশ্নের উত্তর এখানে পাওয়া যাবে।
[To Be Continued...]