Criar o seu próprio uid estilo Tinyurl

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

  •  07-07-2019
  •  | 
  •  

Pergunta

Eu estou escrevendo um pequeno artigo sobre alternativas humanamente legível para Guids / UIDs, por exemplo aqueles usados ??em TinyURL para os hashes URL (que muitas vezes são impressos em revistas, por isso, necessidade de ser curto).

O simples uid Estou geração é - 6 caracteres: ou uma letra minúscula (a-z) ou 0-9.

"De acordo com meus cálculos capitão", que é 6 eventos mutuamente exclusivos, embora o cálculo da probabilidade de um choque fica um pouco mais difícil do que P (A ou B) = P (A) + P (B), como, obviamente, inclui números e do código abaixo, você pode ver ele funciona se pretende utilizar um número ou uma letra usando 50/50.

Estou interessado na taxa de choque e se o código abaixo é uma simulação realista da taxa de confronto antecipado que você deseja obter de gerar um hash. Em média eu recebo 40-50 confrontos por milhão, no entanto ter em mente o uid não seria gerado um milhão de vezes de uma vez, mas provavelmente apenas cerca de 10-1000 vezes por minuto.

Qual é a probabilidade de um conflito cada vez, e alguém pode sugerir uma maneira melhor de fazer isso? 

static Random _random = new Random();

public static void main()
{
    // Size of the key, 6
    HashSet<string> set = new HashSet<string>();
    int clashes = 0;
    for (int n=0;n < 1000000;n++)
    {
        StringBuilder builder = new StringBuilder();

        for (int i =0;i < 7;i++)
        {
            if (_random.NextDouble() > 0.5)
            {
                builder.Append((char)_random.Next(97,123));
            }
            else
            {
                builder.Append(_random.Next(0,9).ToString());
            }
        }

        if (set.Contains(builder.ToString()))
        {
            clashes++;
            Console.WriteLine("clash: (" +n+ ")" +builder.ToString());
        }

        set.Add(builder.ToString());
        _random.Next();
        //Console.Write(builder.ToString());
    }

    Console.WriteLine("Clashes: " +clashes);
    Console.ReadLine();
}

UPDATE: Aqui está o artigo resultante a partir desta questão

Eu realmente fez duas perguntas aqui, então eu estava traindo. A resposta que eu estava depois foi RCAR de, no entanto Sklivvz do também é a resposta para a 2ª parte (uma alternativa). É possível fazer um gerador de id único personalizado em um banco de dados, ou seria do lado do cliente (o que seria 2 possibilidade lê primeiro)?

A idéia geral eu estava depois foi o uso de IDs em bancos de dados ou outras lojas que podem ser usados ??por telefone ou material impresso, não um gigante de 16 bytes guid.

UPDATE 2: Eu coloquei a fórmula para dois eventos mutuamente exclusivos acima em vez de 2 são independentes (como a obtenção de um 'a' pela primeira vez não significa que você não pode obter um 'a ' a segunda vez). Deveria ter sido P (A e B) = P (A) x P (B)

Foi útil?

Solução

A probabilidade de uma colisão contra um ID específico é: 

p = ( 0.5 * ( (0.5*1/10) + (0.5*1/26) ) )^6

que é cerca de 1,7 × 10 ^ -9.

A probabilidade de uma colisão depois de gerar n IDs é de 1-p ^ n, assim você terá uma chance aproximadamente 0,17% de uma colisão para cada nova inserção após 1 milhão de IDs foram inseridas, em torno de 1,7%, depois 10 milhões IDs, e cerca de 16% após 100 milhões.

1000 IDs / minuto funciona a cerca de 43 milhões / mês, de modo Sklivvz apontou, usando algum ID incremento é provavelmente vai ser a melhor maneira de ir neste caso.

EDIT:

Para explicar a matemática, ele está essencialmente lançando uma moeda e, em seguida, escolher um número ou letra 6 vezes. Há uma probabilidade de 0,5 que os jogos de aleta de moedas, e, em seguida, 50% do tempo, há uma possibilidade de 10/01 de harmonização e uma possibilidade de 50% de um 26/01 possibilidade de correspondência. Isso acontece 6 vezes de forma independente, para que se multiplicam essas probabilidades juntos.

Outras dicas

Por que você quer usar uma função aleatória? Eu sempre assumido que tinyurl utilizada uma base 62 (0-9A-Za-z) representação de uma Id sequencial. Não há confrontos e os URLs são sempre o mais curto possível.

Você teria uma tabela DB como 

Id  URL
 1  http://google.com
 2  ...
... ...
156 ...
... ...

e os URLs correspondentes seria: 

http://example.com/1
http://example.com/2
...
http://example.com/2W
...

Procure a aniversário Paradox , é o problema exato que você está correndo em.

A pergunta é: Quantas pessoas que você precisa para se reunir em uma sala, de modo que você tem uma chance de 50% de quaisquer duas pessoas com a mesma data de nascimento? A resposta pode surpreendê-lo.

Algum tempo atrás eu fiz exatamente isso, e eu segui o caminho Sklivvz mencionado. Toda a lógica foi desenvolvido com um procedimento armazenado servidor SQL e um par de UDF (funções definidas pelo usuário). Os passos foram:

  • dizer que você quer encurtar este url: Criar o seu próprio uid estilo Tinyurl
  • Insira o URL em uma tabela
  • Obtenha o valor @@ identidade da última inserção (a id numérico)
  • Transformar o id em um valor alfanumérico correspondente, com base em um "domínio" de letras e números (eu realmente usado este conjunto: "0123456789abcdefghijklmnopqrstuvwxyz")
  • Retorno esse valor de volta, algo como 'CC0'

A conversão foi realizada através de um par de muito curto UDF.

conversão Two chamado um após o outro voltaria valores "seqüenciais" como estes: 

select dbo.FX_CONV (123456) -- returns "1f5n"

select dbo.FX_CONV (123457) -- returns "1f5o"

Se você estiver interessado eu posso compartilhar o código do UDF.

Por que não usar um algoritmo de hash? e usar um hash da url?

Se você estiver usando números aleatórios chances são que você vai ter confrontos, porque eles são indeterminadas.

hashes Arent proovably única, mas há uma boa chance de que o hash de uma string será único.

Correção

Na verdade esperar que você quer que eles sejam humanamente legível ... se você colocá-los em hexadecimal que eles são tecnicamente humanamente legível.

ou você poderia usar um algoritmo que converteu um hash em uma string legível humanamente. se a cadeia legível, é uma representação diferente do hash também deve ser como "único" como o hash, isto é, base 36 do hash originais.

Eu iria gerar um valor representativo aleatória dos dados que você está indo para hash e, em seguida, hash que e clahses verificação ao invés de tentar simular com aleatórias hashes feitas manualmente. Isto lhe dará um indicador melhor. E você terá mais aleatoriedade, porque você vai ter mais a Randomize (Supondo que seus dados sejam hash é maior :)).

Se você estiver usando 6 caracteres, a-z e 0-9, isso é um total de 36 caracteres. O número de permutações é, assim, 36 ^ 6, que é 2176782336 .. por isso só deve colidir 1/2176782336 vezes.

wikipedia :

Ao imprimir menos caracteres é desejada, GUIDs são às vezes codificado em uma string base64 ou ASCII85. Base64-codificado GUID consiste de 22 a 24 caracteres (dependendo do preenchimento), por exemplo: 

7QDBkvCA1+B9K/U0vrQx1A
7QDBkvCA1+B9K/U0vrQx1A==
encoding

e ASCII85 dá apenas 20 caracteres, e. g:. 

5:$Hj:Pf\4RLB9%kU\Lj

Então, se você está preocupado com exclusividade, um base64 codificado GUID você fica um pouco mais perto do que você quer, mas os seus não 6 caracteres.

O seu melhor para trabalho em bytes em primeiro lugar, em seguida, traduzir esses bytes em hexadecimal para exibição, em vez de trabalhar com personagens diretamente.

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