Hash Function

Domain অসীম, codomain সসীম → [[injective]] হওয়া অসম্ভব → collision আছেই। প্রশ্ন শুধু কতটা সমানভাবে ছড়ায়।

Birthday bound: N টা সম্ভাব্য মানে প্রায় 1.177√N টা input-এই ৫০% সম্ভাবনায় collision।

আকার	৫০% collision-এ
32 bit	~৭৭,০০০
64 bit	5×10⁹
256 bit	4×10³⁸

তাই cryptographic hash-এর collision resistance তার আকারের অর্ধেক — SHA-256 দেয় ১২৮ bit, ২৫৬ নয়।

ভালো আর খারাপ hash:

def bad(s):  return sum(ord(c) for c in s)      # সব anagram collide
def good(s):
    h = 0
    for c in s: h = (h * 31 + ord(c)) & 0xFFFFFFFF
    return h

31 কেন — মৌলিক, বিজোড়, আর 31*h == (h<<5) - h।

Hash flooding: Java-র "Aa".hashCode() == "BB".hashCode()। ইচ্ছাকৃত collision দিয়ে hash table-কে O(n²)-এ নামিয়ে DoS করা যায়। প্রতিকার — hash randomization (প্রতি process-এ random seed), যে কারণে Python-এ string-এর hash() প্রতি run-এ বদলায়।

“ভালো” প্রসঙ্গভেদে বদলায়: hash table চায় সমান বণ্টন, cryptographic hash চায় collision খোঁজা অবাস্তব, perceptual hash চায় একই রকম input একই hash পাক — সেখানে collision কাম্য।