Укоротить длинные 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

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

в вашем каталоге:

index.txt
file1
file2
...
etc.

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

Answer 5

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

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

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

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

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

Answer 6

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

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

Answer 7

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