Hash collision
કોમ્પ્યુટર વિજ્ઞાનમાં, હેશ અથડામણ અથવા હેશ અથડામણ ત્યારે થાય છે જ્યારે હેશ ટેબલમાં ડેટાના બે ટુકડાઓ સમાન હેશ મૂલ્ય વહેંચે છે. આ કિસ્સામાં હેશ મૂલ્ય હેશ કાર્યમાંથી મેળવવામાં આવે છે જે ડેટા ઇનપુટ લે છે અને બિટ્સની નિશ્ચિત લંબાઈ આપે છે. જો કે હેશ અલ્ગોરિધમ્સ અથડામણ પ્રતિરોધક હોવાના ઉદ્દેશ સાથે બનાવવામાં આવ્યા છે, તેમ છતાં તેઓ કેટલીકવાર સમાન હેશ (કબૂતર છિદ્ર સિદ્ધાંતના આધારે) પર વિવિધ ડેટાનો નકશો બનાવી શકે છે. દુર્ભાવનાપૂર્ણ વપરાશકર્તાઓ ડેટાની નકલ કરવા, ઍક્સેસ કરવા અથવા તેમાં ફેરફાર કરવા માટે આનો લાભ લઈ શકે છે. ડેટા મેનેજમેન્ટ અને કમ્પ્યુટર સુરક્ષામાં હેશ અથડામણની સંભવિત નકારાત્મક એપ્લિકેશનોને કારણે (ખાસ કરીને, ક્રિપ્ટોગ્રાફિક હેશ કાર્યો), કોમ્પ્યુટર સુરક્ષામાં અથડામણ ટાળવી એ એક મહત્વપૂર્ણ વિષય બની ગયો છે. બેકગ્રાઉન્ડ હેશ અથડામણ સેટમાં વસ્તુઓની સંખ્યાના આધારે અનિવાર્ય હોઈ શકે છે અને તેઓ જે બીટ સ્ટ્રિંગ પર મેપ કરવામાં આવે છે તે લંબાઈમાં પૂરતી લાંબી છે કે નહીં. જ્યારે n પદાર્થોનો સમૂહ હોય, જો n |R | કરતા વધારે હોય, જે આ કિસ્સામાં R એ હેશ મૂલ્યની શ્રેણી છે, તો હેશ અથડામણ થવાની સંભાવના 1 છે, એટલે કે તે થવાની ખાતરી છે. હેશ અથડામણનું અન્ય એક કારણ અમુક સમયે ગણિતમાં જન્મદિવસના વિરોધાભાસના વિચારમાંથી ઉદ્ભવે છે. આ સમસ્યા બે અવ્યવસ્થિત રીતે પસંદ કરાયેલા લોકોના સમૂહની સંભાવના જુએ છે જેનો જન્મદિવસ n સંખ્યામાં લોકોમાંથી એક જ હોય છે. આ વિચારને કારણે જન્મદિવસનો હુમલો થયો છે. આ હુમલાનો આધાર એ છે કે ખાસ કરીને તમારા જન્મદિવસ અથવા ચોક્કસ જન્મદિવસ સાથે મેળ ખાતો જન્મદિવસ શોધવો મુશ્કેલ છે, પરંતુ મેળ ખાતા જન્મદિવસવાળા કોઈપણ બે લોકોનો સમૂહ શોધવાની સંભાવના સંભાવનામાં ઘણો વધારો કરે છે. ખરાબ અભિનેતાઓ આ અભિગમનો ઉપયોગ તેમના માટે કોઈ ચોક્કસ મૂલ્ય શોધવાને બદલે અન્ય કોઈપણ હેશ મૂલ્ય સાથે ટકરાતા હેશ મૂલ્યોને શોધવાનું સરળ બનાવવા માટે કરી શકે છે. અથડામણની અસર અરજી પર આધારિત છે. જ્યારે હેશ ફંક્શન્સ અને ફિંગરપ્રિન્ટ્સનો ઉપયોગ સમાન ડેટાને ઓળખવા માટે કરવામાં આવે છે, જેમ કે હોમોલોગસ ડીએનએ સિક્વન્સ અથવા સમાન ઑડિઓ ફાઇલો, ત્યારે કાર્યોની રચના કરવામાં આવે છે જેથી સ્થાન-સંવેદનશીલ હેશિંગ જેવી તકનીકોનો ઉપયોગ કરીને અલગ પરંતુ સમાન ડેટા વચ્ચે અથડામણની સંભાવનાને મહત્તમ કરી શકાય. બીજી બાજુ, ચેકસમ, ખૂબ જ અલગ ઇનપુટ્સ વચ્ચે અથડામણને ધ્યાનમાં લીધા વિના, સમાન ઇનપુટ્સ વચ્ચે અથડામણની સંભાવનાને ઘટાડવા માટે રચાયેલ છે. એવા ઉદાહરણો કે જ્યાં ખરાબ અભિનેતાઓ હેશ અથડામણ બનાવવાનો અથવા શોધવાનો પ્રયાસ કરે છે તે અથડામણ હુમલા તરીકે ઓળખાય છે. વ્યવહારમાં, સુરક્ષા-સંબંધિત એપ્લિકેશનો ક્રિપ્ટોગ્રાફિક હેશ અલ્ગોરિધમ્સનો ઉપયોગ કરે છે, જે રેન્ડમ મેચો અસંભવિત હોય તેટલા લાંબા સમય સુધી રચાયેલ છે, એટલા ઝડપી છે કે તેનો ઉપયોગ ગમે ત્યાં થઈ શકે છે, અને એટલા સુરક્ષિત છે કે અથડામણ શોધવાનું અત્યંત મુશ્કેલ હશે. હેશ અથડામણ થવાની સંભાવના તક દ્વારા થઇ શકે છે અને ઘણા હેશ અલ્ગોરિધમ્સ માટે ઇરાદાપૂર્વક બનાવી શકાય છે. હેશ અથડામણની સંભાવના આમ અલ્ગોરિધમનો કદ, હેશ મૂલ્યોના વિતરણ અને તે ગાણિતિક રીતે જાણીતું છે કે નહીં અને ચોક્કસ અથડામણ બનાવવા માટે ગણતરીત્મક રીતે શક્ય છે કે નહીં તેના પર આધાર રાખે છે. નીચેના હેશ અલ્ગોરિધમ્સને ધ્યાનમાં લો-CRC-32, ND5 અને SHA-1. અથડામણના જોખમના વિવિધ સ્તરો સાથે આ સામાન્ય હેશ અલ્ગોરિધમ્સ છે. CRC-32 CRC-32 હેશ અથડામણ માટે સૌથી વધુ જોખમ ઊભું કરે છે. આ હેશ કાર્ય સામાન્ય રીતે ઉપયોગ માટે આગ્રહણીય નથી. જો હબમાં 77,163 હેશ મૂલ્યો હોય, તો હેશ અથડામણ થવાની સંભાવના 50 ટકા છે, જે અન્ય પદ્ધતિઓની તુલનામાં અત્યંત વધારે છે. એમ. ડી. 5 એમ. ડી. 5 એ સૌથી વધુ ઉપયોગમાં લેવાય છે અને જ્યારે અન્ય બે હેશ કાર્યોની સરખામણી કરવામાં આવે છે, ત્યારે તે હેશ અથડામણના જોખમની દ્રષ્ટિએ મધ્યમ જમીનનું પ્રતિનિધિત્વ કરે છે. હેશ અથડામણ થવાની 50 ટકા તક મેળવવા માટે, હબમાં 5.6 અબજથી વધુ રેકોર્ડ્સ હોવા જોઈએ. SHA-1 SHA-1 હેશ અથડામણ માટે સૌથી ઓછું જોખમ આપે છે. SHA-1 કાર્ય માટે હેશ અથડામણ થવાની 50 ટકા તક હોય, તો કેન્દ્રમાં 1.42×10 રેકોર્ડ હોવા જોઈએ. નોંધ લો, આ ઉદાહરણોમાં ઉલ્લેખિત રેકોર્ડ્સની સંખ્યા એક જ હબમાં હોવી જોઈએ. ઓછી સંખ્યામાં રેકોર્ડ્સ ધરાવતું કેન્દ્ર હોવું આ તમામ હેશ કાર્યોમાં હેશ અથડામણની સંભાવનાને ઘટાડી શકે છે, જો કે ત્યાં હંમેશા એક નાનું જોખમ હાજર રહેશે, જે અનિવાર્ય છે, જ્યાં સુધી અથડામણ નિવારણ તકનીકોનો ઉપયોગ કરવામાં ન આવે. હેશ અથડામણ અનિવાર્ય હોવાથી, હેશ કોષ્ટકોમાં તેમની સાથે વ્યવહાર કરવાની પદ્ધતિઓ હોય છે, જેને અથડામણના ઠરાવ તરીકે ઓળખવામાં આવે છે. બે સૌથી સામાન્ય વ્યૂહરચનાઓ ખુલ્લી સંબોધન અને અલગ સાંકળ છે. કેશ-સભાન અથડામણ રીઝોલ્યુશન એ બીજી વ્યૂહરચના છે જેની ભૂતકાળમાં સ્ટ્રિંગ હેશ કોષ્ટકો માટે ચર્ચા કરવામાં આવી છે. હેશ કોષ્ટકમાં ઓપન એડ્રેસિંગ સેલ્સને આ પદ્ધતિમાં ત્રણ સ્થિતિઓમાંથી એક સોંપવામાં આવે છે-ઓક્યુપાઇડ, ખાલી અથવા કાઢી નાખવામાં આવે છે. જો હેશ અથડામણ થાય છે, તો રેકોર્ડને વૈકલ્પિક કોષમાં ખસેડવા માટે ટેબલની તપાસ કરવામાં આવશે જે ખાલી હોવાનું કહેવાય છે. જ્યારે હેશ અથડામણ થાય છે અને આ પદ્ધતિ લાગુ કરવામાં આવે છે ત્યારે વિવિધ પ્રકારની તપાસ થાય છે. પ્રોબિંગના કેટલાક પ્રકારો રેખીય પ્રોબિંગ, ડબલ હેશિંગ અને ક્વાડ્રેટિક પ્રોબિંગ છે. ઓપન એડ્રેસિંગને ક્લોઝ્ડ હેશિંગ તરીકે પણ ઓળખવામાં આવે છે. અલગ સાંકળ આ વ્યૂહરચના એક કરતાં વધુ રેકોર્ડને હેશ ટેબલના કોષોમાં "સાંકળ" કરવાની મંજૂરી આપે છે. જો બે રેકોર્ડ્સને એક જ કોષમાં નિર્દેશિત કરવામાં આવે, તો બંને તે કોષમાં જોડાયેલી સૂચિ તરીકે જશે. આ હેશ અથડામણને અસરકારક રીતે અટકાવે છે કારણ કે સમાન હેશ મૂલ્યો સાથેના રેકોર્ડ્સ સમાન કોષમાં જઈ શકે છે, પરંતુ તેના ગેરફાયદા છે. આટલી બધી યાદીઓનો ટ્રેક રાખવો મુશ્કેલ છે અને જે પણ સાધનનો ઉપયોગ કરવામાં આવી રહ્યો છે તે ખૂબ જ ધીમું થઈ શકે છે. અલગ ચેનિંગને ઓપન હેશિંગ તરીકે પણ ઓળખવામાં આવે છે. કેશ-સભાન અથડામણ રીઝોલ્યુશન અગાઉના બે કરતા ઘણું ઓછું ઉપયોગમાં લેવાયું હોવા છતાં, 2005 માં કેશ-સભાન અથડામણ રીઝોલ્યુશન પદ્ધતિનો પ્રસ્તાવ મૂક્યો છે. તે અલગ સાંકળ પદ્ધતિઓનો સમાન વિચાર છે, જો કે તેમાં તકનીકી રીતે સાંકળવાળી યાદીઓનો સમાવેશ થતો નથી. આ કિસ્સામાં, સાંકળવાળી સૂચિને બદલે, હેશ મૂલ્યો વસ્તુઓની સંલગ્ન સૂચિમાં રજૂ થાય છે. આ શબ્દમાળા હેશ કોષ્ટકો માટે વધુ યોગ્ય છે અને આંકડાકીય મૂલ્યો માટેનો ઉપયોગ હજુ પણ અજ્ઞાત છે. આ પણ જુઓ હેશ કાર્યોની યાદી સંદર્ભો બાહ્ય કડીઓ હેશિંગ