CRC32 para fazer URL curta para web

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

Pergunta

Eu estou tentando compreender crc32 para gerar a url única para página web.

Se usarmos o crc32, o que é o número máximo de URLs pode ser usado para que possamos evitar duplicações?

O que poderia ser o comprimento da corda approximative para manter a soma de verificação para ser 2 ^ 32?

Quando eu tentei UUID para uma url e converter os bytes UUID a base 64, eu poderia reduzir a 22 caracteres de comprimento. Pergunto-me posso reduzir ainda mais.

Na maior parte eu quero converter o url (máximo 1024 caracteres) para id curto.

Foi útil?

Solução

Não existe tal número como o "número máximo de URLs pode ser usado para que possamos evitar duplicações" para CRC32.

O problema é que CRC32 pode produzir duplicatas, e não é uma função de quantos valores que você jogue com ele, é uma função do que esses valores se parecem.

Assim, você pode ter uma colisão na segunda url, se você não está com sorte.

Você não deve basear seu algoritmo na produção de um hash exclusivo, em vez produzir um valor único para cada url manualmente.

Outras dicas

Se você já está armazenando a URL completa em uma tabela de banco de dados, um ID de inteiro é muito curto, e pode ser feita mais curta, convertendo-a base 16, 64, ou 85. Se você pode usar um UUID, você pode usar um inteiro, e você pode muito bem, já que é mais curta e eu não vejo o que beneficiar um UUID daria em sua tabela de pesquisa.

O caminho certo para fazer uma URL curta é armazenar a uma cheia no banco de dados e publicar algo que mapeia para o índice de linha. A forma compacta é usar a Base64 da identificação de linha, por exemplo. Ou você poderia usar um UID para a chave primária e mostrar isso.

Não use um checksum, porque é muito pequeno e muito provavelmente ao conflito. Um hash criptográfico é maior e menos provável, mas ainda não é o caminho certo a seguir.

CRC32 meios verificação de redundância cíclica com 32 bits, onde qualquer quantidade arbitrária de bits é resumida a uma soma de verificação de 32 bit. E as funções de soma de verificação são surjective, isso significa que vários valores de entrada têm o mesmo valor de saída. Então você não pode inversa da função.

Não, mesmo que você usar md5, ou qualquer outra soma de verificação, a URL pode ser duplicado, tudo depende da sua sorte.

Portanto, não fazer uma base url única sobre aqueles soma de verificação

O mais rápido (! E talvez melhor) maneira de resolver as coisas podem ser simplesmente usar um hash do caminho local e consulta de um determinado URI, como segue: 

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();
        }
    }
}

Os presume acima que o esquema URI e anfitrião permanecem os mesmos. Se não GetHashCode irá funcionar com qualquer string.

Para uma grande discussão sobre CRC32 Hash Collision visita: http://episteme.arstechnica.com/eve/forums/a/tpc/f/6330927813/m/821008399831

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top