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

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

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

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

Изменить: Вариант использования выглядит следующим образом: Загрузчик данных получает новый экземпляр объекта, переносящего данные. Уникальные типы имеют уникальный репр. так что если файл кеша для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("=")
 u0b34a0f6ae20 авг. 2009 г., 17:50
в заключительном примере, для хеш-кода python, вы можете, конечно, использовать bytes = (..). digest ().
 max02 окт. 2012 г., 05:19
Вы не должны использовать встроенный хэш, потому что это 'не гарантируется постоянство между сеансами (или архитектурами, хотя в вашем случае это может не иметь значения, если все файлы кэша хранятся локально). На самом деле, начиная с Python 3.3, это 's гарантированно будет рандомизирован для строк. Вы должны рассмотреть возможность использования рукописных функций, таких какэтот.
 u0b34a0f6ae20 авг. 2009 г., 01:14
Это безобразно И все программисты хотят выражать меньше с помощью большего, и здесь я знаю, что могу, полный криптографический хеш является излишним.
 Vinko Vrsalovic20 авг. 2009 г., 00:59
Почему вы заботитесь о длине имен файлов? Это нене имеет значения, если вы не используете тупую файловую систему

Ответы на вопрос(8)

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

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

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

def hash(s):
  return 0

но я думаю, ты неЭто действительно так ...

 Frizi04 сент. 2011 г., 13:58
найти наroflcopter.pl/5257 : D
 u0b34a0f6ae20 авг. 2009 г., 00:58
ну я хочу избежать столкновений :-)
Решение Вопроса

парадокс дня рождения применяется: при наличии хорошей хеш-функции ожидаемое количество хешей до возникновения коллизии составляет около 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, неt обрезать ;-) a sha256 до длинного с разумным количеством битов, скажем, 128 или около того, и использовать% оператор, чтобы сократить его до желаемой длины перед кодированием.

 u0b34a0f6ae20 авг. 2009 г., 13:09
очень хорошее правило для выбора длины хеша
 stephendwolff24 февр. 2019 г., 22:36
с python3, base64.b32encode работает с байтами, а не со строками

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

 Ned Batchelder20 авг. 2009 г., 13:59
Да, точно. С любым хешем вам нужно решить, какой риск столкновения является приемлемым, и оценить ваш риск.
 S.Lott20 авг. 2009 г., 12:08
Чем больше вы усекаете, тем выше вероятность одинакового значения хеш-функции для двух разных файлов. Вопрос в том "какие шансы приемлемы?  Когда вы усекаете, вы страдаетеложные срабатывания: Хэши совпадают, но объекты различаются.

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

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

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

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

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

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

 gahooa20 авг. 2009 г., 01:13
В прошлом мы брали 1/2 MD5, преобразовывали его в 64-битное целое и сохраняли его в базе данных (в этом случае производительность была критической, при> 100 000 000 записей.
 Matthew Scharley20 авг. 2009 г., 01:12
На самом деле, по разным математическим причинам, использование подстроки хеша генерирует гораздо больше коллизий, чем просто использование более короткой хеш-функции. Посмотрите, например, протоколы, которые генерируют частичные коллизии SHA1 в реальном времени как часть протокола.
 u0b34a0f6ae20 авг. 2009 г., 01:07
Я распаковываю кеш и замечаю, когда что-то не так, поэтому коллизии - это просто неприятность двух сталкивающихся объектов, один из которых всегда не имеет кеша при запуске приложения. Но это очень хорошее предложение, поскольку sha1 - это тип хэш-функции, который нея не сталкивался, и я ничего не делалне думать о
 gahooa20 авг. 2009 г., 01:15
@ Мэтью Шарли: У вас есть какие-либо ссылки на эту информацию - яЯ заинтересован.

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

Нашел это,binascii.crc32

 Matthew Scharley20 авг. 2009 г., 01:16
CRC нерекомендуется в качестве хэша на том основании, что он будет генерировать столкновения, и это 'относительно легко сделатьнарочно, Это делает его небезопасным, например, для хэширования паролей. Но этоявляется хеш-функция, она просто генерирует очень короткий хеш. Это означает намного больше потенциальных столкновений. Это быстрый и маленький, хотя, этоОбычное применение - проверка работоспособности. Если 2 ^ 32 вариантов достаточно, то CRC32 в порядке (или, видимо,hash() функция в Python генерирует 2 ^ 32 тоже. Didn»не знаю этого, я нея действительно использую Python)
 u0b34a0f6ae20 авг. 2009 г., 01:05
именно этоочень быстро, что хорошо. Но, видя, что это не рекомендуется в качестве хэш-функции, возможно, строка 's hash () так же хорош?

Ваш ответ на вопрос