Таким образом, вы хотите вычисление хеш-кода, которое дает одинаковые результаты для «picture» и «turepic», но (предпочтительно) отличается от хеш-кода, например, «eruptic».Таким образом, недостаточно просто сложить хеш-коды букв, содержащихся в слове - вам также необходимо иметь некоторую информацию о позиции, но, тем не менее, она не должна зависеть от фактической перестановки слова.Вам необходимо определить «классы эквивалентности» и всегда вычислять один и тот же хэш-код для каждого члена класса.
Самый простой способ добиться этого - выбрать определенный член класса эквивалентности и всегда использоватьхеш-код этого варианта для всех эквивалентных слов .Например, выберите первый вариант в алфавитном порядке (спасибо @Michael за краткое изложение).Для «изображения» и др. Это будет «cturepi».И «picture», и «turepic» (и все другие эквивалентные варианты) должны возвращать хеш-код «cturepi».Этот хэш-код может быть рассчитан стандартным методом LinkedList или любым другим предпочтительным способом.
Можно сказать, что это вычисление очень дорого.Правда, однако можно кэшировать результат, так что только первый расчет будет дорогостоящим.И я предполагаю, что выбор первого алфавитного варианта мог бы быть довольно оптимизирован в общем случае (по сравнению с тривиальным решением генерации всех перестановок в определенном классе эквивалентности, затем сортировки их и выбора первого).
Например, во многих словах первая буква в алфавитном порядке уникальна («картинка» является одним из них - ее первая буква в алфавитном порядке - «с», и в ней только одна буква «с»).Так что вам нужно только найти его, а затем вычислить хеш-код, начиная с этого.Если он не уникален, вам нужно сравнивать вторую, третью и т. Д. Буквы после этого, пока не найдете разницу (или вы не перевернетесь).
Обновление 2 - примеры
- "Абракадабра" содержит 5 'а.Вторые символы после «а» - это «b», «c», «d», «b» и «a» соответственно.Таким образом, во 2-м раунде сравнения вы можете сделать вывод, что лексикографически наименьшее изменение - это «aabracadabr».
- «abab» содержит 2 «a» и «b» после каждого (а затем вы переворачиваетесь, достигаяснова «а», так что квест заканчивается там).Таким образом, у вас есть два идентичных лексикографически самых маленьких варианта этого.Но так как они идентичны, они, очевидно, производят один и тот же хэш-код.
Обновление: В конце концов, все сводится к тому, насколько вам на самом деле нужен хеш-код - т.е.Вы планируете поместить свои циклические списки в ассоциативную коллекцию, такую как Set или Map.Если нет, вы можете сделать это с помощью простого или даже тривиального метода хеширования.Но если вы интенсивно используете некоторую ассоциативную коллекцию, тривиальная реализация хеш-функции дает вам множество коллизий, таким образом, неоптимальную производительность.В этом случае стоит попробовать реализовать этот метод хеширования и измерить, окупается ли он за производительность.
Обновление 3: пример кода
Letter в основном остается таким же, как указано вышеЯ только сделал поля private, переименовал theNextNode в next и добавил геттеры / установщики по мере необходимости.
В CircularWord я сделал еще несколько изменений: упал tail и theCurrentNode и сделал слово действительно круглым (то есть last.next == head).Конструктор toString и equals не имеют отношения к вычислению хеш-кода, поэтому для простоты они опущены.
public class CircularWord {
private final Letter head;
private final int numberOfElements;
// constructor, toString(), equals() omitted
@Override
public int hashCode() {
return hashCodeStartingFrom(getStartOfSmallestRotation());
}
private Letter getStartOfSmallestRotation() {
if (head == null) {
return null;
}
Set<Letter> candidates = allLetters();
int counter = numberOfElements;
while (candidates.size() > 1 && counter > 0) {
candidates = selectSmallestSuccessors(candidates);
counter--;
}
return rollOverToStart(counter, candidates.iterator().next());
}
private Set<Letter> allLetters() {
Set<Letter> letters = new LinkedHashSet<Letter>();
Letter letter = head;
for (int i = 0; i < numberOfElements; i++) {
letters.add(letter);
letter = letter.getNext();
}
return letters;
}
private Set<Letter> selectSmallestSuccessors(Set<Letter> candidates) {
Set<Letter> smallestSuccessors = new LinkedHashSet<Letter>();
char min = Character.MAX_VALUE;
for (Letter letter : candidates) {
Letter nextLetter = letter.getNext();
if (nextLetter.getValue() < min) {
min = nextLetter.getValue();
smallestSuccessors.clear();
}
if (nextLetter.getValue() == min) {
smallestSuccessors.add(nextLetter);
}
}
return smallestSuccessors;
}
private Letter rollOverToStart(int counter, Letter lastCandidate) {
for (; counter >= 0; counter--) {
lastCandidate = lastCandidate.getNext();
}
return lastCandidate;
}
private int hashCodeStartingFrom(Letter startFrom) {
int hash = 0;
Letter letter = startFrom;
for (int i = 0; i < numberOfElements; i++) {
hash = 31 * hash + letter.getValue();
letter = letter.getNext();
}
return hash;
}
}
Алгоритм, реализованный в getStartOfSmallestRotation для нахождения лексикографически наименьшего поворотаслова в основном то, что я описал выше: сравнивайте и выбирайте лексикографически наименьшие 1-ю, 2-ю, 3-ю и т. д. буквы каждого вращения, отбрасывая большие буквы, пока не останется только один кандидат, или вы не перевернете слово.Поскольку список циклический, я использую счетчик, чтобы избежать бесконечного цикла.
В конце концов, если у меня останется один кандидат, это может быть в середине слова, и мне нужно получить начало наименьшего поворота слова. Однако, поскольку это односвязный список, неловко в нем отступать. К счастью, счетчик приятно помогает мне: он записал, сколько букв я сравнил до сих пор, но в круговом списке это эквивалентно тому, сколько букв я могу переместить вперед, прежде чем перевернуться. Таким образом, я знаю, сколько букв нужно продвинуть, чтобы снова попасть в начало минимального поворота слов, которое я ищу.
Надеюсь, это кому-нибудь поможет - по крайней мере, было весело написать: -)