CRC32 сделать короткий URL для веб

StackOverflow https://stackoverflow.com/questions/1401218

Вопрос

Я пытаюсь понять crc32, чтобы сгенерировать уникальный URL для веб-страницы.

Если мы используем crc32, какое максимальное количество URL-адресов можно использовать, чтобы избежать дублирования?

Какой может быть приблизительная длина строки, чтобы контрольная сумма составляла 2 ^ 32?

Когда я попробовал UUID для URL и преобразовал байты uuid в базу 64, я мог сократить длину до 22 символов. Интересно, я могу уменьшить еще больше.

В основном я хочу преобразовать URL (максимум 1024 символа) в сокращенный идентификатор.

Это было полезно?

Решение

Не существует такого числа, которое можно использовать как "максимальное количество URL-адресов", чтобы мы могли избежать дубликатов " для CRC32.

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

Так что вы можете столкнуться со вторым URL, если вам не повезло.

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

Другие советы

Если вы уже сохраняете полный URL-адрес в таблице базы данных, целочисленный идентификатор довольно короткий, и его можно сократить, преобразовав его в основание 16, 64 или 85. Если вы можете использовать UUID, вы можете используйте целое число, и вы тоже можете, так как оно короче, и я не вижу, какое преимущество UUID даст в вашей справочной таблице.

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

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

CRC32 означает проверку циклическим избыточным кодом с 32 битами, где любое произвольное количество бит суммируется до 32-битной контрольной суммы. И функции контрольной суммы сюръективны, это означает, что несколько входных значений имеют одинаковое выходное значение. Таким образом, вы не можете инвертировать функцию.

Нет, даже если вы используете md5 или любую другую контрольную сумму, URL МОЖЕТ дублироваться, все зависит от вашей удачи.

Так что не делайте уникальную базу URL на этой контрольной сумме

Самый быстрый (и, возможно, лучший!) способ решения проблем может состоять в простом использовании хэша локального пути и запроса заданного URI следующим образом: 

using System;

namespace HashSample
{
    class Program
    {
        static void Main(string[] args)
        {
            Uri uri = new Uri(
                "http://host.com/folder/file.jpg?code=ABC123");

            string hash = GetPathAndQueryHash(uri);

            Console.WriteLine(hash);
        }

        public static string GetPathAndQueryHash(Uri uri)
        {
            return uri.PathAndQuery.GetHashCode().ToString();
        }
    }
}

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

Для отличного обсуждения посещения CRC32 Hash Collision: http://episteme.arstechnica.com/eve/forums/a/tpc/f/6330927813/m/821008399831

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top