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

Ответ 1

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

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

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

Ответ 2

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

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

Ответ 3

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

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

Ответ 4

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

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

Ответ 5

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

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

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

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

Ответ 6

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

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

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

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

Ответ 7

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

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

Ответ 8

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

Ответ 9

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

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

Ответ 10

Я играю с thumbalizr, используя модифицированную версию своего кеширования script, и у него есть несколько хороших решений, которые я думаю. Код находится на 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, соответствует различным настройкам, которые использует script при разговоре с thumbalizr api, но я думаю, что fcc3a328e0f4c1b51bf5e13747614e7a является прямым md5 URL-адреса, в данном случае для thumbalizr.com

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

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

Ответ 11

Ты сказал:

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

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

Таким образом, вы можете иметь Dictionary<string, string> для работы в качестве кеша для ваших URL-адресов. Таким образом, когда вы получаете новый адрес, сначала выполняете поиск в этом списке и, если не найдете совпадение, хеш его и хранилище для будущего использования.

Следуя этой строке, вы можете попробовать MD5:

public static void Main(string[] args)
{
    foreach (string url in new string[]{ 
        "http://a3.twimg.com/profile_images/130500759/lowres_profilepic.jpg", 
        "http://a1.twimg.com/profile_images/58079916/lowres_profilepic.jpg" })
    {
        Console.WriteLine(HashIt(url));
    }
}

private static string HashIt(string url)
{
    Uri path = new Uri(new Uri(url), ".");
    MD5CryptoServiceProvider md5 = new MD5CryptoServiceProvider();
    byte[] data = md5.ComputeHash(
        Encoding.ASCII.GetBytes(path.OriginalString));
    return Convert.ToBase64String(data);
}

Вы получите:

rEoztCAXVyy0AP/6H7w3TQ==
0idVyXLs6sCP/XLBXwtCXA==

Ответ 12

Похоже, что числовая часть URL twimg.com уже является уникальным значением для каждого изображения. Мои исследования показывают, что число является последовательным (например, примерный URL-адрес для 433 484 366-го профиля изображения, когда-либо загружаемого, что просто является моим). Таким образом, это число уникально. Моим решением было бы просто использовать цифровую часть имени файла как "хеш-значение", не опасаясь когда-либо находить неповторимое значение.

• URL: http://a2.twimg.com/profile_images/433484366/terrorbite-industries-256.png
• Имя файла: 433484366.terrorbite-industries-256.png
• Уникальный идентификатор: 433484366

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

P.S. Не имеет значения, из какого субдомена загружается изображение, все изображения доступны из всех поддоменов.