7

最適なルックアップ構造はHashTable. 平均して一定のアクセスを提供します（最悪の場合は線形）。
これはハッシュ関数に依存します。Ok。
私の質問は次のとおりです。HashTableたとえばHashMap、マップで渡されるキーに関するベストプラクティスはありますか?の適切な実装を想定すると、キーは不変オブジェクトでなければならないことが推奨されますが、他の推奨事項があるかどうか疑問に思っていました。
キーのサイズの例は? たとえば、適切なハッシュマップ (上記の方法で) をキーとして使用した場合、 (キーを見つけようとしている)Stringの文字列比較に「ボトルネック」はありませんか? equalsでは、キーは小さく保つ必要がありますか? または、キーとして使用してはいけないオブジェクトがありますか? 例URL? そのような場合、キーとして使用するものをどのように選択できますか?

4

4 に答える 4

2

HashMapの最もパフォーマンスの高いキーは、おそらく整数です。ここで、hashCode()およびequals()は次のように実装されます。

public int hashCode() {
    return value;
}

public boolean equals(Object obj) {
    if (obj instanceof Integer) {
        return value == ((Integer)obj).intValue();
    }
    return false;
}

つまり、HashMapの目的は、あるオブジェクト（値）を他のオブジェクト（キー）にマップすることです。（値）オブジェクトをアドレス指定するためにハッシュ関数が使用されるという事実は、高速で一定時間のアクセスを提供することです。

キーは不変オブジェクトである必要がありますが、他に推奨事項があるかどうか疑問に思いました。

オブジェクトを必要なものにマップすることをお勧めします。何が速いかを考えないでください。ただし、取得するオブジェクトに対処するためのビジネスロジックに最適なものを考えてください。

重要な要件は、キーオブジェクトが不変でなければならないことです。これは、キーオブジェクトをマップに格納した後で変更すると、後で関連付けられた値を取得できない場合があるためです。

のキーワードはHashMapですMap。オブジェクトはマップする必要があります。キーを最適化するマッピングタスクを犠牲にすると、おそらくパフォーマンスの向上を達成することなく、マップの目的を無効にすることになります。

私はあなたの質問の最初の2つのコメントに100％同意します：

主な制約は、ルックアップのベースにしたいものでなければならないということです;）
– Oli Charlesworth

一般的なルールは、検索する必要があるものは何でもキーとして使用することです。
– Louis Wasserman

最適化の2つのルールを覚えておいてください。

  1. しないでください。
  2. （専門家のみ）まだです。

3番目のルールは次のとおりです。最適化する前のプロファイル。

于 2013-01-16T22:10:15.613 に答える
1

データ構造内のものを検索するために使用したい任意のキーを使用する必要があります。これは通常、ドメイン固有の制約です。そうは言っても、テーブル内のキーを見つけるために と の両方が使用されることにhashCode()注意してください。equals()

hashCode()はキーの位置を見つけるために使用され、equals()は検索しているキーが実際に を使用して見つけたキーであるかどうかを判断するために使用されますhashCode()。

たとえば、別のチェーンを使用して、テーブル内に同じハッシュ コードを持つ2 つのキーaとがあるとします。次に、とfromを含むリストのインデックスが見つかったら、テーブル内のとの両方の可能性があるかどうかをテストする必要があります。baa.equals(key)ababhashCode()

于 2013-01-16T20:32:26.027 に答える
0

実装を掘り下げました。この方法の有効性が重要な要素になるという仮定がありましたhashCode()。

HashMap()と実装を調べたHashtable()ところ、実装が非常に似ていることがわかりました (1 つの例外を除いて)。どちらもすべてのエントリに対して内部ハッシュ コードを使用および保存しているhashCode()ため、パフォーマンスにそれほど影響を与えていないことは良い点です。

両方とも、値が格納される多数のバケットを持っています。バケットの数 (n など) とバケット内のキーの平均数 (k など) のバランスが重要です。バケットは O(1) 時間で見つかり、バケットのコンテンツは O(k) サイズで反復されますが、バケットが多いほど、より多くのメモリが割り当てられます。また、多くのバケットが空の場合はhashCode()、キー クラスのメソッドがハッシュコードの幅を十分に広げていないことを意味します。

アルゴリズムは次のように機能します。

Take the `hashCode()` of the Key (and make a slight bijective transformation on it)
Find the appropriate bucket
Loop through the content of the bucket (which is some kind of LinkedList)
Make the comparison of the keys as follows:
1. Compare the hashcodes 
    (it is calculated in the first step, and stored for the entry)
2. Examine if key `==` the stored key (still no call) 
    (this step is missing from Hashtable)
3. Compare the keys by `key.equals(storedKey)`

要約する：

  • hashCode() は呼び出しごとに 1 回呼び出されます (これは必須であり、これなしでは実行できません)
  • equals() は、hashCode が十分に分散されておらず、2 つのキーがたまたま同じハッシュコードを持つ場合に呼び出されます。

get()andの場合も同じアルゴリズムですput()(put() の場合、既存のキーの値を設定できるため)。したがって、最も重要なことは、メソッドがどのようhashCode()に実装されたかです。最も頻繁に呼び出されるメソッドです。

2 つの戦略は、迅速にすることと効果的にすること(十分に普及させること) です。JDK の開発者は、両方を実現しようと努力しましたが、常に両方を実現できるとは限りません。

  • Numeric種類が良い
  • Object(およびオーバーライドされていないクラス) は適切hashCode()です (ネイティブです)。equals()
  • String良くありません、文字を繰り返しますが、その後キャッシュします（以下の私のコメントを参照してください）
  • 同期化された hashCode() を持つクラスは適切ではありません
  • 繰り返しのあるクラスは良くありません
  • ハッシュコード キャッシュを持つクラスは少し優れています (使用状況によって異なります)。

String に関するコメント: 高速にするために、JDK の最初のバージョンでは、最初の 32 文字のみに対して String ハッシュ コードの計算が行われました。しかし、生成されたハッシュコードは十分に拡散されていなかったため、すべての文字をハッシュコードに含めることにしました。

于 2013-01-16T23:26:47.153 に答える
0

キーは不変オブジェクトでなければならないことが推奨されていますが、他の推奨事項があるかどうか疑問に思っていました。

値のキーは である必要がありますfinal。

ほとんどの場合、オブジェクトのフィールドがキーとして使用されます。そのフィールドが変更された場合、マップはそれを見つけることができません:

void foo(Employee e) {
  map.put(e.getId(), e);
  String newId = e.getId() + "new";
  e.setId(newId);
  Employee e2 = e.get(newId);
  // e != e2 !
}

したがってEmployee、メソッドをまったく持つべきではありませんが、書いているときに何がキーになるかわからないsetId()ため、それは困難です。Employee

于 2013-01-17T00:46:38.717 に答える