이것은 파이썬의 내장 해시 함수를 적절히 사용하고 있습니까?

Question

나는 평등에 대한 데이터의 큰 덩어리를 비교해야하고, 나는, 초당 많은 비교 빠른이 필요합니다. 모든 객체는 동일한 크기로 보장되며, 알 수없는 위치에서 약간 다를 수 있습니다.

아래 대화식 세션에서 == 연산자를 사용하여 바이트 문자열에 대한 차이가 문자열 끝에 가까울수록 느려질 수 있으며 시작 부분에 차이가있을 경우 매우 빨라질 수 있습니다.

나는 일종의 해시를 사용하여 작업 속도를 향상시킬 수있는 방법이있을 것이라고 생각했다. 물론 md5 해시를 계산하고 비교하는 것은 공정한 딱딱한 속도이지만, 파이썬의 inbuilt 해시는 작업 속도를 크게 향상시키는 것처럼 보입니다.

그러나이 해시의 구현 세부 사항에 대해서는 전혀 알지 못하지만 실제로 해시와 비슷한 점이있어서 hash(a) == hash(b) 일 때 a == b 일 가능성이 높습니다. 해시 충돌이 파이썬의 해시 함수는 속도를 위해 설계되었습니다

In [1]: import hashlib 

In [2]: with open('/dev/urandom') as f: 
    ...:  spam = f.read(2**20 - 1) 
    ...:  

In [3]: spamA = spam + 'A' 

In [4]: Aspam = 'A' + spam 

In [5]: spamB = spam + 'B' 

In [6]: timeit spamA == spamB 
1000 loops, best of 3: 1.59 ms per loop 

In [7]: timeit spamA == Aspam 
10000000 loops, best of 3: 66.4 ns per loop 

In [8]: timeit hashlib.md5(spamA) == hashlib.md5(spamB) 
100 loops, best of 3: 4.42 ms per loop 

In [9]: timeit hashlib.md5(spamA) == hashlib.md5(Aspam) 
100 loops, best of 3: 4.39 ms per loop 

In [10]: timeit hash(spamA) == hash(spamB) 
10000000 loops, best of 3: 157 ns per loop 

In [11]: timeit hash(spamA) == hash(Aspam) 
10000000 loops, best of 3: 160 ns per loop 

Answer 1

(an array of 200 PS3s several hours to make a collision을 필요로하는 의미에서 희귀) 합리적으로 드문 및 64 비트 공간에 매핑하고있는 경우에 나는 몇 가지 잘못된 결과를 가지고 기쁘게 생각합니다. birthday paradox로 인해,이 (해시 함수가 cryptographical하지 않기 때문에, 아마 방법은 이전 버전) 당신은 가능성이 약 50 억 항목에서 충돌을 얻을 것이다 의미한다. 또한, hash의 정확한 정의는 파이썬 구현에, 그리고 Architecture를 또는 기계 관련 될 수있다. 여러 컴퓨터에서 같은 결과를 원한다면 사용하지 마십시오.

MD5는 암호화 해쉬 함수로서 설계된다; 입력에서의 약간의 섭동조차도 출력을 완전히 바꾼다. 또한 128 비트 공간으로 매핑되기 때문에 특별히 찾지 않는 한 충돌이 발생할 가능성은 거의 없습니다.

충돌을 처리 할 수 ​​있다면 (예 : MD5 또는 SHA2와 같은 암호화 알고리즘을 사용하여 버킷의 모든 구성원간에 동일한지 테스트 할 수 있음) Python의 해시 함수는 완벽합니다.

한가지 더 : 당신이 디스크에 기록하면 공간을 절약하기 위해, 당신은 바이너리 형식의 데이터를 저장해야합니다. (즉, struct.pack('!q', hash('abc'))/hashlib.md5('abc').digest()). 보조 노트로

: is 파이썬에서 ==에 해당하지 않습니다. ==을 의미합니다.