Короткий алфавитно-цифровой хэш-код Python с минимальными коллизиями
Я хотел бы установить нецелые первичные ключи для таблицы, используя какую-либо хеш-функцию. md5 () кажется длинным (32 символа).
Каковы некоторые альтернативные хеш-функции, которые, возможно, используют каждую букву в алфавите, а также целые числа, которые, возможно, короче длины строки и имеют низкие скорости столкновений?
- Хеширование неизменяемого словаря в Python
- Когда вычисляется хэш-объект python и почему хэш -1 отличается?
- Является ли словарь Python примером хеш-таблицы?
- Реверсивная хеш-функция?
- Что делает hash в python?
- Почему -1 и -2 оба хеша до -2 в CPython?
Благодаря!
5 Solutions collect form web for “Короткий алфавитно-цифровой хэш-код Python с минимальными коллизиями”
Самый маленький встроенный хэш, о котором я знаю, – md5
>>> import hashlib >>> hashlib.md5("hello worlds").digest().encode("base64") 'uWuHitcvVnCdu1Yo4c6hjQ==\n' Низкое столкновение и короткое замыкание являются несколько взаимоисключающими из-за парадоксальности дня рождения
Чтобы сделать это urlsafe, вам нужно использовать функцию из модуля base64
>>> import base64 >>> base64.urlsafe_b64encode(hashlib.md5("hello world").digest()) 'XrY7u-Ae7tCTyyK7j1rNww=='
Однако не должно быть проблем с хранением 16-байтового md5-дайджеста в базе данных в двоичной форме.
>>> 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=='->>> 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=='
Вы можете выбрать либо quote_plus либо urlsafe_b64encode для своего URL- urlsafe_b64encode , а затем декодировать с помощью соответствующей функции unquote_plus или urlsafe_b64decode прежде чем искать их в базе данных.
Почему бы вам просто не урезать SHA1 или MD5? Тогда у вас будет больше коллизий, если вы не усекаетесь, но это все же лучше, чем создание собственного. Обратите внимание, что вы можете base64-кодировать усеченный хэш, а не использовать шестнадцатеричный. Например
import base64 import hashlib hasher = hashlib.sha1("The quick brown fox") base64.urlsafe_b64encode(hasher.digest()[0:10])
Вы можете обрезать как можно меньше (в том числе и вовсе) или столько, сколько хотите, до тех пор, пока вы понимаете компромиссы.
EDIT: поскольку вы упомянули URL-safe, вы можете использовать urlsafe_b64encode и urlsafe_b64decode , который использует - и _ а не + и / .
Ниже приведено решение, в котором используются буквенно-цифровые символы плюс несколько знаков препинания. Он возвращает очень короткие строки (около 8 символов).
import binascii, struct def myhash(s): return binascii.b2a_base64(struct.pack('i', hash(s)))
Hashids – это библиотека (с поддержкой Python), которая создает хэши, которые вы можете легко кодировать / декодировать.
Вы можете использовать что-то вроде нотации базы 32. Он более компактен, чем десятичная нотация, без учета регистра и без столкновений. Просто закодируйте простой старый порядковый номер, чтобы создать короткий хэш-код.
Если ключ не предназначен для потребления человеком, вы можете использовать нотацию base 64, которая чувствительна к регистру, но немного более компактна.
См. http://code.google.com/p/py-cupom/ для примера.