CRC32 pour créer une URL courte pour le Web

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

Question

J'essaie de comprendre que crc32 génère l'URL unique de la page Web.

Si nous utilisons crc32, quel est le nombre maximal d'URL pouvant être utilisées pour éviter les doublons?

Quelle pourrait être la longueur approximative de la chaîne pour que la somme de contrôle soit de 2 ^ 32?

Lorsque j'ai essayé UUID pour une URL et converti les octets uuid en base 64, je pouvais réduire la longueur à 22 caractères. Je me demande si je peux encore réduire.

Généralement, je souhaite convertir l'URL (1024 caractères maximum) en identifiant en court-circuit.

Était-ce utile?

La solution

Il n’existe pas de nombre tel que le "nombre maximal d’URL puisse être utilisé afin d’éviter les doublons". pour CRC32.

Le problème, c’est que CRC32 peut produire des doublons et que cela ne dépend pas du nombre de valeurs que vous lui attribuez, mais de l’apparence de ces valeurs.

Donc, vous pourriez avoir une collision sur la deuxième URL, si vous êtes malchanceux.

Vous ne devez pas baser votre algorithme sur la production d'un hachage unique, mais produire manuellement une valeur unique pour chaque URL.

Autres conseils

Si vous stockez déjà l'URL complète dans une table de base de données, un ID entier est assez court et peut être raccourci en le convertissant en base 16, 64 ou 85. Si vous pouvez utiliser un UUID, vous pouvez utilisez un entier, et vous pouvez aussi bien, car il est plus court et je ne vois pas quel avantage un UUID apporterait dans votre table de correspondance.

La bonne façon de créer une URL courte consiste à stocker l'intégralité de celle-ci dans la base de données et à publier quelque chose qui correspond à l'index de ligne. Une méthode compacte consiste à utiliser le Base64 de l'ID de ligne, par exemple. Vous pouvez également utiliser un UID pour la clé primaire et indiquer que.

N'utilisez pas de somme de contrôle, car elle est trop petite et très susceptible d'entrer en conflit. Un hachage cryptographique est plus gros et moins probable, mais ce n’est toujours pas la bonne façon de procéder.

CRC32 signifie contrôle de redondance cyclique avec 32 bits, où toute quantité arbitraire de bits est additionnée jusqu’à une somme de contrôle de 32 bits. Et les fonctions de somme de contrôle sont surjectives, ce qui signifie que plusieurs valeurs d'entrée ont la même valeur de sortie. Donc, vous ne pouvez pas inverser la fonction.

Non, même si vous utilisez md5 ou toute autre somme de contrôle, l’URL PEUT ÊTRE EN DOUBLE, tout dépend de votre chance.

Donc, ne créez pas une base d'URL unique sur ces sommes de contrôle

Le moyen le plus rapide (et peut-être même le meilleur!) de résoudre les problèmes consiste simplement à utiliser un hachage du chemin local et la requête d'un URI donné, comme suit: 

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

Ce qui précède suppose que le schéma d'URI et l'hôte restent les mêmes. Sinon, GetHashCode fonctionnera avec n’importe quelle chaîne.

Pour une discussion intéressante sur la collision de hachage CRC32, visitez: http://episteme.arstechnica.com/eve/forums/a/tpc/f/6330927813/m/821008399831

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top