Создание Вашего собственного Tinyurl разрабатывает uid

Я пишу маленькую статью о по-человечески читаемых альтернативах Guids/UIDs, например, используемые на TinyURL для хешей URL (которые часто печатаются в журналах, так должно быть коротким).

Простой uid, который я генерирую, - 6 символов: или строчная буква (a-z) или 0-9.

"По словам моего капитана вычислений", это - 6 взаимоисключающих событий, хотя вычисляя вероятность столкновения, становится немного более твердым, чем P (A или B) = P (A) + P (B), поскольку, очевидно, это включает числа и из кода ниже, Вы видите, что это удается, использовать ли число или букву с помощью 50/50.

Я интересуюсь уровнем столкновения и если бы код ниже является реалистическим моделированием ожидаемого уровня столкновения, Вы добрались бы от генерации хеша. В среднем я получаю 40-50 столкновений на миллион, однако пустой в памяти, uid не был бы сгенерирован миллион раз сразу, но вероятно только приблизительно 10-1000 раз в минуту.

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

static Random _random = new Random();

public static void main()
{
    // Size of the key, 6
    HashSet set = new HashSet();
    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();
}

ОБНОВЛЕНИЕ: вот получающаяся статья от этого вопроса

Я действительно задал два вопроса здесь, таким образом, я обманывал. Ответ, которым я был после, был rcar's, однако Sklivvz является также ответом на 2-ю часть (альтернатива). Действительно ли возможно сделать пользовательский генератор уникального идентификатора в базе данных, или это была бы сторона клиента (который будет 2 возможными чтениями сначала)?

Общее представление, которым я был после, использовало Ids в базах данных или других хранилищах, которые могут использоваться телефоном или распечатали материал, не гигантский 16-байтовый гуид.

ОБНОВЛЕНИЕ 2: Я поместил формулу для двух взаимоисключающих событий выше вместо 2 независимых (как получение, первый раз не означает, что Вы не можете добраться во второй раз). Должен был быть P (A и B) = P (A) x P (B)

17
задан Chris S 14 August 2012 в 17:10
поделиться

8 ответов

Вероятность коллизии против одного определенного идентификатора:

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

, который является вокруг 1.7Г — 10^-9.

вероятность коллизии после генерации n идентификаторы является 1-p^n, таким образом, у Вас будет примерно шанс на 0,17% коллизии для каждой новой вставки после того, как 1 миллион идентификаторов был вставлен, приблизительно 1,7% после 10 миллионов идентификаторов и приблизительно 16% после 100 миллионов.

1 000 идентификаторов/минута удаются к приблизительно 43 миллионам/месяц, поэтому поскольку Sklivvz, на который указывают, с помощью некоторого идентификатора постепенного увеличения, вероятно, будет лучшим способом пойти в этом случае.

РЕДАКТИРОВАНИЕ:

Для объяснения математики он по существу бросает монетку и затем выбирает времена буквы 6 или число. Существует 0,5 вероятности, что подбрасывание монеты соответствует, и затем 50% времени существует 1/10 шанс соответствия и 50%-й шанс 1/26 шанса соответствия. Это происходит 6 раз независимо, таким образом, Вы умножаете те вероятности вместе.

4
ответ дан 30 November 2019 в 10:59
поделиться

Почему Вы хотите использовать случайную функцию? Я всегда предполагал, что tinyurl использовал основу 62 (0-9A-Za-z) представления последовательного идентификатора. Никакие столкновения и URL не всегда максимально коротки.

у Вас была бы Таблица базы данных как

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

, и соответствующие URL будут:

http://example.com/1
http://example.com/2
...
http://example.com/2W
...
31
ответ дан 30 November 2019 в 10:59
поделиться

Некоторое время назад я сделал точно это, и я следовал за способом, которым упомянул Sklivvz. Целая логика была разработана с хранимой процедурой SQL-сервера и несколькими UDF (определяемые пользователем функции). Шаги были:

  • говорят, что Вы хотите сократить этот URL: Создание Вашего собственного uid
  • стиля Tinyurl Вставляет URL в таблицу
  • , Получают @@, значение идентификационных данных последней вставки (числовой идентификатор)
  • Преобразовывает идентификатор в соответствующее алфавитно-цифровое значение, на основе "домена" букв и чисел (я на самом деле использовал этот набор: "0123456789abcdefghijklmnopqrstuvwxyz")
  • Возврат, которые оценивают назад, что-то как 'cc0'

преобразование, был понят через несколько очень коротких UDF.

Два преобразования, названные один за другим, возвратили бы "последовательные" значения как они:

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

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

, Если Вам интересно, я могу совместно использовать код UDF.

5
ответ дан 30 November 2019 в 10:59
поделиться

Почему не только используют алгоритм хеширования? и используйте хеш URL?

, если Вы используете возможности случайных чисел, Вы, получит столкновения, потому что они неопределенны.

хеши не доказуемо уникальны, но существует довольно хороший шанс, что хеш строки будет уникален.

Исправление

На самом деле ожидает, Вы хотите, чтобы они были по-человечески читаемы..., при помещении их в шестнадцатеричное число, они технически по-человечески читаемы.

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

0
ответ дан 30 November 2019 в 10:59
поделиться

Я генерировал бы случайного представителя значения данных, которые Вы собираетесь хешировать, и затем хешировать это и проверить clahses вместо того, чтобы пытаться моделировать со случайными вручную сделанными хешами. Это даст Вам лучший индикатор. И у Вас будет больше случайности, потому что у Вас будет больше для рандомизации (Предположение, что данные, которые будут хешированы, больше :)).

0
ответ дан 30 November 2019 в 10:59
поделиться

Если Вы используете 6 символов, a-z и 0-9, это - в общей сложности 36 символов. Количество перестановок таким образом 36^6, который равняется 2176782336.. таким образом, это должно только столкнуться 1/2176782336 времена.

0
ответ дан 30 November 2019 в 10:59
поделиться

от Википедия :

, Когда печать меньшего количества символов желаема, GUID иногда кодируются в строку Ascii85 или base64. Base64-закодированный GUID состоит из 22 - 24 символов (в зависимости от дополнения), например:

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

и кодирование Ascii85 дает только 20 символов, например:

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

Поэтому, если Вы обеспокоены уникальностью, base64, закодированный, GUID получает Вас несколько ближе к тому, что Вы хотите, хотя не 6 символов.

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

0
ответ дан 30 November 2019 в 10:59
поделиться

Ищите День рождения Paradox , это - точная проблема, с которой Вы сталкиваетесь.

вопрос: Сколько людей необходимо собраться в комнате, так, чтобы у Вас был 50%-й шанс каких-либо двух человек, имеющих ту же дату рождения? Ответ может удивить Вас.

6
ответ дан 30 November 2019 в 10:59
поделиться
Другие вопросы по тегам:

Похожие вопросы: