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

Question

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

Таким образом, генерирование уникального и небольшого значения ключа из большой строки казалось чем-то, что должна была иметь контрольная сумма, и hashing seemed like the evolution of that.

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

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

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

Hint : Подумайте, как работает хеш-таблица.

Answer 3

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

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

Answer 4

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

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

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

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