Ответ 1

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

Какая польза для этой проблемы - это псевдослучайная перестановка между инкрементным идентификатором и его партнером, который будет отображаться в URL-адресе. Этот метод гарантирует, что столкновение невозможно, но при этом генерируется в пространство вывода, которое меньше входного.

Реализация

Я предлагаю эту версию С# шифр Feistel с 32-битными блоками, 3 раундами и круглой функцией который вдохновлен псевдослучайными генераторами.

private static double RoundFunction(uint input)
{
    // Must be a function in the mathematical sense (x=y implies f(x)=f(y))
    // but it doesn't have to be reversible.
    // Must return a value between 0 and 1
    return ((1369 * input + 150889) % 714025) / 714025.0;
}

private static uint PermuteId(uint id)
{
    uint l1=(id>>16)&65535;
    uint r1=id&65535;
    uint l2, r2;
    for (int i = 0; i < 3; i++)
    {
        l2 = r1;
        r2 = l1 ^ (uint)(RoundFunction(r1) * 65535);
        l1 = l2;
        r1 = r2;
    }
    return ((r1 << 16) + l1);
}

Чтобы выразить переменный ID в строке base62:

private static string GenerateCode(uint id)
{
    return ToBase62(PermuteId(id));
}

Функция Base62 совпадает с предыдущим ответом, за исключением того, что принимает uint вместо int (иначе эти функции пришлось бы переписать для решения отрицательных значений).

Настройка алгоритма

RoundFunction - секретный соус алгоритма. Вы можете изменить его на непубличную версию, возможно, включая секретный ключ. Сеть Feistel имеет две очень приятные свойства:

• даже если поставляемый RoundFunction не обратим, алгоритм гарантирует, что PermuteId() будет перестановкой в ​​математическом смысле (подразумевает нулевое столкновение).

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

Остерегайтесь того, что положить что-то слишком тривиальное в круглое выражение может испортить псевдослучайный эффект, хотя он все равно будет работать с точки зрения уникальности каждого вывода PermuteId. Кроме того, выражение, которое не было бы функцией в математическом смысле, было бы несовместимо с алгоритмом, поэтому, например, ничего, связанное с random(), не допускается.

Reversability

В своей текущей форме функция PermuteId является ее собственным обратным, что означает, что:

PermuteId(PermuteId(id))==id

Поэтому, если вы указали короткую строку, создаваемую программой, если вы переведете ее обратно в uint с помощью функции FromBase62 и дадите ее как вход в PermuteId(), которая вернет соответствующий начальный идентификатор. Это довольно круто, если у вас нет базы данных для хранения отношений [internal-ID/shortstring]: их фактически не нужно хранить!

Создание еще более коротких строк

Диапазон вышеуказанной функции - 32 бита, то есть около 4 миллиардов значений от 0 до 2^32-1. Чтобы выразить этот диапазон в base62, требуется 6 символов.

Имея всего 5 символов, мы можем надеяться представить не более 62^5 значения, что немного меньше 1 миллиарда. Если строка вывода ограничена 5 символами, код должен быть изменен следующим образом:

• найдите N, чтобы N был четным, а 2^N был как можно выше, но ниже 62^5. Это 28, поэтому наш реальный диапазон вывода, который находится в 62^5, будет 2^28 или около 268 миллионов значений.

• в PermuteId используйте 28/2=14 значения битов для l1 и r1 вместо 16 бит, при этом старайтесь не игнорировать один бит ввода (который должен быть меньше 2 ^ 28).

• умножьте результат RoundFunction на 16383 вместо 65535, чтобы оставаться в пределах 14 бит.

• в конце PermuteId, рекомбинируйте r1 и l1, чтобы сформировать значение бита 14+14=28 вместо 32.

Тот же метод может применяться для 4 символов с диапазоном вывода 2^22 или около 4 миллионов значений.

Как выглядит

В вышеприведенной версии первые 10 строк, начинающихся с id = 1, следующие:

cZ6ahF
3t5mM
xGNPN
dxwUdS
ej9SyV
cmbVG3
cOlRkc
bfCPOX
JDr8Q
eg7iuA

Если я делаю тривиальное изменение в круглой функции, это становится:

ey0LlY
ddy0ak
dDw3wm
bVuNbg
bKGX22
c0s5GZ
dfNMSp
ZySqE
cxKH4b
dNqMDA

Ответ 2

Вы можете представить пятибуквенный код как число в нотации base-62: ваши "цифры" - 26 строчных и 26 прописных букв и цифры от 0 до 9. (26 + 26 + 10) цифр в целом, Если число от 0 до 62^5 (что равно 916132832) (например, ваш первичный ключ), вы можете сделать преобразование в пятизначную базу-62 следующим образом:

private static char Base62Digit(int d) {
    if (d < 26) {
        return (char)('a'+d);
    } else if (d < 52) {
        return (char)('A'+d-26);
    } else if (d < 62) {
        return (char)('0'+d-52);
    } else {
        throw new ArgumentException("d");
    }
}

static string ToBase62(int n) {
    var res = "";
    while (n != 0) {
        res = Base62Digit(n%62) + res;
        n /= 62;
    }
    return res;
}

private static int Base62Decode(char c) {
    if (c >= '0' && c <= '9') {
        return 52 + c - '0';
    } else if (c >= 'A' && c <= 'Z') {
        return 26 + c - 'A';
    } else if (c >= 'a' && c <= 'z') {
        return c - 'a';
    } else {
        throw new ArgumentException("c");
    }
}

static int FromBase62(string s) {
    return s.Aggregate(0, (current, c) => current*62 + Base62Decode(c));
}

Вот как создать криптографически сильные случайные числа (вам нужно добавить ссылку на System.Security):

private static readonly RNGCryptoServiceProvider crypto =
    new RNGCryptoServiceProvider();

private static int NextRandom() {
    var buf = new byte[4];
    crypto.GetBytes(buf);
    return buf.Aggregate(0, (p, v) => (p << 8) + v) & 0x3FFFFFFF;
}

Ответ 3

Это то, что я закончил делать

(Обновлено после ответа Даниэля Верита):

class Program
{

    private static double RoundFunction(uint input)
    {
        // Must be a function in the mathematical sense (x=y implies f(x)=f(y))
        // but it doesn't have to be reversible.
        // Must return a value between 0 and 1
        return ((1369 * input + 150889) % 714025) / 714025.0;
    }
    private static char Base62Digit(uint d)
    {
        if (d < 26)
        {
            return (char)('a' + d);
        }
        else if (d < 52)
        {
            return (char)('A' + d - 26);
        }
        else if (d < 62)
        {
            return (char)('0' + d - 52);
        }
        else
        {
            throw new ArgumentException("d");
        }
    }
    private static string ToBase62(uint n)
    {
        var res = "";
        while (n != 0)
        {
            res = Base62Digit(n % 62) + res;
            n /= 62;
        }
        return res;
    }
    private static uint PermuteId(uint id)
    {
        uint l1 = (id >> 16) & 65535;
        uint r1 = id & 65535;
        uint l2, r2;
        for (int i = 0; i < 3; i++)
        {
            l2 = r1;
            r2 = l1 ^ (uint)(RoundFunction(r1) * 65535);
            l1 = l2;
            r1 = r2;
        }
        return ((r1 << 16) + l1);
    }


    private static string GenerateCode(uint id)
    {
        return ToBase62(PermuteId(id));
    }

    static void Main(string[] args)
    {

        Console.WriteLine("testing...");

            try
            {

                for (uint x = 1; x < 1000000; x += 1)
                {
                    Console.Write(GenerateCode(x) + ",");

                }

            }
            catch (Exception err)
            {
                Console.WriteLine("error: " + err.Message);
            }

        Console.WriteLine("");
        Console.WriteLine("Press 'Enter' to continue...");
        Console.Read();
    }
}