java - 关于Oracle的java在线教程中使用HashMap存储anagram的例子

Question

我正在阅读 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是用哈希表实现的，所以我认为每个按字母顺序排序的字符串在压缩后应该有一个唯一的哈希码(否则HashMap中存储值的链表将存储一个不是按字母顺序排序的字谜词的值)字符串)。

我不太确定 Java 的 HashMap 实现如何满足这个要求 - 我假设它们使用字符串的哈希码 (a1*31^n-1 + a2*31^n-2 + ... + an )。如果我们讨论仅包含小写字符的字符串，这可能会保证哈希码的唯一性。然而，在将键的值放入哈希表中的桶之前，还必须压缩哈希码(否则你将拥有一个无法在内存中处理的巨大哈希表，想想 31^10 有多大是)。在这个压缩当中，我会认为会有碰撞。换句话说，两个不是真正的 anagram 的不同字符串最终将存储在同一个存储桶中(该存储桶应该仅用于存储真正的 anagram 列表)...

有人可以帮助我了解我可能缺少什么吗？或者在线教程是否缺少某些内容？

谢谢!

杰森

Answer 1

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

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