각 20 ~ 60 바이트의 고유 한 ASCII 텍스트 문자열이 ~ 35000 개 있습니다. 나는 그것들 안에 유일한 색인을 소개하고 싶다. 단순히 번호를 매기는 것은 여러 가지 이유로 바람직하지 않습니다.중간 강도의 해시 함수 찾기
MD5와 같은 암호화 등급 기능은 정상적으로 작동하지만 과장이라고 생각합니다. 이것은 궁극적으로 모바일 프로젝트를위한 것이기 때문에 저는 스토리지와 CPU 사이클 모두에 대해 다소 욕심이납니다. 반면에 32 비트 Adler32를 시도하고 충돌이 발생했습니다.
누구나 64 비트 값을 생성하는 좋은 해시 함수를 생각할 수 있습니까?
64 비트 MurmurHash64B에 정착 됨. purry 울리는 이름에 대한 추가 포인트.
문자열 세트가 고정되어 있기 때문에 충돌이 발생하지 않도록 데이터 세트에 대해 특별히 설계된 해시 함수 인 perfect hash function을 찾아야합니다. 이 중 하나 인 gperf (혼동하지 말아야 gprof)과 같은 해시 함수를 만드는 데 사용할 수있는 도구가 많이 있습니다. 무료로 사용할 수 있습니다. 나는 이것을 강력히 제안 할 것이다.
나중에 문자열 세트를 변경해야하며 가볍고 간단한 해시 함수가 필요하면 Rabin-Karp rolling hash function을 사용하는 것이 좋습니다. O (n) 덧셈, 곱셈 및 모듈러스를 사용하여 길이가 n 인 문자열에 대해 계산할 수 있으며 각 두 문자열에 쌍 독립적 해시 값이 있음을 보장합니다. 또한, Adler 체크섬보다 성능이 좋은지 여부를 테스트하기 위해 약 30 분 내에 코드를 작성할 수 있습니다.
즉, MD5와 같은 잘 알려진 해시 함수를 사용하면 암호화 보안을 얻으 려하지 않는 것이 좋습니다. 이 경우 간단한 CRC32조차도 충분할 수 있습니다.
MD4가 암호로 깨졌지만 MD5보다 빠릅니다. Fowler-Noll-Vo는 좋은 비 암호 해시 함수입니다. – rossum
64 비트에서 128 비트로 갈수록 충돌 가능성이 크게 줄어들 기 때문에 MD5128을 사용하는 것이 좋습니다.
Max entries before X chance of collision
Bits 10e−18 10e−15 10e−12 10e−9 10e−6 0.1% 1% 25% 50% 75%
----------------------------------------------------------------------------------------------
16 2 2 2 2 2 11 36 1.9e2 3.0e2 4.3e2
32 2 2 2 2.9 93 2.9e3 9.3e3 5.0e4 7.7e4 1.1e5
64 6.1 1.9e2 6.1e3 1.9e5 6.1e6 1.9e8 6.1e8 3.3e9 5.1e9 7.2e9
128 2.6e10 8.2e11 2.6e13 8.2e14 2.6e16 8.3e17 2.6e18 1.4e19 2.2e19 3.1e19
256 4.8e29 1.5e31 4.8e32 1.5e34 4.8e35 1.5e37 4.8e37 2.6e38 4.0e38 5.7e38
384 8.9e48 2.8e50 8.9e51 2.8e53 8.9e54 2.8e56 8.9e56 4.8e57 7.4e57 1.0e58
512 1.6e68 5.2e69 1.6e71 5.2e72 1.6e74 5.2e75 1.6e76 8.8e76 1.4e77 1.9e77
128 비트로 증가하면 (10 억 억 달러) 1에서 상당히 줄어 듭니다.
물론 문자열 집합은 정적이므로 질문자는 64 비트 해시를 실행할 수 있습니다. 십억의 가능성으로 데이터 세트에 충돌이있는 경우 소금을 넣고 다시 시도하십시오. 이 두 번째 시도는 128 비트로 늘어나지 않고 10 억에 1로 확률을 늘립니다. 두 번째 소금을 시도 할 수있는 용량은 10 억 큐브가 될 것이므로 공격자가 35k 문자열을 선택하지 않는 한 알맞은 분배의 비 암호화 해시를 사용해도 소리가납니다. –
스티브가 말한 것. –
@Steve 당신이 그렇게 멀리 간다면 32 비트 해시로 줄일 수 있습니다. 그것은 충돌 할 확률이 20 %에 불과합니다. 이것의 많은 부분은 해시가 어떻게 사용될 것인지에 달려 있습니다. – corsiKa
두 개의 서로 다른 32 비트 해시 함수의 값을 연결하여 64 비트 해시를 얻을 수 있다고 생각합니다.
네 가지 해시 함수를 얻으려면 해시 함수의 값으로 통근하지 않는 방법으로 해시 함수에 대한 입력을 변경하는 전처리 단계를 사용해야합니다. 한 가지 방법은 256 바이트 룩업 테이블을 사용하여 바이트의 번호를 다시 매기는 것입니다. 또 다른 것은 X mod 257에 의해 각 바이트를 곱해서, 그렇지 않으면 발생하지 않을 것이기 때문에 -X mod 257에 의해 256 = -1 mod 257이되는 것을 대체 할 수 있습니다. (a * 256 + b) mod 257은 + b mod 257입니다.
FWIW 아주 안전한 보장이있는 안전하지 않은 해시 함수가 있습니다. 예를 들어, 소수를 선택하고 해당 숫자를 모듈로 계산하여 모든 수학 계산을 수행하십시오. 데이터를 프라임 (prime)이되는 숫자의 시퀀스로 잘라서 다항식의 계수로 처리하십시오. 뿐만 아니라 귀하의 해시 함수에 대한 계수를 선택하면 숫자 x mod 소수를 선택한 다음 해당 x에서 다항식을 평가합니다. 이론상 x는 무작위로 선택됩니다.
두 개의 메시지는 다항식의 차가 0 인 경우 동일한 값으로 매핑됩니다. 즉, 선택한 x는 해당 다항식의 루트입니다. 차수 N의 다항식은 최대 N 개의 루트를가집니다. 따라서 매우 짧은 문자열을 사용하고 큰 모듈을 선택하면 나쁜 경우는 아닙니다. 이 계산의 결과를 암호화하면 보안 해시 함수를 가져 오는 더 빠른 방법으로 제안 된 것으로 생각됩니다. 나는 그것이 MD5보다 빠르다고 생각했는데, 비록 128 비트 소수를 계산하는 것이 비싸다 할지라도 누군가는 MD5보다 저렴하다고 생각했기 때문이다.
번호 매기기가 바람직하지 않은 이유에 대해 자세히 설명해 주시겠습니까?하지만 64 비트 해시로 깨는 것이 바람직합니다. – corsiKa
나는 추가 된 여분의 문자열이나 삭제의 사소한 수정으로 키 값 (즉, 해쉬)을 불변으로하고 싶다. 문자열 집합은 때때로 (나를 제외한) 업데이트되며 저장 해시 값의 의미를 유지하기를 원합니다. –
음. 결국 새로운 항목을 추가 할 수 없으며 삭제 된 항목의 색인을 "폐기"할 수 있습니까? 기본 키를 증가시키면서 데이터베이스 테이블에 대해 꽤 잘 작동합니다. 필자가 보게되는 문제는 문자열 값에서 인덱스로의 검색 비용입니다 (Trie, BST 또는 역설적으로 해시 테이블을 원할 것입니다.이 중 하나는 절약하려는 것보다 많은 메모리를 차지할 수 있습니다). 세트. –