해시 충돌이 문제가되는 시스템에서 작업하고 있습니다. 기본적으로 해시 테이블 + 트리 구조의 항목을 참조하는 시스템이 있습니다. 그러나 문제의 시스템은 먼저 구조의 경로가 들어있는 텍스트 파일을 해시 된 값이 들어있는 바이너리 파일로 컴파일합니다. 이는 성능상의 이유로 수행됩니다. 그러나이 충돌 때문에 구조가 동일한 해시 값을 가진 2 개의 항목을 저장할 수 없으므로 매우 나쁩니다. 항목을 요구하는 부분은 필요한 항목을 알 수있는 정보가 충분하지 않습니다.하나의 32 비트 해시와 두 개의 16 비트 해시간에 충돌 비율 차이가 있습니까?
처음 생각한 것은 두 개의 해시 중 하나가 2 개의 알고리즘을 사용하거나 동일한 알고리즘을 두 번 사용했지만 2 개의 소금은 충돌 저항력이 더 강하다는 것입니다. 서로 다른 해싱 알고리즘에 대해 동일한 해시를 갖는 두 항목은 거의 발생하지 않습니다.
공간상의 이유로 해시 값을 32 비트로 유지하려고하므로 하나의 32 비트 알고리즘 대신 두 개의 16 비트 알고리즘을 사용하도록 전환 할 수 있다고 생각했습니다. 하지만 그 가능한 해시 값의 범위를 늘리지 않을 것이라고 ...
나는 두 개의 32 비트 해시로 전환하는 것이 더 많은 충돌 저항을 알고 있지만 2 16 비트 해시로 전환하는 것이 적어도 일부는지 궁금해. 단일 32 비트 해시를 통해 얻을 수있는 이점은 무엇입니까?
항목이 주어진 이름으로 :
시스템의 일부 배경 ... 내가 가장 수학적으로 사람이 아니에요, 그래서 난 소문 힘 그것보다 다른 대답을 점검 시작하는 방법을 모른다 사람들은 임의의 문자열이 아니며 대개 공백이없는 단어, 문자 및 숫자로 구성됩니다. 중첩 해시 구조이므로 {a => {b => {blah '}}}와 같이 a/b/c의 값을 가져 와서'blah '값을 얻으면 컴파일 된 요청은 즉각적인 순서에서 3 개의 해시 값, a, b 및 c의 해쉬 값이됩니다.
주어진 레벨에서 충돌이있을 때만 문제가 있습니다. 최상위 항목과 하위 항목 간의 충돌이 문제가되지 않습니다. {a => {{a => {{}}}를 가질 수 있으며, 서로 다른 수준의 충돌을 거의 보장합니다 (문제가 아님).
실제로 주어진 레벨은 해시 값이 100 개 미만이며 동일한 레벨에서는 중복되지 않습니다.
내가 채택한 해싱 알고리즘을 테스트하려면 (어느 것을 잊었지만 발명하지 않았다) CPAN Perl 모듈의 전체 목록을 다운로드하고 모든 네임 스페이스/모듈을 고유 한 단어로 분리 한 다음 충돌을 검색하는 각 해시를 해시했습니다. , 나는 0 개의 충돌을 만났다. 이는 알고리즘이 CPAN 네임 스페이스 목록의 각 고유 단어에 대해 다른 해시 값을 가짐을 의미합니다 (또는 잘못 했음). 그것은 나에게 충분히 좋지만, 여전히 내 두뇌에 잔소리가있다.
나는 16 비트 해시 알고리즘을 2 가지 다른 소금 값으로 사용하는 것에 대해 조금 걱정할 것입니다. 두 해시 값은 내재적으로 상관됩니다. –
@IraBaxter 나는 소금을 말했다. 그러나 나는 틀렸다라고 생각한다. 나는 같은 알고리즘을 사용했지만, 두 번째 접두사는 값을 의미했다. 이 알고리즘은 문자열을 슬 루핑하고 "ab"와 "ba"가 다른 값을 가질 때마다 has를 변경하는 각 문자를 반복합니다. 그리고 두 번째 실행에 값을 접두어로 붙이는 동일한 문자열 (충돌 지점)에 대한 충돌에 대해 걱정할 필요가 없으므로 첫 번째 실행 후 동일한 해시를 가진 두 항목에 대해 두 번째 실행에 다른 해시를 갖기에 충분해야합니다 . (그런 다음 다시 확인해야 할 것입니다.) – Exodist
@ ira-baxter : 해시 알고리즘이 암호로 안전하다면 그러한 상관 관계가 없어야합니다. 그러나 그것은 무시되어서는 안된다. – btilly