如何定义Java中循环链表的一个好的哈希代码?

如何计算列表中所有元素的哈希代码之和,每个元素乘以一个任意值?

有点像

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

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

最简单的方法是 选择等价类的特定成员,并始终对所有等价词使用该变量的哈希代码。 . 例如,按字母顺序选择第一个变体(感谢@michael简明地总结)。对于“picture”等,这将是“ecurepi”。“picture”和“turepic”(以及所有其他等效变体)都应返回“cturepi”的哈希代码。散列代码可以通过标准的LinkedList方法或任何其他首选方法计算。

有人可能会说这个计算非常昂贵。是的,但是可以缓存结果,这样只有第一次计算的开销才会很大。我猜在一般情况下,第一个字母变体的选择可以得到相当多的优化(与在特定的等价类中生成所有置换的平凡解相比,然后对它们进行排序并选择第一个置换)。

例如,在许多单词中,第一个字母按字母顺序是唯一的(“picture”是其中之一-其第一个字母按字母顺序是“c”,其中只有一个“c”)。所以你只需要找到它,然后从那里开始计算散列码。如果它不是唯一的,您需要比较第二个、第三个等字母,直到您发现不同之处(或翻滚)。

更新2-示例

• “abracadabra”包含5个“a”。“a”后面的第二个字符分别是“b”、“c”、“d”、“b”和“a”。因此,在第二轮比较中,你可以得出这样的结论:词典学上最小的变化是“aabracadabr”。
• “abab”包含2个“a”,每个“b”之后都包含一个“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 找到单词在词典上最小的旋转,基本上就是我上面所描述的:比较并选择每个旋转中在词典上最小的第一、第二、第三等字母,去掉较大的字母,直到只剩下一个候选字母,或者滚动单词。由于列表是循环的,所以我使用计数器来避免无限循环。

最后,如果我还有一个候选词,它可能在单词的中间,我需要得到最小单词旋转的开始。然而,由于这是一个单独的链表,所以向后退是很难的。幸运的是,计数器很好地帮助了我:它记录了到目前为止我比较了多少个字母,但在一个循环列表中,这相当于我可以向前移动多少个字母,然后滚动过来。因此,我知道要向前移动多少个字母,以便再次到达我正在寻找的最小单词旋转的开头。

希望这能帮助别人——至少写起来很有趣——)

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

public int hashCode() {
    return 5;
}

这满足了相同实例具有相同哈希代码的要求。除非我知道我需要一个更好的散列分布,否则这可能对我自己的需要足够好。

但我想我可能有一个想法,可以更好地分配散列。PSuedo代码:

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

因为hash()可能是o(n),那么这个算法是o(n^2),虽然有点慢,但是hash反映了等价性测试的方法,hash代码的分布可能相当不错。任何其他可交换的内核(prod、xor)都可以和本例中使用的和一起工作。

int hashcode() {
    int hash = 0;
    for (c in list) {
        hash += c * c;
    }
    return hash;
}

因为+是交换的,所以相等的单词将具有相等的哈希码。散列代码不是很有识别力(所有字母排列都得到相同的散列代码),但它应该做到这一点,除非您通常在散列集中放入许多排列。

注:我补充 c * c 而不是简单的 c 为了减少不同字母之间的冲突。

注2:具有相同哈希代码的不相等列表do 不 违反了哈希代码的约定。这种“冲突”应该避免,因为它们会降低性能,但不会威胁程序的正确性。一般来说,碰撞可以 不 避免,尽管比起我的答案,避免它们确实是可能的,但是这样做会使哈希代码的计算成本更高,这可能比消耗任何性能增益都要高。

1. 定义 equals() 和 hashCode() 对于 Letter . 只使用 char 场。
2. 为了 CircularWord ,实施 哈希代码() 通过迭代 head 到 tail 分别表示 Letter.hashCode . 最后用某个常量对结果执行异或运算。

另一种方法是将这些暗语规范化,将它们表示为:

public class CircularWord {

    private static Set<String> canonicalWords = new HashSet<String>();
    private String canonicalWord;
    private int offset;

    public CircularWord(String word) {
        // Looks for an equal cirular word in the set (according to our definition)
        // If found, set canonicalWord to it and calculate the offset.
        // If not found, put the word in the set, set canonical word to our argument and set offset to 0.
    }
    // Implementation of CircularWord methods using
    // canonicalWord and offset
}

然后您将实现 等于() 和 哈希代码() 授权给 String 实施。

我误解了你的问题——我认为你想要“picture”和“turepic”使用不同的haschodes;我认为在这种情况下,你可以从两个相等的对象必须具有相同的哈希代码这一事实中得到提示,但具有相同哈希代码的两个对象未必是相等的。

因此,您可以使用Vivien的解决方案,它将确保“picture”和“turepic”具有相同的哈希代码。然而,它也意味着“picture”和“pitch”也将具有相同的哈希代码。在这种情况下,您的 equals 方法必须更聪明,并且必须弄清楚这两个字母列表是否代表同一个单词。基本上,你的等号方法有助于解决你可以从“picture”/“turepic”和“pitchure”中得到的碰撞问题。

记住,哈希代码不是唯一的。两个不同的对象可以哈希到完全相同的值。因此,hashcode不足以确定相等性;您必须在equals()中进行实际比较。[删除推测性评论。OMG]

hashcode()在所有情况下都只能返回一个常量。这可能会影响性能,但完全有效。一旦完成了所有其他工作,就可以使用更高效的hashcode()算法。

This is a good article . 注意“lazy hashcode”部分。