Сокращать длинные URL с помощью хеша?

Question

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

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

Спасибо

Answer 1

Вы можете сгенерировать UUID для каждого URL и использовать его в качестве имени файла.

UUID уникальны (или "практически уникальны") и имеют длину 36 символов, поэтому я думаю, что имя файла не будет проблемой.

Начиная с версии 5, JDK поставляется с классом для генерации UUID (java.util.UUID). Вы можете использовать случайную генерацию UUID, если есть способ связать их с URL-адресами, или вы могли бы использовать UUID на основе имени. UUID, основанные на имени, всегда одинаковы, поэтому всегда верно следующее:

String url = ...
UUID urlUuid = UUID.nameUUIDFromBytes(url.getBytes);
assertTrue(urlUuid.equals(UUID.nameUUIDFromBytes(url.getBytes)));

Answer 2

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

Обычно я делаю это, сохраняя оригинальное имя в начале (например, в первой строке) файла кэша. Итак, чтобы найти файл в кеше, вы делаете это так:

• Хэш URL
• Найдите файл, соответствующий этому хешу
• Проверьте первую строку. Если он совпадает с полным URL-адресом:
• Остальная часть файла от второй строки и вперед

Вы также можете рассмотреть сохранение URL-> сопоставления файлов в базе данных.

Answer 3

Но я не уверен, гарантируется ли уникальность хэшей для двух разных строк.

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

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

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

Answer 4

Хэши не гарантируют, что они уникальны, но вероятность столкновения крайне мала.

Если ваш хэш, скажем, 128 битов, то вероятность коллизии для любой пары записей равна 1 в 2^128. По парадоксу дня рождения, если в вашей таблице было 10^18 записей, тогда вероятность столкновения составляет всего 1%, поэтому вам не нужно об этом беспокоиться. Если вы чрезмерно параноидальны, увеличьте размер хеша с помощью SHA256 или SHA512.

Очевидно, вам нужно убедиться, что хешированное представление на самом деле занимает меньше места, чем оригинальное имя файла. Строки в кодировке Base-64 представляют 6 битов на символ, так что вы можете выполнить математические вычисления, чтобы выяснить, стоит ли вообще делать хеш в первую очередь.

Если ваша файловая система раздражает, потому что имена слишком длинные, вы можете создать префиксные подкаталоги для фактического хранилища. Например, если файл отображает хэш ABCDE, вы можете сохранить его как /path/to/A/B/CDE, или, может быть /path/to/ABC/DE в зависимости от того, что лучше всего подходит для вашей файловой системы.

Git является хорошим примером этой техники на практике.

Answer 5

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

в каталоге у вас есть:

index.txt
file1
file2
...
etc.

и в index.txt вы используете некоторую структуру данных для эффективного поиска имен файлов (или замены на БД)

Answer 6

В настоящее время рекомендуется алгоритм SHA-1. Для этого алгоритма нет известных способов преднамеренного провоцирования коллизий, поэтому вы должны быть в безопасности. Провоцирование коллизий с двумя частями данных, которые имеют общую структуру (например, http:// префикс) еще сложнее. Если вы сохраните этот материал после того, как получите ответ HTTP 200, то URL явно извлечет что-то, поэтому получение двух разных действительных URL с одинаковым хешем SHA-1 действительно не должно быть проблемой.

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

Answer 7

Посмотрите на мой комментарий.
Одним из возможных решений (их много) является создание локального файла (SQLite? XML? TXT?), В котором вы храните пару (file_id - file_name), чтобы вы могли сохранить загруженные файлы с их уникальным идентификатором в качестве имени файла.
Просто идея, не самая лучшая...