Đây có phải là cách sử dụng thích hợp chức năng băm tích hợp của python không?

Question

Tôi cần phải so sánh các khối dữ liệu lớn cho sự bình đẳng và tôi cần phải so sánh nhiều số liệu mỗi giây, nhanh. Mỗi đối tượng được đảm bảo có cùng kích thước và có thể có khả năng chúng chỉ khác nhau một chút (ở các vị trí không xác định). Tôi đã thấy, từ phiên tương tác bên dưới, sử dụng toán tử == cho chuỗi byte có thể chậm hơn nếu sự khác biệt ở cuối chuỗi và có thể rất nhanh nếu có sự khác biệt gần bắt đầu. Tôi nghĩ rằng có thể có một số cách để tăng tốc độ sử dụng một số loại băm, tất nhiên tính toán băm md5 và so sánh là một whack công bằng chậm hơn, nhưng băm inbuilt của python dường như tốc độ những thứ lên đáng kể.

Tuy nhiên, tôi không có ý tưởng về chi tiết triển khai của hàm băm này, có thực sự là băm giống như vậy khi tôi có thể thoải mái khi hash(a) == hash(b) sau đó a == b rất có thể? Tôi hạnh phúc để có một vài kết quả không chính xác nếu một vụ va chạm băm là hợp lý hiếm (hiếm theo nghĩa cần an array of 200 PS3s several hours to make a collision)

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

hàm băm Python được thiết kế cho tốc độ và bản đồ vào một không gian 64-bit. Do birthday paradox, điều này có nghĩa là bạn có thể sẽ nhận được một vụ va chạm ở khoảng 5 tỷ mục (có thể là cách trước đó, vì hàm băm không mã hóa). Ngoài ra, định nghĩa chính xác của hash là tùy thuộc vào việc triển khai Python và có thể là kiến ​​trúc hoặc thậm chí là máy cụ thể. Không sử dụng nó, bạn muốn có cùng một kết quả trên nhiều máy.

md5 được thiết kế dưới dạng hàm băm mật mã; thậm chí nhiễu loạn nhẹ trong đầu vào hoàn toàn thay đổi đầu ra. Nó cũng bản đồ thành một không gian 128-bit, mà làm cho nó không chắc bạn sẽ bao giờ gặp phải một vụ va chạm ở tất cả trừ khi bạn đang cụ thể tìm kiếm một.

Nếu bạn có thể xử lý các va chạm (tức là kiểm tra sự bình đẳng giữa tất cả các thành viên trong một nhóm, có thể bằng cách sử dụng thuật toán mã hóa như MD5 hoặc SHA2), hàm băm của Python hoàn toàn ổn.

Một điều nữa: Để tiết kiệm dung lượng, bạn nên lưu trữ dữ liệu dưới dạng nhị phân nếu bạn ghi nó vào đĩa. (ví dụ: struct.pack('!q', hash('abc'))/hashlib.md5('abc').digest()).

Lưu ý: is không tương đương với == bằng Python. Ý bạn là ==.