3

3 つの入力データ フィールドに基づいてデータを検索する必要があります。ルックアップは高速でなければなりません。ルックアップの組み合わせは 20 通りしかありません。これは、3 つのデータ フィールドを連結してキーを作成する静的な HashMap インスタンスを使用して実装しました。これを行うためのより良い方法はありますか、それともこれが進むべき道ですか? コードは以下です。

更新: このコードが遅いと言っているわけではありません。これを行うためのより良い方法があるかどうかに興味があります。もっとエレガントな解決策があるかもしれないと思っていましたが、説得力のある代替案がない場合は、これをそのままにしておきます!

クラス レベルの静的 HashMap インスタンスを作成します。

private static HashMap map = new HashMap();

データをメモリにロードする方法:

private void load(Iterator iterator) {        
    while (iterator.next()) {  
      Object o = it.next();
      key = o.getField1() + "-" + o.getField2() + "-" o.getField3();
      map.put(key, o.getData());
    }
}

そして、3 つのフィールドに基づいてデータを検索する方法は次のとおりです。

private Stirng getData(String f1, String f2, String f3) {
   String key = f1 + "-" + f2 + "-" f3;
   return map.get(key);
}
4

7 に答える 7

7

もちろん、自問すべき問題は、「十分に高速かどうか」です。アプリケーションを高速化する必要があり、これがボトルネックでない限り、実際には問題にならないからです。あなたが持っているものはすでにかなり効率的です。

そうは言っても、(アセンブリ言語で書き直さずに) このルーチンから可能な限りの速度を引き出したい場合は、 の代わりに配列を使用することを検討してくださいHashMap。各オブジェクトを 0 から 19 までの一意の数値 (または実際に持っている要素の数) にハッシュする、ある種のハッシュ関数を開発する必要があります。そのハッシュ関数の実装を最適化することもできるかもしれませんが、作業しているオブジェクトの詳細を知らずにそれを行う方法を正確に説明することはできません.

于 2009-10-04T13:22:27.537 に答える
3

キー文字列の作成を避けるために、3 つの String フィールドを持つ特別なキー オブジェクトを作成できます。

class MapKey {
  public final String k1;
  public final String k2;
  public final String k3;

  public MapKey(String k1, String k2, String k3) {
    this.k1 = k1; this.k2 = k2; this.k3 = k3;
  }

  public MapKey(Object o) {
    this.k1 = o.getField1(); this.k2 = o.getField2(); this.k3 = o.getField3();
  }

  public int hashCode() {
    return k1.hashCode();  // if k1 is likely to be the same, also add hashes from k2 and k3
  }
}
于 2009-10-04T13:39:27.833 に答える
1

キーを作成する場合、文字列を連結することはお勧めできません。私の主な目的は、それが不明確であることです。しかし実際には、かなりの割合の実装にバグがあり、特に区切り文字が実際に文字列で発生する可能性があります。パフォーマンスに関しては、文字列ハックのキーを意味のあるキー オブジェクトに変更するだけで、プログラムの速度が 10% 向上するのを見てきました。(本当にコードを怠る必要がある場合は、 を使用Arrays.asListしてキーを作成できます - List.equalsAPI doc を参照してください。)

于 2009-10-04T15:45:14.023 に答える
1

あなたのアプローチはかなり速いと思います。独自のハッシュ アルゴリズムを実装することによる利益は、特に必要な労力と比較すると非常に小さいものです。

鍵の形式について 1 つのコメント。フィールド toString() の値でセパレーターが発生しないようにすることをお勧めします。そうしないと、キーの衝突が発生する可能性があります。

field1="a-", field2="b-", field3="c" -> key="a--b--c"
field1="a", field2="-b", field3="-c" -> key="a--b--c"
于 2009-10-04T15:32:51.803 に答える
1

あなたの場合、私はあなたが概説した実装を使い続けます。定数データにマッピングされた定数キーの大きなリストについては、 Minimal Perfect Hashingを使用できます。これをコーディングするのは簡単ではなく、既存のライブラリについてもよくわからないため、これを使用する前に実装コストを考慮する必要があります。

于 2009-10-04T13:50:28.320 に答える
0

組み合わせは 20 個しかないので、各組み合わせの特性を知ってから、「この組み合わせのインデックス 1..20 を教えてください」を手作りすることは可能かもしれません。

組み合わせの正確なリストをリストする立場にありますか?

于 2009-10-04T17:44:55.403 に答える
0

これを行うもう 1 つの方法はObject、キーを処理する を作成することです。これをオーバーライドしてequals()(およびhashCode())、着信キーに対してテストを実行し、 testingfield1を実行field2しfield3ます。

編集（コメントへの応答）：

から返された値はhashCode()Map によってキーをバケットに入れるために使用されるため (そこからテストされますequals)、値は理論的にはすべてのキーで同じになる可能性があります。ただし、HashMaps のパフォーマンスのメリットを享受できないため、これを行うことはお勧めしません。基本的に、バケット内のすべてのアイテムを反復処理してテストしますequals()。

hashCode()1 つのアプローチとして、呼び出しをキー コンテナー内の値の 1 つに委任することができます。field3たとえば、常に hashCode を から返すことができます。この場合、潜在的には の個別の値と同じ数のバケットにキーを配布しますfield3。バケットが見つかったらHashMap、バケット内のアイテムを繰り返し処理して equals()、一致が見つかるまで結果をテストする必要があります。

hashCode()すべてのフィールドで返される値の合計を作成できます。前述したように、この値は一意である必要はありません。さらに、衝突の可能性、したがってより大きなバケットがはるかに小さくなります。それを念頭に置いて、 でのルックアップはHashMapより速くなるはずです。

EDIT2：

このキーの適切なハッシュ コードに関する質問は、別の質問で回答されています。

于 2009-10-04T13:39:40.737 に答える