0

我正在阅读 Oracle 的在线 java 教程中使用 HashMap 存储字谜的示例：

    // Read words from file and put into a simulated multimap
    Map<String, List<String>> m = new HashMap<String, List<String>>();

    try {
        Scanner s = new Scanner(new File(args[0]));
        while (s.hasNext()) {
            String word = s.next();
            String alpha = alphabetize(word);
            List<String> l = m.get(alpha);
            if (l == null)
                m.put(alpha, l=new ArrayList<String>());
            l.add(word);
        }
    } catch (IOException e) {
        System.err.println(e);
        System.exit(1);
    }

    // Print all permutation groups above size threshold
    for (List<String> l : m.values())
        if (l.size() >= minGroupSize)
            System.out.println(l.size() + ": " + l);
}

private static String alphabetize(String s) {
    char[] a = s.toCharArray();
    Arrays.sort(a);
    return new String(a);
}

}

由于 HashMap 是用 Hash Table 实现的，我认为每个排序后的按字母顺序排列的字符串在压缩后应该有一个唯一的哈希码（否则在 HashMap 中存储值的链表将存储一个不是按字母顺序排序的字符串的变位词的值）。

我不确定 Java 的 HashMap 实现如何满足这一点 - 我假设它们使用字符串的哈希码 (a1*31^n-1 + a2*31^n-2 + ... + an)。如果我们谈论的字符串只有小写字符，这可能会保证哈希码的唯一性。但是，在将key的值放入哈希表中之前，还必须压缩哈希码（否则您将有一个无法在内存中处理的huggggggge哈希表，只是想想31^10有多大是）。在这种压缩中，我认为会有碰撞。换句话说，两个不是真正字谜的不同字符串最终将存储在同一个桶中（它应该只用于存储真正字谜的列表）......

任何人都可以帮助我了解我可能会错过什么吗？或者如果在线教程缺少一些东西？

谢谢！

杰森

4

1 回答 1

1

永远不要假设哈希码是唯一的——但要意识到HashMap已经知道哈希码是非唯一的，并适当地处理它们。

换句话说，即使a.hashCode() == b.hashCode(), if !a.equals(b), 那么 aHashMap也不会混淆与 关联a的值和与 关联的值b。

于 2012-11-26T21:08:46.890 回答