길이가 다른 두 개의 문자열이 동일한 해시 코드를 가질 수 있습니까?

Question

두 개의 다른 String이 동일한 해시 코드를 반환 할 수 있다는 것을 알고 있지만, 이렇게 다른 길이의 두 가지에 대해서는 아무 것도 찾을 수 없습니다. 이것이 가능한지, 그렇다면 예제가 인정 될 것입니다. 이것은 자바 해시 코드 함수를 사용하고 있습니다.

Answer 1

해시 코드는 int의 공간에 분산되어 있습니다. int에 대해서만 가능한 값은 2^32 = ~4 billion입니다. 그 수보다 더 많은 수의 문자열이 있으므로 비둘기 원칙에 따라 동일한 해시 코드를 가진 여러 문자열이 있어야합니다.

그러나 아래에서 지적한 것과 같이 길이 문자열의 해시 코드가 다를 수 있음을 증명하지는 않습니다. Java는 해시 문자열에 수식 s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]을 사용합니다. 이것을 알면 같은 해시 코드를 가진 길이가 다른 문자열을 쉽게 만들 수 있습니다 :

하자 String s1 = "\001!"; 및 String s2 = "@";을 입력하십시오. 그런 다음 s1.length() != s2.length()이지만 s1.hashCode() == '\001' * 31 + '!' == 1 * 31 + 33 == 64 == s2.hashCode() == '@' == 64입니다.

그러나, 내가 다시 int의000000000 4 이상 사용할 수있는 값이 있다고 가정 해 봅시다 당신이 생각하는 것만 큼 낮은 것은 아니지만, 그래서 충돌의 당신의 가능성은 있음을주는 때문에 Birthday Paradox의, 낮은 약 77K 해시 후에 충돌 가능성이 약 50 %입니다 (해시가 무작위로 분산되어 있다고 가정하면 실제로 데이터에 따라 결정됩니다. 아주 작은 길이의 문자열을 처리하는 경우 자주 충돌이 발생합니다). 해싱 거래를 사용하는 모든 데이터 구조는 충돌을 처리해야하지만 (예 : 일반적인 해쉬 위치에서 연결된 목록 사용) 데이터 손실 (예 : 블룸 필터)을 처리해야합니다.

Answer 2

예. 이런 일이 발생할 수 있습니다.

다소 사소한 예 :

• 초기 문자 그래서, 해시 코드에 영향을주지 않는 등 "\0foo", "\0\0foo", "foo" (예를 들어), 모두가 같은 해시 코드를 제로 값 .
• 다음 문자를 추가하기 전에 각 문자에 31이 곱해집니다. 그래서 예를 들어 두 자로 된 문자열 new String(new char[] { 12, 13 })은 하나의 문자 인 new String(new char[] { 12 * 31 + 13 })과 같은 해시 코드를 가지고 있습니다 (내가 임의로 12과 13을 선택한 경우, 12 * 31 + 13 아날로그가 두 개 이내에있는 한 다른 값에 대해서도 동일하게 작동합니다) -byte-unsigned- 정수 범위).

그러나 이것들은 구성하기 쉬운 몇 가지 예입니다. 심지어 해시 코드가 서로 짝을 지어서도 서로 뚜렷한 관계가 있음에도 불구하고 작동하는 문자열 쌍이 많습니다.