Băm chữ số ngắn Python với các va chạm tối thiểu

Question

Tôi muốn đặt các khóa chính không phải số nguyên cho một bảng sử dụng một số loại hàm băm. md5() có vẻ là loại dài (32 ký tự).

Một số hàm băm thay thế có thể sử dụng mọi chữ cái trong bảng chữ cái cũng như số nguyên có lẽ ngắn hơn về độ dài chuỗi và có tỷ lệ va chạm thấp?

Cảm ơn!

Answer 1

Tại sao bạn không chỉ cắt ngắn SHA1 hoặc MD5? Bạn sẽ có nhiều va chạm sau đó nếu bạn không cắt ngắn, nhưng nó vẫn tốt hơn thiết kế của riêng bạn. Lưu ý rằng bạn có thể mã hóa base64 hash được cắt ngắn, thay vì sử dụng hệ thập lục phân. Ví dụ.

import base64 
import hashlib 
hasher = hashlib.sha1("The quick brown fox") 
base64.urlsafe_b64encode(hasher.digest()[0:10]) 

Bạn có thể cắt bớt ít (không bao gồm) hoặc nhiều như bạn muốn, miễn là bạn hiểu được sự cân bằng.

EDIT: Kể từ khi bạn đề cập URL-an toàn, bạn có thể sử dụng và urlsafe_b64decode, trong đó sử dụng - và _ hơn + và /.

Answer 2

Các băm BUILTIN nhỏ nhất tôi biết là md5

>>> import hashlib 
>>> hashlib.md5("hello worlds").digest().encode("base64") 
'uWuHitcvVnCdu1Yo4c6hjQ==\n' 

va chạm thấp và ngắn có phần loại trừ lẫn nhau do sự birthday paradox

Để làm cho nó urlsafe bạn cần phải sử dụng các chức năng từ base64 mô-đun

>>> import base64 
>>> base64.urlsafe_b64encode(hashlib.md5("hello world").digest()) 
'XrY7u-Ae7tCTyyK7j1rNww==' 

Tuy nhiên, sẽ không có vấn đề gì khi lưu trữ thông tin 16 byte md5 trong cơ sở dữ liệu dưới dạng nhị phân.

>>> md5bytes=hashlib.md5("hello world").digest() 
>>> len(md5bytes) 
16 
>>> urllib.quote_plus(md5bytes) 
'%5E%B6%3B%BB%E0%1E%EE%D0%93%CB%22%BB%8FZ%CD%C3' 
>>> base64.urlsafe_b64encode(md5bytes) 
'XrY7u-Ae7tCTyyK7j1rNww==' 

Bạn có thể chọn một trong hai quote_plus hoặc urlsafe_b64encode cho url của bạn, sau đó giải mã với chức năng tương ứng unquote_plus hay urlsafe_b64decode trước khi bạn nhìn chúng trong cơ sở dữ liệu.

Answer 3

Dưới đây là giải pháp sử dụng ký tự chữ và số cộng với một vài ký tự dấu chấm câu. Nó trả về các chuỗi rất ngắn (khoảng 8 ký tự).

import binascii, struct 

def myhash(s): 
    return binascii.b2a_base64(struct.pack('i', hash(s))) 

Answer 4

Bạn có thể sử dụng ký hiệu cơ bản 32. Nó nhỏ gọn hơn ký hiệu thập phân, không phân biệt chữ hoa chữ thường và không có xung đột. Chỉ cần mã hóa một số thứ tự cũ đơn giản để tạo ra một mã băm ngắn.

Nếu khóa không dành cho tiêu thụ của con người, bạn có thể sử dụng ký pháp cơ sở 64, có phân biệt chữ hoa chữ thường nhưng gọn hơn một chút.

Xem http://code.google.com/p/py-cupom/ để biết ví dụ.

Answer 5

Hashids là một thư viện (với sự hỗ trợ của Python) để tạo ra các băm mà bạn có thể mã hóa/giải mã rất dễ dàng.

http://hashids.org/python/