Хеширование данных. Подходящий алгоритм? - PullRequest
0 голосов
/ 15 июня 2011

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

Данные, которые мне понадобятся для хеширования, варьируются от 8 кБ изображений до 40анимации в килобайтах, до 3–5 МБ музыкальных файлов, до <0,5 МБ звуковых файлов.Какой, по вашему мнению, лучший алгоритм хеширования для моего случая?В этом отношении хеширование данных - это путь, или я должен подумать о каком-то другом способе идентификации данных? </p>

Ответы [ 2 ]

1 голос
/ 15 июня 2011

Существует множество сильных алгоритмов, широко используемых:

  • sha512 (128 байт)
  • sha384 (96 байт)
  • sha224 (56 байт)
  • sha1 и palemd160 (40 байт)
  • md5 (32 байта) ( как у старых md4 и md2 )

слабее * CRC (10 байт)

Общее правило:

  • вероятность столкновения увеличивается с количеством элементов в ваших коллекциях, не с их размером
  • вероятность столкновения уменьшается с количеством битов в контрольной сумме

Хеширование - это путь . Просто помните, что для очень очень очень больших коллекций элементов следует учитывать вероятность возникновения коллизии (т. Е. Использовать поиск по хешу с последующим линейным поиском по содержимому).

Пока вы, похоже, храните файлы, вероятно, было бы неплохо создать составной ключ:

  • хэш содержимого
  • имя файла
  • длина файла

Это имеет следующие преимущества:

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

$ 0,02

0 голосов
/ 15 июня 2011

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...