Функцию, похожую на хэш, с коротким непоследовательным дайджестом и без коллизий?

Для целых в диапазоне 0..M надо получать n-символьные соответствия, не выглядящие последовательными:

0 JZQ736
1 KVYZ97
2 PW7NB3


Подскажите ф-ю f(i) = s, чтобы в заданном диапазоне получать такие микро-хэши без коллизий. А совсем круто было бы и обратную ф-ю f1(s) = i чтобы из кода получать целое, или узнать, что код левак.


Криптостойкость не требуется, это для маркетинговой красоты билетов.
  • Вопрос задан
  • 7191 просмотр
Решения вопроса 1
@MikeMirzayanov
Можно так. Работает для всех m от 1 до MOD-1. Если не хватает, то можно либо увеличить константы (тогда может вырасти длина), либо чуток адаптировать алгоритм. Я подогнал, чтобы было как в примере 6 знаков в коде. На самом деле можно все делать в 64-битных переменных, просто так на Java удобнее.

    private static final BigInteger MULTIPLIER = BigInteger.valueOf(13L);
    private static final BigInteger MOD = BigInteger.valueOf(99990001L);
    private static final BigInteger ADDEND = BigInteger.valueOf(699930007L);

    public static String encode(long m) {
        if (m <= 0 || m >= MOD.longValue()) {
            throw new IllegalArgumentException("Argument is out of range.");
        }
        return BigInteger.valueOf(m).modInverse(MOD).multiply(MULTIPLIER)
                .add(ADDEND).toString(36).toUpperCase();
    }

    public static long decode(String encoded) {
        return new BigInteger(encoded.toLowerCase(), 36).subtract(ADDEND).divide(MULTIPLIER)
                .modInverse(MOD).longValue();
    }


Вот примеры того, что получается (для разных m):

1 BKPXGK
2 MBOAIK
3 PWNQV8
4 RP5H1K
5 SRUICK
10000 X2JV9T
10001 PWMTFN
10002 U025II
10003 TRK6AU
10004 JRJEMK
10005 UARMRU
10006 S2NCNJ
10007 R1E1UK
10008 HRCMBX
10009 WU4GN7
99989996 FVI2O7
99989997 GY73Z7
99989998 IQOU5J
99989999 MBOAI7
99990000 X2MNK7
Ответ написан
Пригласить эксперта
Ответы на вопрос 8
xanep
@xanep
Вам не нужна хэш функция, т.к. обратно не сможете конвертировать, да и коллизии возможны в любом случае. Лучшее решение для вас — перевести из десятеричнойной системы счисления в N-ричную, где N — количество символов, которые вы хотите использовать (26 букв латинского алфавита + 10 цифр?). Как это сделать написано на вики. Чтоб числа не выглядели последовательно, можно обернуть биты исходного числа в обратном порядке.
Ответ написан
CKOPOBAPKuH
@CKOPOBAPKuH
> Подскажите аналог хэш-функций, но короче, и без коллизий?

в такой постановке вам может помочь единорог.
Ответ написан
Sivkoff
@Sivkoff
Web Developer
Всем доброго времени суток.
Если кому-то нужно, реализовал алгоритм @MikeMirzayanov на php.
Ответ написан
@gribozavr
Математический подход: возьмите два простых числа, a и m, причём M < a < m, m — наибольшее простое, меньшее чем {мощность алфавита}^{количество символов в коде}. f(i) = i * a (mod m), f(s) = i * a^-1 (mod m), где a^-1 — обратное к a по модулю m.

Программистский подход: f(i) = биты числа i в обратном порядке. Тогда у последовательных билетов коды не будут казаться последовательными. После преобразования в строку можно добавить случайных символов в фиксированные места.
Ответ написан
AlexanderG
@AlexanderG
Попробуйте использовать какой-либо ГПСЧ (генератор псевдослучайных чисел), в качестве зерна берите ваш индекс. Поскольку числа псевдослучайные, каждому зерну будет однозначно соответствовать известный результат, что удовлетворяет условию задачи. Например, линейный конгруэнтный метод может подойти: он отображает зерно в единственный результат; позволяет выполнить обратное преобразование; прост в реализации.
Ответ написан
Gokjer
@Gokjer
В случае не очень больших M можно нагенерить M рандомных n-символьных комбинаций(проверяя на уникальность пиханием в какой-нибудь словарь/дерево/..), сопоставить каждому числу комбинацию по порядку и просто их запомнить.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы