我应该如何为Java中的循环链表定义一个好的hashCode？

Question

我已经设置了一个表示单词的循环链表数据结构,列表中的每个元素都是单词中的一个字母.在我的问题的底部是列表的类定义和列表的元素.

列表数据结构的目的是能够比较循环词.所以......"picture"和"turepic"是相同的循环词,所以这两个列表是相同的.

所以我equals()在比较两个列表时会覆盖,而且我已经读过,每当你必须覆盖时equals(),你也必须覆盖hashCode().但是,我真的不知道如何做到这一点.

我应该如何为我设置的内容定义一个好的hashCode？我应该考虑什么？在"picture"和"turepic"的例子中,两个列表是相同的,因此它们的hashCode需要相同.有任何想法吗？

谢谢,Hristo

public class Letter {
 char value;
 Letter theNextNode;

 /**
  * Default constructor for an element of the list.
  * 
  * @param theCharacter - the value for this node.
  */
 Letter(char theCharacter) {
  this.value = theCharacter;
 }
}


public class CircularWord {

 /*
  * Class Variables
  */
 Letter head;
 Letter tail;
 Letter theCurrentNode;

 int iNumberOfElements;


 /**
  * Default Constructor. All characters that make up 'theWord' are stored in a 
  * circular linked list structure where the tail's NEXT is the head. 
  */
 public CircularWord(String theWord) {

  char[] theCharacters = theWord.toCharArray();

  for (int iIndex = 0; iIndex < theCharacters.length; iIndex++) {
   this.addElement(theCharacters[iIndex]);
  }

  this.theCurrentNode = head;
  this.iNumberOfElements = theCharacters.length;
 }
}

Answer 1

因此,您需要一个哈希码计算,它为"picture"和"turepic"提供相同的结果,但(最好)与例如"eruptic"的哈希码不同.因此,仅仅添加单词中包含的字母的哈希码是不够的 - 您还需要一些位置信息,但是,它应该独立于单词的实际排列.您需要定义"等价类",并始终为该类的每个成员计算相同的哈希码.

实现此目的的最简单方法是选择等价类的特定成员,并始终对所有等效单词使用该变体的哈希码.例如,按字母顺序选择第一个变体(感谢@Michael简明扼要地总结).对于"picture"等人来说,这将是"cturepi"."picture"和"turepic"(以及所有其他等效变体)都应该返回"cturepi"的哈希码.该哈希码可以通过标准LinkedList方法或任何其他优选方式来计算.

有人可能会说这种计算非常昂贵.是的,但是可以缓存结果,因此只有第一次计算才会成本高昂.我想在第一种情况下可以相当优化第一个字母变量的选择(与在特定等价类中生成所有排列,然后对它们进行排序并选择第一个)的简单解决方案相比较.

例如,在许多单词中,第一个字母按字母顺序排列是唯一的("图片"是其中之一 - 它的第一个字母按字母顺序排列为'c',其中只有一个'c').所以你只需要找到它,然后从那里开始计算哈希码.如果它不是唯一的,则需要比较之后的第二个,第三个等字母,直到找到差异(或翻转).

更新2 - 示例

• "abracadabra"包含5'a'.'a'之后的第2个字符分别是'b','c','d','b'和'a'.因此,在第二轮比较中,您可以得出结论,按字典顺序排列的最小变化是"aabracadabr".
• "abab"包含2'a',并且在每个之后包含'b'(然后你翻身,再次达到'a',所以任务结束那里).因此,您有两个相同的词典编码最小的变体.但由于它们是相同的,因此它们显然会生成相同的哈希码.

更新:最后,这一切归结为您实际需要多少哈希码 - 即您是否计划将您的循环列表放入像Set或的关联集合中Map.如果没有,您可以使用简单的,甚至是简单的哈希方法.但是如果你大量使用一些关联集合,那么一个简单的哈希实现会给你带来很多冲突,从而导致性能欠佳.在这种情况下,值得尝试实现这种哈希方法并测量它是否在性能上付出代价.

更新3:示例代码

Letter基本上和上面一样,我只根据需要创建了字段private,重命名theNextNode为next,并添加了getter/setter.

在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等字母,丢弃更大的字母,直到只剩下一个候选者为止或者你滚过这个词.由于列表是循环的,我使用计数器来避免无限循环.

最后,如果我剩下一个候选者,它可能在单词的中间,我需要得到最小单词旋转的开始.但是,由于这是一个单链表,所以向前退一步是很尴尬的.幸运的是,计数器很好地帮助了我:它已经记录了我到目前为止已经比较了多少个字母,但是在一个循环列表中,这相当于我可以在翻滚之前向前移动多少个字母.因此,我知道要向前移动多少个字母,以便再次进入我正在寻找的最小单词旋转的开始.

希望这有助于某人 - 至少写起来很有趣:-)

Answer 2

你真的需要使用你的hashCodes吗？如果您不打算将对象成员放在任何类型的哈希结构中,您可以忽略该问题:

public int hashCode() {
    return 5;
}

这满足了相等实例具有相同哈希码的要求.除非我知道我需要更好的哈希分布,否则这可能足以满足我自己的需求.

但我想我可能有一个能够更好地分配哈希的想法.伪代码:

hash = 0
for each rotation
    hash += hash(permutation)
end
hash %= MAX_HASH

由于hash()可能是O(n),那么这个算法是O(n ^ 2),这有点慢,但是哈希反映了用于等价测试的方法,哈希码的分布可能相当不错.任何其他可交换的内核(prod,xor)都可以和本例中使用的总和一样工作.

Answer 3

列表中所有元素的哈希码之和（每个元素乘以任意值）怎么样？

就像是

hashCode = 1;
for (char c : myChars) {
    hashCode += 31 * c;
}