Создание уникального ключа на основе содержания файла в Python
Я заставил многих, много файлов быть загруженными на сервер, и я просто хочу способ избежать дубликатов.
Таким образом генерация уникального и маленького значения ключа от большой строки казалась чем-то, что контрольная сумма была предназначена, чтобы сделать, и хеширование походило на эволюцию этого.
Таким образом, я собирался использовать хеш md5, чтобы сделать это. Но затем я считал где-нибудь, что "MD5 не предназначены, чтобы быть уникальными ключами", и я думал, что это действительно странно.
Каков правильный способ сделать это?
править: между прочим, я взял два источники для получения до следующего, которое является, как я в настоящее время делаю его, и он работает просто великолепно с Python 2.5:
import hashlib
def md5_from_file (fileName, block_size=2**14):
md5 = hashlib.md5()
f = open(fileName)
while True:
data = f.read(block_size)
if not data:
break
md5.update(data)
f.close()
return md5.hexdigest()
3 ответа
Использование MD5 - хорошая идея. Просто чтобы убедиться, что я добавляю длину файла или количество фрагментов в вашу хеш-таблицу файлов.
Да, есть вероятность, что вы столкнетесь с двумя файлами с одинаковым хешем MD5, но это маловероятно (если ваши файлы имеют приличный размер). Таким образом, добавление количества кусков к вашему хешу может помочь вам уменьшить его, поскольку теперь вам нужно найти два файла одинакового размера с одинаковым MD5.
# This is the algorithm you described, but also returns the number of chunks.
new_file_hash, nchunks = hash_for_tile(new_file)
store_file(new_file, nchunks, hash)
def store_file(file, nchunks, hash):
"" Tells you whether there is another file with the same contents already, by
making a table lookup ""
# This can be a DB lookup or some way to obtain your hash map
big_table = ObtainTable()
# Two level lookup table might help performance
# Will vary on the number of entries and nature of big_table
if nchunks in big_table:
if hash in big_table[hash]:
raise DuplicateFileException,\
'File is dup with %s' big_table[nchunks][lookup_hash]
else:
big_table[nchunks] = {}
big_table[nchunks].update({
hash: file.filename
})
file.save() # or something
Чтобы уменьшить эту возможность, переключитесь на SHA1 и используйте тот же метод. Или даже используйте оба (объединение), если производительность не является проблемой.
Конечно, имейте в виду, что это будет работать только с дублирующимися файлами на двоичном уровне, а не с изображениями, звуками и видео, которые «одинаковы», но имеют разные подписи.
Проблема с хешированием заключается в том, что он генерирует «маленький» идентификатор из «большого» набора данных. Это похоже на сжатие с потерями. Хотя вы не можете гарантировать уникальность, вы можете использовать его, чтобы существенно ограничить количество других элементов, с которыми вам нужно сравнивать.
Учтите, что MD5 дает 128-битное значение (я думаю, что это так, хотя точное количество битов не имеет значения). Если ваш набор входных данных содержит 129 битов, и вы фактически используете их все, каждое значение MD5 будет появляться в среднем дважды. Для более длинных наборов данных (например, «все текстовые файлы, содержащие ровно 1024 печатных символа») вы все равно столкнетесь с конфликтами, как только вы получите достаточное количество входных данных. Вопреки тому, что сказано в другом ответе, математическая уверенность в том, что вы получите столкновения.
См. http://en.wikipedia.org/wiki/Birthday_Paradox
Конечно, у вас есть примерно 1% шанс столкновения со 128-битным хешем при 2,6 * 10 ^ 18 записей, но это лучше чтобы справиться с ситуацией, когда вы действительно получаете столкновения, чем надеяться, что вы никогда не столкнетесь.
Проблема с MD5 в том, что он не работает. Для наиболее распространенных применений возникает небольшая проблема, и люди все еще используют как MD5, так и SHA1, но я думаю, что если вам нужна функция хеширования, вам понадобится сильная функция хеширования. Насколько мне известно, до сих пор нет стандартной замены ни одному из них. Есть ряд алгоритмов, которые «считаются» сильными, но у нас больше всего опыта работы с SHA1 и MD5. То есть мы (думаем) знаем, когда эти два ломаются, тогда как на самом деле мы не так много знаем, когда ломаются новые алгоритмы.
Итог: подумайте о рисках. Если вы хотите пройти лишнюю милю, вы можете добавить дополнительные проверки при обнаружении дубликата хэша за счет снижения производительности.