Страницы

Поиск по вопросам

пятница, 9 ноября 2018 г.

Подскажите функцию, похожую на хэш, но короче и без коллизий

Требуется генерировать из последовательных целых, уникальные непоследовательные n-значные коды. Представьте хэши, серийники, или номера купонов. Целочисленному id от 0 до K соответствует строго один n-значный код. И важно, чтобы последовательно идущие коды сильно различались, а не одним-двумя символами.
Пример:
0 KXBR6Z 1 8FLWGG 2 PAZT73
Из-за коллизий и краткости требуемых кодов, популярные хэш-функции не подходят. Криптостойкость не требуется. Если злодеи разгадают алгоритм, пусть хоть все коды распечатают. Делается для красоты. Хотя, рассмотреть, от чего зависит сложность отгадывания алгоритма по X имеющимся на руках кодам тоже интересно!
Вопрос: подскажите алгоритм / функцию f(i) = s для соответствия между множествами 0..K и n-значными ABC123XYZ. Обратная функция была бы тоже интересна: f1(s) = i чтобы из кода получить целое, либо узнать, что код невалиден.
Наверняка, задача не нова, но не придумал, как искать ответ. Требуется human-трансляция. )
P.S. ищу именно "математику", алгоритм, а не способ забить в БД уникальные значения, каждый раз при создании нового, проверяя уникальность.


Ответ

С такой задачей хорошо справляются шифры подстановки. Первое, что Вам надо сделать - это расширить алфавит (перейти от цифр к буквам, где несколько букв будут соответствовать одной цифре). Если для Вас очень важно скрыть исходные значение, то имеет смысл предварительно зашифровать данные блочным или асиметричным шифрованием. накидал пример кода с подстановкой, результат: input/encoded/decoded - 123 / efg / 123 input/encoded/decoded - 456 / hij / 456 input/encoded/decoded - 789 / abc / 789 input/encoded/decoded - 012 / def / 012 input/encoded/decoded - 1157232188 / eoiafgpybl / 1157232188 сам код: import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Map;
public class Substitution { private static final int NUMBER_COUNT = 10; private static final int LETTER_COUNT = 26; private static final int ZERO_ASCII_CODE = 48; private static final int A_CHAR_ASCII_CODE = 97;
// substitution tables private static final Map> numToChar = new HashMap>( NUMBER_COUNT); private static final Map charToNum = new HashMap( LETTER_COUNT);
// init tables static { // add list containers for (int i = 0; i < NUMBER_COUNT; i++) { numToChar.put(Character.valueOf((char) (ZERO_ASCII_CODE + i)), new LinkedList()); }
// init substitution table for (int i = A_CHAR_ASCII_CODE; i < A_CHAR_ASCII_CODE + LETTER_COUNT; i++) {
// number = (symbol ascii code) mod 9 Character num = Character .valueOf((char) (i % NUMBER_COUNT + ZERO_ASCII_CODE)); Character ch = Character.valueOf((char) i);
numToChar.get(num).add(ch); charToNum.put(ch, num); } }
public static void main(String[] args) { System.out.println("dumping straight substitution table"); for (Character num : numToChar.keySet()) { System.out.println("num to char - " + num + ", replacements = " + numToChar.get(num)); } System.out.println(); System.out.println("dumping reverse substitution table"); for (Character ch : charToNum.keySet()) { System.out.println("char to num - " + ch + ", replacements = " + charToNum.get(ch)); }
// test String[] nums = new String[] { "123", "456", "789", "012", "1157232188" }; String r = null; for (int i = 0; i < nums.length; i++) { r = decode(nums[i], true); System.out.println("input/encoded/decoded - " + nums[i] + " / " + r + " / " + decode(r, false)); }
}
public static String decode(String input, boolean direction) { // result buffer StringBuilder b = new StringBuilder(input.length());
// ensure all latters are in lower case String data = input.toLowerCase();
// store indexes (determines which letter to use when coding a number) Map indexes = new HashMap();
// encode string for (int i = 0; i < input.length(); i++) { b.append(decode(indexes, data.charAt(i), direction)); }
return b.toString(); }
// straight - number to letter // reverse - letter to number private static Character decode(Map indexes, char ch, boolean direction) { // convert character Character character = Character.valueOf(ch); if (direction) { // get list List list = numToChar.get(character);
// get index to use Integer index = indexes.get(character); if (null == index) { index = Integer.valueOf(0); }
// update index map int next = index.intValue() + 1; if (next == list.size()) { next = 0; }
indexes.put(character, Integer.valueOf(next));
return list.get(index); }
return charToNum.get(character); } } Данный пример строго "заточен" под цифры и буквы, но, по аналогии, можно сделать код который будет делать подстановки отдельных символов и/или их последовательностей

Комментариев нет:

Отправить комментарий