Как создать уникальный хеш для URL?

Question

Учитывая эти два изображения из твиттера.

http://a3.twimg.com/profile_images/130500759/lowres_profilepic.jpg
http://a1.twimg.com/profile_images/58079916/lowres_profilepic.jpg

Я хочу загрузить их в локальную файловую систему и сохранить в одном каталоге. Как мне преодолеть конфликт имен?

В приведенном выше примере я не могу сохранить их как lowres_profilepic.jpg . Моя идея заключается в том, чтобы обрабатывать URL-адреса как непрозрачные строки, за исключением последнего сегмента. Какие алгоритмы (реализованные как f ) можно использовать для хеширования префиксов в уникальные строки.

f( "http://a3.twimg.com/profile_images/130500759/" ) = 6tgjsdjfjdhgf
f( "http://a1.twimg.com/profile_images/58079916/" )  = iuhd87ysdfhdk

Таким образом, я могу сохранить файлы как: -

6tgjsdjfjdhgf_lowres_profilepic.jpg
iuhd87ysdfhdk_lowres_profilepic.jpg

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

Answer 1

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

Причина в том, что поиск файлов для большинства файловых систем включает линейное сканирование по именам файлов в каталоге. Таким образом, если все N ваших файлов находятся в одном каталоге, поиск потребует в среднем 1/2 N сравнений; т.е. O(N) (Обратите внимание, что ReiserFS организует имена в каталоге как BTree. Однако ReiserFS представляется скорее исключением, чем правилом.)

Вместо одного большого плоского каталога было бы лучше сопоставить URI с деревом каталогов. В зависимости от формы дерева, поиск может составлять O(logN). Например, если вы организовали дерево так, чтобы в нем было 3 уровня каталогов, содержащих не более 100 записей в каждом каталоге, вы могли бы разместить 1 миллион URL-адресов. Если вы спроектировали отображение для использования двухсимвольных имен файлов, каждый каталог должен легко помещаться в один блок диска, а поиск пути (при условии, что требуемые каталоги уже кэшированы) должен занять несколько микросекунд.

Answer 2

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

• Будет работать любая кодировка URL, даже base64: например, filename = base64(url)
• Криптохеш даст вам то, что вы хотите - хотя вы и утверждаете, что это будет узким местом в производительности, не будьте уверены, пока не сравните тест

Answer 3

Очень простой подход:

f( "http://a3.twimg.com/profile_images/130500759/" ) = a3_130500759.jpg
f( "http://a1.twimg.com/profile_images/58079916/" )  = a1_58079916.jpg

Поскольку другие части этого URL являются постоянными, вы можете использовать поддомен, последнюю часть пути запроса, в качестве уникального имени файла.

Не знаю, в чем может быть проблема с этим решением

Answer 4

Одним из ключевых понятий URL-адреса является его уникальность. Почему бы не использовать его?

Каждый алгоритм, который сокращает информацию, может создавать коллизии. Может быть, маловероятно, но все же возможно

Answer 5

Природа хэша заключается в том, что он может привести к коллизиям. Как насчет одной из этих альтернатив:

1. использовать дерево каталогов. Буквально создавайте подкаталоги для каждого компонента URL.
2. Создать уникальный идентификатор. Проблема в том, как сохранить соответствие между реальным именем и сохраненным идентификатором. Вы можете использовать базу данных, которая отображается между URL-адресом и сгенерированным уникальным идентификатором. Вы можете просто вставить запись в базу данных, которая генерирует уникальные идентификаторы, а затем использовать этот идентификатор в качестве имени файла.

Answer 6

Вы можете использовать класс UUID в Java для генерации чего-либо в UUID из байтов, который является уникальным, и у вас не будет проблем с поиском файлов

String url = http://www.google.com;
String shortUrl = UUID.nameUUIDFromBytes("http://www.google.com".getBytes()).toString();

Answer 7

Несмотря на то, что CRC32 выдает максимум 2 ^ 32 значения независимо от вашего ввода и поэтому не будет избегать конфликтов, для этого сценария это все еще жизнеспособный вариант.

Это быстро, поэтому, если вы генерируете конфликтующее имя файла, просто добавьте / измените символ в своем URL и просто пересчитайте CRC.

4,3 миллиарда возможных контрольных сумм означают, что вероятность конфликта имени файла в сочетании с исходным именем файла будет настолько низкой, что в обычных ситуациях будет неважной.

Я сам использовал этот подход для чего-то подобного и был доволен производительностью. См. Fast CRC32 в программном обеспечении.

Answer 8

Я играю с thumbalizr, используя модифицированную версию их скрипта кэширования, и я думаю, что у него есть несколько хороших решений. Код находится на github.com/mptre/thumbalizr, но в короткой версии он использует md5 для построения имен файлов, и он берет первые два символа из имени файла и использует его для создания папки, которая называется точно так же , Это означает, что папки легко разбить на части и быстро найти соответствующую папку без базы данных. Вид взорвал мой разум своей простотой.

Он генерирует такие имена файлов http://pappmaskin.no/opensource/delicious_snapcasa/mptre-thumbalizr/cache/fc/fcc3a328e0f4c1b51bf5e13747614e7a_1280_1024_8_90_250.png

последняя часть, _1280_1024_8_90_250, соответствует различным настройкам, которые использует скрипт при обращении к API thumbalizr, но я полагаю, что fcc3a328e0f4c1b51bf5e13747614e7a - это прямой md5 URL, в данном случае для thumbalizr.com

Я попытался изменить конфигурацию для генерации изображений шириной 200px, и эти изображения помещаются в ту же папку, но вместо _250.png она называется _200.png

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

Answer 9

Система управления контентом git основана на SHA1 , потому что вероятность столкновения очень мала.

Если это хорошо для мерзавца, это будет хорошо для тебя.

Answer 10

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