Как генерировать уникальный хеш для URL?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вы сказали:

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

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

Итак, у вас может быть Словарь <строка, строка> для работы в качестве кеша для ваших 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==

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

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

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

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

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

• URL: http: //a2.twimg.com/profile_images/ 433484366 / Terrorbite-industries-256.png
• Имя файла: 433484366.

Я играю с 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, соответствует различным настройкам, которые скрипт использует при общении с thumbalizr api, но я полагаю, что fcc3a328e0f4c1b51bf5e13747614e7a - это прямой md5 url, в данном случае для thumbalizr. com

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

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