3

次のようなキーを持つハッシュマップがあります: '2+4+5' , '653+65+1324+75'.(+ 記号で区切られた整数値)

「2 + 4 + 5」、「5 + 4 + 2」、「4 + 5 + 2」などのキーが得られるように、適切なハッシュコードと equals メソッドとは何でしょうか... (2,4,5 のすべての順列)同じハッシュコード値を返す必要があり、equals は true を返す必要があります。

キーの整数値を取得して並べ替え、昇順で文字列に入れ、その文字列の hashcode と equals メソッドを呼び出すことを計画しています。「5+2+4」がある場合、それを「245」に変更し、文字列の hashcode と equals メソッドを呼び出すとします。しかし、毎回並べ替えを行う必要があるため、これはコストのかかる操作になります。そして、put、get などのハッシュマップ内のすべてのメソッドは、再び高価になります

ログまたは線形時間でこれを行う他の方法はありますか...

4

3 に答える 3

2

優れたハッシュコード アルゴリズムは、入力のわずかな違いに対して非常に異なるハッシュを返す必要があります。あなたの場合、値の順列も「等しい」と見なします。

構成要素の整数を解析してから並べ替えるのが良い方法のようです (比較のために一貫した順序を確保するための簡単な方法の 1 つ)。

並べ替えられた成分番号が同じ場合、2 つの値が等しいと見なします。

次のような実証済みのハッシュ アプローチを使用します。

hash = value1 + 31 * value2 + 31 * 31 * value3 + 31 * 31 * 31 * value4 + etc.
于 2012-04-23T22:49:49.657 に答える
1 
class Combination {
    final int[] parts;

    Combination(String str) {
        String[] strings = str.split("\\+");
        parts = new int[strings.length];
        for (int i = 0; i < parts.length; i++) {
            parts[i] = Integer.parseInt(strings[i]);
        }
        Arrays.sort(parts);
    }

    @Override public int hashCode() {
        return Arrays.hashCode(parts);
    }

    @Override public boolean equals(Object o) {
        return o instanceof Combination && Arrays.equals(parts, ((Combination) o).parts);
    }
}

テストコード:

public static void main(String[] args) {
    Set<Combination> set = new HashSet<>();
    set.add(new Combination("1+2+3"));
    set.add(new Combination("1+2+4"));
    System.out.println(set.contains(new Combination("3+2+1"))); // prints "true"
    System.out.println(set.contains(new Combination("4+2+1"))); // prints "true"
    System.out.println(set.contains(new Combination("4+3+1"))); // prints "false"
}
于 2012-04-23T23:07:01.193 に答える
1

シンプルで効果的：

public int hashcode(){
    int hash=5;
    for(int i:array)
       hash=hash*17+i;

    return hash;
}
于 2012-04-23T22:55:50.333 に答える