Создание уникального ключа на основе содержимого файла в python

Question

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

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

Так что я собирался использовать хеш md5 для этого. Но потом я прочитал где-то , что "MD5 не должен быть уникальным ключом", и я подумал, что это действительно странно.

Как правильно это сделать?

edit: кстати, я взял два источника , чтобы добраться до следующего, как я сейчас это делаю, и это работает просто хорошо, с 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()

Answer 1

Хорошая идея - придерживаться 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 и используйте тот же метод. Или даже используйте оба (объединение), если производительность не является проблемой.

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

Answer 2

Проблема с хешированием заключается в том, что он генерирует «маленький» идентификатор из «большого» набора данных. Это как сжатие с потерями. Хотя вы не можете гарантировать уникальность, вы можете использовать ее для существенного ограничения количества других предметов, с которыми вам нужно сравниваться.

Учтите, что MD5 дает 128-битное значение (я думаю, что так оно и есть, хотя точное количество битов не имеет значения). Если ваш входной набор данных имеет 129 битов, и вы фактически используете их все, каждое значение MD5 будет появляться в среднем дважды. Для более длинных наборов данных (например, «все текстовые файлы с ровно 1024 печатными символами») вы все равно столкнетесь с коллизиями, когда получите достаточно входных данных. Вопреки тому, что сказал другой ответ, это математическая уверенность, что вы получите столкновения.

См. http://en.wikipedia.org/wiki/Birthday_Paradox

Конечно, у вас есть около 1% вероятности коллизий с 128-битным хешем при 2,6 * 10 ^ 18 записей, но лучше обрабатывать случай, когда вы получаете коллизии, чем надеяться, что вы никогда не будете.

Answer 3

Проблема с MD5 в том, что он сломан. Для большинства распространенных применений есть небольшая проблема, и люди все еще используют и MD5, и SHA1, но я думаю, что если вам нужна функция хеширования, тогда вам нужна сильная функция хеширования. Насколько мне известно, до сих пор нет стандартного заменителя ни одного из них. Есть ряд алгоритмов, которые «должны быть сильными», но у нас больше всего опыта с SHA1 и MD5. То есть мы (думаем), что мы знаем, когда эти два ломаются, тогда как мы не знаем так много, когда ломаются более новые алгоритмы.

Итог: подумайте о рисках. Если вы хотите пройти лишнюю милю, вы можете добавить дополнительные проверки, когда найдете дубликат хеша, за цену штрафа за производительность.