0

HashMapを使用してアナグラムを格納するOracleのオンラインJavaチュートリアルの例を読んでいました。

    // 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はHashTableで実装されているため、ソートされたアルファベット順の各文字列には、圧縮後に一意のハッシュコードが必要だと思います（そうでない場合、HashMapに値を格納するリンクリストには、ソートされたアルファベット順の文字列のアナグラムではない値が格納されます）。

JavaのHashMapの実装がこれをどのように満たすことができるか正確にはわかりません-文字列のハッシュコード（a1 * 31 ^ n-1 + a2 * 31 ^ n-2 + ... + an）を使用していると思います。これにより、小文字のみの文字列について話している場合、ハッシュコードの一意性が保証される可能性があります。ただし、キーの値をハッシュテーブルのバケットに配置する前に、ハッシュコードを圧縮する必要もあります（そうしないと、メモリで処理できないhuggggggeハッシュテーブルが作成され、31^10の大きさを考えるだけです。は）。この圧縮の中で、衝突があると思います。言い換えると、真のアナグラムではない2つの異なる文字列は、同じバケットに格納されることになります（これは、真のアナグラムのリストを格納するためにのみ使用する必要があります）。

誰かが私が欠けているかもしれないものを理解するのを手伝ってもらえますか？または、オンラインチュートリアルに何かが欠けている場合はどうなりますか？

ありがとう！

ジェイソン

4

1 に答える 1

1

決して、ハッシュコードが一意であると想定することはありませんが、ハッシュコードが一意ではないことをHashMapすでに知っており、それらを適切に処理することを理解してください。

言い換えると、たとえa.hashCode() == b.hashCode()、の場合でも!a.equals(b)、aはに関連付けられた値とに関連付けHashMapられた値を混同しません。ab

于 2012-11-26T21:08:46.890 に答える