hashCode複雑さの必要性

Question

私は、15パズルゲームのN行Nのボードを表す不変のBoardクラスに取り組んでいます（N行Nの場合、N^2 - 1パズルゲームになります） 。 1エントリ - 私はequals()（下図参照）オブジェクト契約、私はを実装したいしかしhashCodeメソッド、を、保存するために、その結果hashCode()方法は、二次の時間がかかります（それがすべてNを確認してください^ 2をオーバーライドしています）。

私の質問は、パフォーマンスが低下する可能性があるので、hashCodeが一定の時間を取らないと悪い習慣と考えられますか？HashMap/（これは私が使用する予定はありません）私は、たとえそれが衝突を増加させるにもかかわらず、同じプライムを毎回返すなど、より簡単なものを選ぶべきですか？

サンプル（のtoString（）メソッドから採取）3×3ボード

1 2 3 
4 5 6 
7 0 8 

Boardsつが等しいIFFとみなされている、すべてのエントリが一致します。

ボードクラスからのコードのスニペット：

public class Board { 

    private final int[][] tilesCopy; // tiles 
    private final int N;    // size of the board 

... code... 


@Override 
    public boolean equals(Object y) { 
     if (!(y instanceof Board)) return false; 
     Board that = (Board) y; 
     if (this.size() != that.size()) return false; 

     for (int i = 0; i < this.size(); i++) { 
      for (int j = 0; j < this.size(); j++) { 
       if (this.tileAt(i, j) != that.tileAt(i, j)) return false; 
      } 
     } 
     return true; 
    } 

@Override 
public int hashCode() { 
    ...code... 
    } 

Answer 1

良い練習はあなたが言及しているの理由から、できるだけ速くなることです。しかし、hashCodeが弁別的であることがより重要である。。

N*N要素がある場合、ハッシュはそれらをすべて考慮する必要があります。 何かを無視しようとすると、より多くの衝突につながります.HashMapsなどでは、equalsコールがさらに多く発生します。これは、さらに高額になります（一致しないとすぐにreturn falseを入力すると、equalshashCode呼び出しよりも漸近的に大きくなります）。さらに通話用

hashCodeは、インスタンス上で複数回呼び出されることになるだろう、と計算するには高価であるされている場合、あなたは一度だけそれをeveluateすべき

、およびキャッシュそれが（もちろん、あなたのオブジェクトは不変である必要があり、またはオブジェクトの突然変異でキャッシュされたhashCodeを無効にする必要があります）。

---

更新：インスピレーションとして、Javaコレクション（Lists、Sets等）ハッシュコードの計算も、全ての要素をループ挙げられます。 APIの観点からは、コレクションのサイズだけをハッシュコードとして使用することはOKですが

アップデート2：あなたはどのハッシュコレクションを使用しない場合、それはとにかく使用されませんので、あなたが実際には、return 0ハッシュコードを実装することができます。しかし、他の人とこの実装を共有している場合は、そのようなコレクションに配置したい場合があるので、実装する必要があります。

Answer 2

「悪い習慣」とはみなされません。良いか悪い練習は本当にそれに来ていません。

あなたが本当に考慮する必要があるのは、それが最善の解決策であるかどうかです。 O(N^2)ではないハッシュコードを計算する方法はありますか？ O(N^2)が有意であるためにこれらのハッシュコードを頻繁に計算するつもりです全体？あなたは（再）同じ状態のハッシュコードを計算することを避けることができますか？

ボックスの外側を少し考えて、あなたのボード状態が実際には相互に関連していると考えて、1つの状態が前の状態からの増分変化（移動）を表しているとします。 （ゲームルールが正常に動作する方法です）ハッシングアルゴリズムを適切に選択した場合、ゲームのインクリメンタルな性質を利用して、前の状態のハッシュコードから新しい状態のハッシュコードを計算することができます。

たとえば、XOR関数には可逆性があります。つまり、A XOR BがCの場合、C XOR BはAです。したがって、ボード状態のハッシュコードが要素のハッシュのXORで構成されている場合は、hashcode(state S)からhashcode(state S + 1)に移動できます。変更された状態要素。

もちろん、ボード状態を表すオブジェクトにハッシュコードをキャッシュする必要があります。しかし、そうするなら、O(N^2)ではなく、O(1)でハッシュコードを計算できるはずです。