Кратчайший хэш в python для именования файлов кэша

Question

Какой самый короткий хеш (в форме, используемой в имени файла, например, hexdigest) доступен в python? Мое приложение хочет сохранить файлы кэша для некоторых объектов. Объекты должны иметь уникальный repr (), поэтому они используются для «заполнения» имени файла. Я хочу создать возможно уникальное имя файла для каждого объекта (не так много). Они не должны сталкиваться, но если они это сделают, моему приложению будет просто не хватать кеша для этого объекта (и ему придется переиндексировать данные этого объекта, незначительные затраты для приложения).

Итак, если происходит одно столкновение, мы теряем один файл кэша, но именно благодаря экономии средств кэширования всех объектов запуск приложения происходит намного быстрее, поэтому это не имеет большого значения.

Прямо сейчас я использую abs (hash (repr (obj))); это верно, строка хэш! Пока не найдено никаких коллизий, но я бы хотел иметь лучшую хэш-функцию. hashlib.md5 доступен в библиотеке python, но hexdigest очень длинный, если поместить его в имя файла. Альтернативы с разумным сопротивлением столкновению?

Edit: Вариант использования выглядит так: Загрузчик данных получает новый экземпляр объекта, переносящего данные. Уникальные типы имеют уникальный репр. таким образом, если существует файл кэша для hash(repr(obj)), я распаковываю этот файл кэша и заменяю объект obj на не выбранный объект. Если было столкновение, и кэш был ложным совпадением, я замечаю. Поэтому, если у нас нет кэша или есть ложное совпадение, я вместо этого инициирую obj (перезагружаю его данные).

Выводы (?)

Хэш str в python может быть достаточно хорош, я беспокоился только о его сопротивлении столкновению. Но если я смогу хэшировать 2**16 объектов с ним, это будет более чем достаточно.

Я узнал, как взять шестнадцатеричный хеш (из любого источника хеша) и сохранить его компактно с base64:

# 'h' is a string of hex digits 
bytes = "".join(chr(int(h[i:i+2], 16)) for i in xrange(0, len(h), 2))
hashstr = base64.urlsafe_b64encode(bytes).rstrip("=")

Answer 1

Применяется парадокс дня рождения : при наличии хорошей хеш-функции ожидаемое количество хешей до возникновения коллизии составляет около sqrt (N), где N - количество различных значений, которые может принять хеш-функция , (Запись в википедии, на которую я указал, дает точную формулу). Так, например, если вы хотите использовать не более 32 бит, ваши опасения коллизий серьезны для объектов размером около 64 КБ (т. Е. 2**16 объектов - квадратный корень из 2**32 различных значений, которые может принимать ваша хеш-функция) , Сколько объектов вы ожидаете иметь на порядок?

Поскольку вы упоминаете, что столкновение является незначительным раздражением, я рекомендую вам стремиться к длине хеша, которая примерно равна квадрату числа объектов, которое у вас будет, или немного меньше, но не НАМНОГО меньше этого значения.

Вы хотите создать имя файла - это в файловой системе, чувствительной к регистру, как в Unix, или вам также нужно обслуживать системы без учета регистра? Это важно, потому что вы стремитесь к коротким именам файлов, но количество бит на символ, которое вы можете использовать для представления своего хэша в качестве имени файла, резко меняется в системах с чувствительностью к регистру и против нечувствительных.

В чувствительной к регистру системе вы можете использовать модуль base64 стандартной библиотеки (я рекомендую версию кодировки urlsafe, т.е. эту функцию, чтобы избежать символов '/', которые могут присутствие в простом base64 важно в именах файлов Unix). Это дает вам 6 используемых бит на символ, что намного лучше, чем 4 бита / символ в шестнадцатеричном формате.

Даже в нечувствительной к регистру системе вы все равно можете работать лучше, чем в шестнадцатеричном формате - используйте base64.b32encode и получите 5 бит на символ.

Эти функции принимают и возвращают строки; используйте модуль struct для преобразования чисел в строки, если выбранная вами хеш-функция генерирует числа.

Если у вас есть несколько десятков тысяч объектов, я думаю, вы будете в порядке со встроенным хешем (32 бита, поэтому 6-7 символов в зависимости от выбранной вами кодировки). Для миллиона объектов вы бы хотели 40 бит или около того (7 или 8 символов) - вы можете сложить (xor, не обрезать ;-) sha256 до длинного с разумным количеством бит, скажем, 128 или около того и используйте оператор %, чтобы обрезать его до желаемой длины перед кодированием.

Answer 2

Встроенная хеш-функция строк довольно свободна от столкновений, а также довольно коротка. Он имеет значения 2**32, поэтому маловероятно, что вы столкнетесь с коллизиями (если вы используете его значение abs, оно будет иметь только значения 2**31).

Вы запрашивали самую короткую хэш-функцию. Это, безусловно, будет

def hash(s):
  return 0

но я полагаю, вы на самом деле не имели это в виду ...

Answer 3

Вы можете сократить любой понравившийся хеш, просто обрезая его. md5 - это всегда 32 шестнадцатеричные цифры, но произвольная его подстрока (или любой другой хеш) имеет надлежащие качества хеша: равные значения производят равные хеши, а значения разбросаны по куче.

Answer 4

Я уверен, что в Python есть реализация CRC32, но она может быть слишком короткой (8 шестнадцатеричных цифр). С другой стороны, это очень быстро.

Нашел, binascii.crc32

Answer 5

Учитывая ваш вариант использования, если вы не настроены на использование отдельных файлов кэша и не слишком далеко зашли по пути разработки, вы можете рассмотреть возможность использования модуля shelve.

Это даст вам постоянный словарь (хранится в одном файле DBM), в котором вы храните свои объекты. Травление / расщепление выполняется прозрачно, и вам не нужно беспокоиться о хешировании, коллизиях, файловом вводе-выводе и т. Д.

Для полочных словарных ключей вы просто должны использовать repr (obj) и позволить shelve разбирать ваши объекты для вас. Простой пример:

import shelve
cache = shelve.open('cache')
t = (1,2,3)
i = 10
cache[repr(t)] = t
cache[repr(i)] = i
print cache
# {'(1, 2, 3)': (1, 2, 3), '10': 10}
cache.close()

cache = shelve.open('cache')
print cache
#>>> {'(1, 2, 3)': (1, 2, 3), '10': 10}
print cache[repr(10)]
#>>> 10

Answer 6

Мы используем hashlib.sha1.hexdigest (), который производит еще более длинные строки, для объектов кэширования с хорошим успехом. На самом деле никто не смотрит на файлы кеша.

Answer 7

Если у вас есть столкновение, как вы собираетесь сказать, что это действительно произошло?

На вашем месте я бы использовал hashlib для sha1() repr(), а затем просто получил бы его ограниченную подстроку (например, первые 16 символов).

Если вы не говорите об огромном количестве этих объектов, я бы посоветовал вам просто использовать полный хэш. Тогда вероятность столкновения настолько, настолько, настолько мала, что вы никогда не доживете до того, чтобы это произошло (вероятно).

Кроме того, если вы имеете дело с таким множеством файлов, я предполагаю, что ваша техника кэширования должна быть скорректирована с учетом этого.

Answer 8

Короткие хэши означают, что у вас может быть одинаковый хеш для двух разных файлов. То же самое может случиться и с большими хэшами, но это происходит гораздо реже. Возможно, эти имена файлов должны отличаться в зависимости от других ссылок, таких как микротайм (если эти файлы не могут быть созданы слишком быстро).