Самый короткий хэш в python для указания файлов кеша

Ответ 1

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

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

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

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

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

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

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

Ответ 2

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

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

def hash(s):
  return 0

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

Ответ 3

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

Ответ 4

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

Нашел, binascii.crc32

Ответ 5

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

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

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

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

Ответ 6

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

Ответ 7

Учитывая ваш вариант использования, если у вас нет вашего сердца, использующего отдельные файлы кеша, и вы не слишком далеко от этого пути разработки, вы можете подумать об использовании модуля 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

Ответ 8

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