Հեշ բախումներ (Hash Collisions)
Հեշ ֆունկցիաները կատարյալ չեն. երբեմն տեղի է ունենում, որ միանգամայն տարբեր տվյալներ տալիս են միևնույն հեշ արժեքը։ Սա խախտում է մուտքերի և հեշի միջև één–to–one համապատասխանությունը։ Արդյունքում տարբեր տողեր կարող են ստանալ նույն հեշ արժեքը, կամ երկու թվերի զույգեր կարող են նույն հեշը ունենալ։ Հեշ բախումները (collisions) կարող են դառնալ ինչպես անվտանգության, այնպես էլ արտադրողականության խնդիր, կախված համատեքստից։ Օրինակ, երկու ամբողջ թվերի
(a, b) զույգը հեշի վերածող պարզ հեշ ֆունկցիան կարող է բազմաթիվ (a, b) զույգեր քարտեզավորել նույն արժեքի վրա.Ահա մի քանի օրինակ
(a, b) զույգերի, որոնք տալիս են նույն հեշ արժեքը.- h(1, 1) = (1997 + 1) mod 5077 = 1998
- h(1, 5078) = (1997 + 5078) mod 5077 = 1998
- h(5078, 1) = (10140766 + 1) mod 5077 = 1998
- …
Հետևաբար, եթե ունենանք հատուկ ընտրված
(a, b) զույգերի ցանկ, որոնք բոլորն ունեն նույն հեշը, ապա տվյալների փնտրման կամ (a, b) զույգի առկայությունը ստուգելու գործընթացը շատ անարդյունավետ կլինի կամ անգամ սխալ (կախված իրագործման մանրամասներից)։Հեշ բախումները կարող են նաև անվտանգության խոցելիությունների աղբյուր դառնալ։ Օգտատերերի գաղտնաբառերը սովորաբար պահվում են որպես հեշեր անվտանգության նկատառումներով (որպեսզի նույնիսկ տվյալների շտեմարանի դեմ գործողության դեպքում գաղտնաբառերը չհրապարակվեն)։ Եթե հեշ ֆունկցիան լավագույնը չէ ու բազմաթիվ բախումներ է առաջացնում, ապա կողոպտիչները կարող են կոտրել հաշիվը навіть առանց ճիշտ գաղտնաբառը գուշակելու։ Եթե որևէ պատահական գաղտնաբառի հեշը համընկնի բուն գաղտնաբառի հեշի հետ, համակարգը կընդունի, որ նույն օգտատերն է։
Լավ հեշ ֆունկցիան ապահովում է, որ բախումների քանակը լինի նվազագույն։ Սովորաբար ծրագրային միջավայրի մեջ առկա ներկառուցված հեշ ֆունկցիաները բավականին լավ են աշխատում պատահական մուտքերի դեպքում։ Բայց եթե տվյալների տեսակն առանձին առանձնահատկություններ ունի կամ առաջադրանքը հատուկ պահանջներ ունի, ապա գուցե հարկ լինի գրել հատուկ հեշ ֆունկցիա (custom hashing function)։
Առաջադրանք: Ստուգել բախումները
Ենթադրենք տրված է հեշ ֆունկցիա
h, որը (a, b) integer զույգին համապատասխանեցնում է մեկ ամբողջ թիվ։ Ձեզ խնդրում են գրել ծրագիր, որը ստուգում է, թե արդյոք տվյալ h-ը բավականաչափ լավն է։ Ծրագիրը պետք է ստուգի, կա՞ն արդյոք բախումներ, և եթե ոչ — տպի Yes, իսկ հակառակ դեպքում — No։ Հեշ ֆունկցիան սահմանված է այսպես.Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
n (1 ≤ n ≤ 10 000), որը ցույց է տալիս զույգերի քանակը։Հաջորդ
n տողերում տրվում են ամբողջ թվերի զույգեր a_i, b_i (0 ≤ a_i, b_i ≤ 10^9), առկա է երաշխիք, որ տրված (a_i, b_i) զույգերը միանշանակ են (unique)։Ելք
Ծրագիրը ելքում պետք է տպի
Yes, եթե հեշ ֆունկցիան այս մուտքի համար բախումներ չի առաջացրել, և No հակառակ դեպքում։Օրինակներ
Input | Մուտք |
3
0 4
1 5
2 9 | Yes |
2
0 0
0 1
542313474 3 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB