Уникальный хеш для одного и того же набора символов в любом порядке?

Рассмотрим этот пример поиска анаграмм

aabc
abca

Они оба являются анаграммами, я ищу способ, чтобы их хэш, сгенерированный символами, был одинаковым и уникальным.

Уникальность важна, так как никакие две разные строки aabc и xyaq не генерируют один и тот же хэш.

Я понятия не имею об этом, но меня тошнит здесь, чтобы узнать, что мне нужно искать


java string hash anagram
person daydreamer    schedule 17.02.2015    source источник
comment
То, что вы ищете, - это идеальная хэш-функция (при условии, что "aabc".equals("abca") в конечном Set и вместе представляют собой отдельный элемент в Set.). Ваше определение проблемы должно быть конечным, чтобы любой мог предложить решение.   -  person Deepak Bala    schedule 17.02.2015
comment
Хэши, по сути, никогда не будут уникальными. Либо разработайте приемлемый способ, либо найдите какой-нибудь подход без хеширования.   -  person Louis Wasserman    schedule 17.02.2015
comment
это идея   -  person Neha Agrawal    schedule 18.02.2015

Ответы (1)


arrow_upward
2
arrow_downward

Отсортируйте символы в строке и используйте их в качестве хэша. Строки будут иметь одинаковый хэш, если они являются анаграммами друг друга:

String anagramHash(String str) {
    char[] chars = str.toCharArray();
    Arrays.sort(chars);
    return new String(chars);
}

Это, вероятно, не сработает, если у вас есть кодовые точки, которых нет в BMP (http://docs.oracle.com/javase/7/docs/api/java/lang/Character.html).

В качестве альтернативы создайте гистограмму и используйте ее в качестве хэша.

person Adrian Leonhard    schedule 20.02.2015
comment
Разные строки могут иметь один и тот же хэш, поэтому часть if and only if не выполняется. - person toolforger; 25.10.2018