CRC32 per creare un breve URL per il web

Question

Sto cercando di capire crc32 per generare l'URL unico per la pagina web.

Se utilizziamo crc32, qual è il numero massimo di URL in modo da evitare duplicati?

Quale potrebbe essere la lunghezza approssimativa della stringa per mantenere il checksum pari a 2 ^ 32?

Quando ho provato UUID per un url e ho convertito i byte uuid in base 64, ho potuto ridurre a 22 caratteri. Mi chiedo di poter ridurre ulteriormente.

Principalmente voglio convertire l'URL (massimo 1024 caratteri) in ID in corto.

Answer 1

Non esiste un numero in quanto è possibile utilizzare il numero massimo di URL in modo da evitare duplicati " per CRC32.

Il problema è che CRC32 può produrre duplicati, e non è una funzione di quanti valori ci si lancia, è una funzione di come appaiono quei valori.

Quindi potresti avere una collisione sul secondo url, se sei sfortunato.

Non dovresti basare il tuo algoritmo sulla produzione di un hash univoco, ma produci manualmente un valore univoco per ciascun URL.

Answer 2

Se stai già memorizzando l'URL completo in una tabella del database, un ID intero è piuttosto breve e può essere ridotto convertendolo in base 16, 64 o 85. Se puoi usare un UUID, puoi usa un numero intero, e potresti anche, dato che è più corto e non vedo quale beneficio fornirebbe un UUID nella tua tabella di ricerca.

Answer 3

Il modo giusto per creare un breve URL è quello di memorizzare quello completo nel database e pubblicare qualcosa che sia mappato all'indice di riga. Un modo compatto è usare Base64 dell'ID riga, ad esempio. Oppure potresti usare un UID per la chiave primaria e mostrarlo.

Non utilizzare un checksum, perché è troppo piccolo e molto probabilmente in conflitto. Un hash crittografico è più grande e meno probabile, ma non è ancora la strada giusta da percorrere.

Answer 4

CRC32 significa controllo di ridondanza ciclico con 32 bit in cui qualsiasi somma arbitraria di bit viene sommata fino a una somma di controllo a 32 bit. E le funzioni di somma dei controlli sono suriettive, il che significa che più valori di input hanno lo stesso valore di output. Quindi non è possibile invertire la funzione.

Answer 5

No, anche se usi md5 o qualsiasi altra somma di controllo, l'URL PUO 'ESSERE duplicato, tutto dipende dalla tua fortuna.

Quindi non creare una base URL unica su quella somma di controllo

Answer 6

Il modo più rapido (e forse il migliore!) per risolvere le cose potrebbe essere semplicemente quello di utilizzare un hash del percorso locale e una query di un determinato URI, come 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();
        }
    }
}

Quanto sopra presume che lo schema URI e l'host rimangano gli stessi. Altrimenti GetHashCode funzionerà con qualsiasi stringa.

Per una grande discussione sulla visita di CRC32 Hash Collision: http://episteme.arstechnica.com/eve/forums/a/tpc/f/6330927813/m/821008399831