Двусторонняя строковая хеш-функция - PullRequest
Новая
       2

Двусторонняя строковая хеш-функция

4 голосов
/ 10 июля 2011

Я хочу получить уникальное числовое представление строки.Я знаю, что есть много способов сделать это, мой вопрос, какой, по вашему мнению, является лучшим?Я не хочу иметь отрицательные числа - так что функция hashcode () в java не так хороша, хотя я мог бы ее переопределить ... но я бы не хотел, потому что я не настолько уверен в себе и не хочу случайносломайте что-нибудь.

Мои строки - это семантическая сеть URIS.Причина числового представления заключается в том, что когда я отображаю данные для URI на странице, мне нужно что-то передать в строку запроса или поместить в различные поля в моем JavaScript.Сам URI слишком громоздкий и выглядит плохо, когда в качестве значения URI указан URI.

В основном я хочу иметь класс с именем Resource, который будет выглядеть следующим образом 

Resource{
  int id;
  String uri;
  String value; // this is the label or human readable name

  // .... other code/getters/setters here

  public int getId(){
    return id = stringToIntFunction();
  }

  private int stringToIntFunction(String uri){
  // do magic here
  }
}

Можете ли вы предложить функцию, которая будет делать это, если:

  1. Это должно быть два пути, то есть вы также можете восстановить исходную строку из числового значения
  2. Это неНе должно быть двухстороннего

Также есть другие важные вопросы, которые я не рассматриваю?

Ответы [ 5 ]

12 голосов
/ 10 июля 2011

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

В частности, учитывая, что int имеет 32 бита информации, а char имеет 16 бит информации, что требует средств обратимостивы можете иметь только строки из нуля, одного или двух символов (и даже если вы предполагаете, что вы счастливы закодировать "" как "\ 0 \ 0" или что-то подобное).Конечно, если у вас нет хранилища.Если вы можете использовать хранилище, тогда просто сохраняйте числа последовательно ... что-то вроде: 

private int stringToIntFunction(String uri) {
    Integer existingId = storage.get(uri);
    if (existingId != null) {
        return existingId.intValue();
    }
    return storage.put(uri);
}

Здесь storage.put() внутренне увеличит счетчик, сохранит URI как связанный с этим значением счетчика и вернет его,Я предполагаю, что это не то, что вам нужно.

По сути, для выполнения обратимого шифрования я бы использовал стандартную библиотеку шифрования, предварительно преобразовав строку в двоичный формат (например, используя UTF-8).).Я ожидал бы, что результат будет byte[].

Если бы он не не должен был быть обратимым, я бы подумал просто взять абсолютное значение нормального hashCode() результата(но сопоставление Integer.MIN_VALUE с чем-то конкретным, поскольку его абсолютное значение не может быть представлено как int).

7 голосов
/ 10 июля 2011

Хэши только односторонние (это одна из причин, по которой они имеют фиксированную длину независимо от размера ввода).Если вам нужна двусторонняя связь, вы смотрите что-то вроде кодировки Base64.

Почему у вас не может быть отрицательных чисел?Откуда берутся URI?Они в базе данных?Почему бы не использовать идентификатор ключа базы данных?Если их нет в базе данных, можете ли вы сгенерировать их для пользователя с учетом набора переменных / параметров?(Таким образом, строка запроса содержит только такие вещи, как foo = 1 & bar = two, и вы генерируете URL на стороне сервера или JavaScript)

3 голосов
/ 10 июля 2011

Учитывая все переделчики, сделанные выше (хеш-функция является односторонней), я бы выбрал 2 возможных решения:

  • Используйте некоторую функцию шифрования, чтобы получить длинную строку, представляющую ваш URL (вы будетеполучить что-то вроде -> param = 456ab894ce897b98f (это может быть длиннее и / или короче в зависимости от URL). См., например, шифрование DES или base64url .
  • Отслеживание URL-адресов вбаза данных (может быть также простой файловой базой данных, такой как SQLite). Тогда у вас будет эффективная <=> эквивалентность URL-адреса.
2 голосов
/ 10 июля 2011

«Уникальное представление» подразумевает, что предоставленный Java string.hashcode будет бесполезен - вы скоро встретите два URI, которые используют один и тот же хэш-код.

Любая двусторонняя схема приведет к громоздкой строке - если только вы не сохраните URI в базе данных и не используете идентификатор записи в качестве уникального идентификатора.

Что касается одностороннего подхода - хеш MD5 будет значительно более уникальным (но отнюдь не уникальным), чем простой хеш-код, - но может зависеть от «громоздкости» в зависимости от вашего определения!

0 голосов
/ 10 июля 2011

Q1: Если вы хотите восстановить строку из числа, вы можете использовать:

1a: шифрование строки, которая будет того же размера или дольше, если вы сначала не заархивируете строку. Это даст массив произвольно выглядящих байтов, который может отображаться как Base-64.

1b: база данных или карта, а число - это индекс строки в карте / базе данных.

Q2: строка не подлежит восстановлению.

Здесь возможны различные идеи. Вы можете отобразить хеш в шестнадцатеричном или в Base-64, чтобы избежать отрицательных знаков. Единственные не буквенно-цифровые символы в Base-64 - это «+», «/» и «=». Для почти уникального хэша вам понадобится нечто криптографического размера, MD5 (128 бит), SHA-1 (160 бит) или SHA-2 (256 или 512 бит).

MD5-хеш выглядит как "d131dd02c5e6eec4693d9a0698aff95c" в шестнадцатеричном виде; чем больше хэш, тем меньше вероятность столкновения.

Россум

...