Hash collision
কম্পিউটার বিজ্ঞানে, একটি হ্যাশ সংঘর্ষ বা হ্যাশ সংঘর্ষ হল যখন একটি হ্যাশ টেবিলের দুটি ডেটা একই হ্যাশ মান ভাগ করে নেয়। এই ক্ষেত্রে হ্যাশ মান একটি হ্যাশ ফাংশন থেকে উদ্ভূত হয় যা একটি ডেটা ইনপুট নেয় এবং বিটের একটি নির্দিষ্ট দৈর্ঘ্য প্রদান করে। যদিও হ্যাশ অ্যালগরিদমগুলি সংঘর্ষ প্রতিরোধী হওয়ার অভিপ্রায় নিয়ে তৈরি করা হয়েছে, তবুও তারা কখনও কখনও একই হ্যাশে বিভিন্ন তথ্যের মানচিত্র তৈরি করতে পারে (পায়রা ছিদ্র নীতির ভিত্তিতে)। বিদ্বেষপূর্ণ ব্যবহারকারীরা ডেটা নকল করতে, অ্যাক্সেস করতে বা পরিবর্তন করতে এর সুবিধা নিতে পারে। ডেটা ম্যানেজমেন্ট এবং কম্পিউটার নিরাপত্তায় হ্যাশ সংঘর্ষের সম্ভাব্য নেতিবাচক প্রয়োগের কারণে (বিশেষত, ক্রিপ্টোগ্রাফিক হ্যাশ ফাংশন), সংঘর্ষ এড়ানো কম্পিউটার নিরাপত্তায় একটি গুরুত্বপূর্ণ বিষয় হয়ে উঠেছে। ব্যাকগ্রাউন্ড হ্যাশ সংঘর্ষগুলি একটি সেটের বস্তুর সংখ্যা এবং তাদের ম্যাপ করা বিট স্ট্রিং দৈর্ঘ্যে যথেষ্ট দীর্ঘ কিনা তার উপর নির্ভর করে অনিবার্য হতে পারে। যখন n বস্তুর একটি সেট থাকে, যদি n |R। এর চেয়ে বড় হয়, যা এই ক্ষেত্রে R হ্যাশ মানের পরিসীমা, একটি হ্যাশ সংঘর্ষ হওয়ার সম্ভাবনা 1, যার অর্থ এটি ঘটবে বলে নিশ্চিত করা হয়। হ্যাশ সংঘর্ষের আরেকটি কারণ সম্ভবত কোনও সময়ে গণিতে জন্মদিনের প্যারাডক্সের ধারণা থেকে উদ্ভূত হয়। এই সমস্যাটি n সংখ্যক মানুষের মধ্যে এলোমেলোভাবে নির্বাচিত দু 'জনের একই জন্মদিন হওয়ার সম্ভাবনার দিকে নজর দেয়। এই ধারণাটি জন্মদিনের আক্রমণের দিকে পরিচালিত করেছে। এই আক্রমণের ভিত্তি হল যে আপনার জন্মদিন বা একটি নির্দিষ্ট জন্মদিনের সাথে বিশেষভাবে মেলে এমন একটি জন্মদিন খুঁজে পাওয়া কঠিন, তবে মিলযুক্ত জন্মদিনের সাথে যে কোনও দু 'জনের একটি সেট খুঁজে পাওয়ার সম্ভাবনা সম্ভাবনাকে ব্যাপকভাবে বাড়িয়ে তোলে। খারাপ অভিনেতারা একটি নির্দিষ্ট মান অনুসন্ধানের পরিবর্তে অন্য কোনও হ্যাশ মানের সাথে সংঘর্ষ করা হ্যাশ মানগুলি খুঁজে পাওয়া সহজ করার জন্য এই পদ্ধতিটি ব্যবহার করতে পারেন। সংঘর্ষের প্রভাব প্রয়োগের উপর নির্ভর করে। যখন হ্যাশ ফাংশন এবং আঙুলের ছাপগুলি অনুরূপ ডেটা সনাক্ত করতে ব্যবহার করা হয়, যেমন সমজাতীয় ডিএনএ সিকোয়েন্স বা অনুরূপ অডিও ফাইল, ফাংশনগুলি এমনভাবে ডিজাইন করা হয় যাতে স্থানীয়-সংবেদনশীল হ্যাশিংয়ের মতো কৌশলগুলি ব্যবহার করে স্বতন্ত্র কিন্তু অনুরূপ ডেটার মধ্যে সংঘর্ষের সম্ভাবনা সর্বাধিক করা যায়। অন্যদিকে, চেকসামগুলি খুব ভিন্ন ইনপুটগুলির মধ্যে সংঘর্ষের বিষয়টি বিবেচনা না করে অনুরূপ ইনপুটগুলির মধ্যে সংঘর্ষের সম্ভাবনা হ্রাস করার জন্য ডিজাইন করা হয়েছে। যে উদাহরণগুলিতে খারাপ অভিনেতারা হ্যাশ সংঘর্ষ তৈরি বা খুঁজে বের করার চেষ্টা করে সেগুলি সংঘর্ষ আক্রমণ হিসাবে পরিচিত। বাস্তবে, নিরাপত্তা-সম্পর্কিত অ্যাপ্লিকেশনগুলি ক্রিপ্টোগ্রাফিক হ্যাশ অ্যালগরিদম ব্যবহার করে, যা র্যান্ডম ম্যাচগুলি অসম্ভব হওয়ার জন্য যথেষ্ট দীর্ঘ, এত দ্রুত যে সেগুলি যে কোনও জায়গায় ব্যবহার করা যেতে পারে এবং এত নিরাপদ যে সংঘর্ষগুলি খুঁজে পাওয়া অত্যন্ত কঠিন হবে। হ্যাশ সংঘর্ষের সম্ভাব্যতা কাকতালীয়ভাবে ঘটতে পারে এবং অনেক হ্যাশ অ্যালগরিদমের জন্য ইচ্ছাকৃতভাবে তৈরি করা যেতে পারে। হ্যাশ সংঘর্ষের সম্ভাবনা এইভাবে নির্ভর করে অ্যালগরিদমের আকার, হ্যাশ মানগুলির বিতরণ এবং নির্দিষ্ট সংঘর্ষ তৈরি করা গাণিতিকভাবে জানা এবং গণনামূলকভাবে সম্ভব কিনা তার উপর। নিম্নলিখিত হ্যাশ অ্যালগরিদমগুলি বিবেচনা করুন-সিআরসি-32, এমডি5 এবং এসএইচএ-1। এগুলি সংঘর্ষের ঝুঁকির বিভিন্ন স্তর সহ সাধারণ হ্যাশ অ্যালগরিদম। সিআরসি-32 সিআরসি-32 হ্যাশ সংঘর্ষের জন্য সর্বোচ্চ ঝুঁকি তৈরি করে। এই হ্যাশ ফাংশনটি সাধারণত ব্যবহারের জন্য সুপারিশ করা হয় না। যদি একটি হাব 77,163 হ্যাশ মান ধারণ করে, হ্যাশ সংঘর্ষের সম্ভাবনা 50 শতাংশ, যা অন্যান্য পদ্ধতির তুলনায় অত্যন্ত বেশি। এম. ডি. 5 এম. ডি. 5 সবচেয়ে বেশি ব্যবহৃত হয় এবং অন্যান্য দুটি হ্যাশ ফাংশনের তুলনায় এটি হ্যাশ সংঘর্ষের ঝুঁকির দিক থেকে মধ্যম স্থলকে উপস্থাপন করে। হ্যাশ সংঘর্ষের 50 শতাংশ সম্ভাবনা পেতে হলে হাবটিতে 5.6 কোটিরও বেশি রেকর্ড থাকতে হবে। এসএইচএ-1 এসএইচএ-1 হ্যাশ সংঘর্ষের জন্য সর্বনিম্ন ঝুঁকি প্রদান করে। একটি এসএইচএ-1 ফাংশনের হ্যাশ সংঘর্ষের 50 শতাংশ সম্ভাবনা থাকার জন্য, হাবটিতে 1.42x10 রেকর্ড থাকতে হবে। লক্ষ্য করুন, এই উদাহরণগুলিতে উল্লিখিত নথির সংখ্যা একই কেন্দ্রে থাকতে হবে। কম সংখ্যক রেকর্ড সহ একটি হাব থাকা এই সমস্ত হ্যাশ ফাংশনে হ্যাশ সংঘর্ষের সম্ভাবনা হ্রাস করতে পারে, যদিও সর্বদা একটি ছোটখাটো ঝুঁকি উপস্থিত থাকবে, যা অনিবার্য, যদি না সংঘর্ষ সমাধান কৌশল ব্যবহার করা হয়। সংঘর্ষের সমাধান যেহেতু হ্যাশ সংঘর্ষ অনিবার্য, হ্যাশ টেবিলগুলির তাদের মোকাবেলা করার প্রক্রিয়া রয়েছে, যা সংঘর্ষের সমাধান হিসাবে পরিচিত। দুটি সবচেয়ে সাধারণ কৌশল হল ওপেন অ্যাড্রেসিং এবং পৃথক চেইনিং। ক্যাশ-সচেতন সংঘর্ষের সমাধান আরেকটি কৌশল যা স্ট্রিং হ্যাশ টেবিলের জন্য অতীতে আলোচনা করা হয়েছে। হ্যাশ টেবিলে খোলা অ্যাড্রেসিং সেলগুলি এই পদ্ধতিতে তিনটি অবস্থার মধ্যে একটি বরাদ্দ করা হয়-দখল, খালি বা মুছে ফেলা। যদি একটি হ্যাশ সংঘর্ষ ঘটে, তবে রেকর্ডটি একটি বিকল্প কক্ষে নিয়ে যাওয়ার জন্য টেবিলটি পরীক্ষা করা হবে যা খালি বলে উল্লেখ করা হয়েছে। যখন একটি হ্যাশ সংঘর্ষ ঘটে এবং এই পদ্ধতিটি প্রয়োগ করা হয় তখন বিভিন্ন ধরনের তদন্ত হয়। কিছু ধরনের প্রোবিং হল রৈখিক প্রোবিং, ডাবল হ্যাশিং এবং চতুর্ভুজ প্রোবিং। ওপেন অ্যাড্রেসিং ক্লোজড হ্যাশিং নামেও পরিচিত। পৃথক চেইনিং এই কৌশলটি একাধিক রেকর্ডকে হ্যাশ টেবিলের কোষে "চেইন" করার অনুমতি দেয়। যদি দুটি রেকর্ড একই কোষে পাঠানো হয়, তবে উভয়ই একটি সংযুক্ত তালিকা হিসাবে সেই কোষে যাবে। এটি দক্ষতার সাথে একটি হ্যাশ সংঘর্ষ ঘটতে বাধা দেয় কারণ একই হ্যাশ মান সহ রেকর্ডগুলি একই কোষে যেতে পারে, তবে এর অসুবিধা রয়েছে। এতগুলি তালিকার উপর নজর রাখা কঠিন এবং যে কোনও সরঞ্জাম ব্যবহার করা হচ্ছে তা খুব ধীর হয়ে যেতে পারে। পৃথক চেইনিং ওপেন হ্যাশিং নামেও পরিচিত। ক্যাশ-সচেতন সংঘর্ষ সমাধান যদিও আগের দুটির তুলনায় অনেক কম ব্যবহৃত হয়েছে, 2005 সালে ক্যাশ-সচেতন সংঘর্ষ সমাধান পদ্ধতির প্রস্তাব দেওয়া হয়েছে। এটি পৃথক চেইনিং পদ্ধতির অনুরূপ ধারণা, যদিও এটি প্রযুক্তিগতভাবে চেইনযুক্ত তালিকাগুলিকে জড়িত করে না। এই ক্ষেত্রে, শৃঙ্খলিত তালিকার পরিবর্তে, হ্যাশ মানগুলি আইটেমগুলির একটি সংলগ্ন তালিকায় উপস্থাপিত হয়। এটি স্ট্রিং হ্যাশ টেবিলের জন্য আরও উপযুক্ত এবং সংখ্যাসূচক মানগুলির ব্যবহার এখনও অজানা। আরও দেখুন হ্যাশ ফাংশনের তালিকা রেফারেন্স বাহ্যিক লিঙ্ক হ্যাশিং