38

だから私はHashMapについて読んだ。ある時点で、次のことが指摘されました。

「不変性により、さまざまなキーのハッシュコードをキャッシュできるため、全体的な取得プロセスが非常に高速になり、IntegerJavaコレクションAPIによって提供されるStringおよびさまざまなラッパークラス（たとえば）が非常に優れたHashMapキーであることがわかります。」

よくわかりません…なんで？

4

7 に答える 7

36

String#hashCode：

private int hash;

...

public int hashCode() {
    int h = hash;
    if (h == 0 && count > 0) {
        int off = offset;
        char val[] = value;
        int len = count;

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}

内容はString決して変更されないため、クラスの作成者は、一度計算された後にハッシュをキャッシュすることを選択しました。このようにして、同じ値を再計算するために時間を無駄にすることはありません。

于 2012-04-26T23:43:50.093 に答える
10

リンクされたブログエントリの引用：

適切なequals（）およびhashcode（）実装を備えた最終オブジェクトは、完全なJava HashMapキーとして機能し、衝突を減らすことでJavahashMapのパフォーマンスを向上させます。

私は両方がどのようになっているかを理解できずfinal、equals()ハッシュ衝突と関係があります。この文は、記事の信頼性についての私の疑いを引き起こします。それは独断的なJavaの「知恵」のコレクションのようです。

不変性により、さまざまなキーのハッシュコードをキャッシュできるため、全体的な取得プロセスが非常に高速になり、StringやJavaコレクションAPIによって提供される整数などのさまざまなラッパークラスが非常に優れたHashMapキーであることがわかります。

この文には2つの解釈が考えられますが、どちらも間違っています。

  • HashMap不変オブジェクトのハッシュコードをキャッシュします。これは正しくありません。マップには、オブジェクトが「不変」であるかどうかを確認する可能性がありません。
  • オブジェクトが独自のハッシュコードをキャッシュするには、不変性が必要です。理想的には、オブジェクトのハッシュ値は常にオブジェクトの非変化状態に依存する必要があります。そうしないと、オブジェクトをキーとして適切に使用できません。したがって、この場合も、作成者は指摘しません。オブジェクトがその状態を変更していないと仮定すると、オブジェクトが可変であっても、毎回ハッシュ値を再計算する必要はありません。

例

したがって、私たちが本当に夢中になっていて、実際にListaのキーとしてaHashMap を使用し、ハッシュ値をリストのIDではなくコンテンツに依存させることにした場合、変更のたびにキャッシュされたハッシュ値を無効にすることを決定できます。ハッシュ計算の数をリストへの変更の数に制限します。

于 2012-04-26T23:46:13.460 に答える
6

とても簡単です。不変オブジェクトは時間の経過とともに変化しないため、ハッシュコードの計算を1回実行するだけで済みます。もう一度計算すると、同じ値が得られます。したがって、コンストラクターで（または怠惰に）ハッシュコードを計算し、それをフィールドに格納するのが一般的です。次に、hashcode関数はフィールドの値だけを返します。これは実際には非常に高速です。

于 2012-04-26T23:45:28.843 に答える
1

基本的に、Javaではクラスを拡張できないようにすることで不変性が実現され、オブジェクト内のすべての操作がオブジェクトの状態を変更しないのが理想的です。replace（）のようなStringの操作を見ると、操作している現在のオブジェクトの状態は変更されず、置き換えられた文字列を持つ新しいStringオブジェクトが提供されます。したがって、理想的には、キーなどのオブジェクトを維持する場合、状態は変更されないため、ハッシュコードも変更されません。したがって、ハッシュコードをキャッシュすると、取得時にパフォーマンスが向上します。

于 2012-04-26T23:46:40.827 に答える
1

ハッシュマップは、番号が付けられたボックスの大きな配列と考えてください。番号はハッシュコードで、ボックスは番号順に並べられています。

これで、オブジェクトを変更できない場合、ハッシュ関数は常に同じ値を再現します。したがって、オブジェクトは常にボックス内にとどまります。

ここで、変更可能なオブジェクトを想定します。ハッシュに追加した後に変更されるため、ジョーンズ夫人がたまたまミスター・ドーと結婚し、現在はドーと呼ばれているように、間違ったボックスに配置されていますが、多くのレジスターではまだジョーンズと呼ばれています。

于 2012-04-26T23:47:48.350 に答える
0

ハッシュ テーブルは、オブジェクトがテーブルに格納されている間、オブジェクトのハッシュ コードが変更できない場合にのみ機能します。これは、テーブル内にある間に変更される可能性のあるオブジェクトの側面をハッシュ コードが考慮できないことを意味します。オブジェクトの最も興味深い側面が変更可能である場合、それは次のいずれかを意味します。

  • ハッシュコードは、オブジェクトの興味深い側面のほとんどを無視する必要があるため、多くのハッシュ衝突が発生するか...

  • ハッシュ テーブルを所有するコードは、その中のオブジェクトがハッシュ テーブルに格納されている間に変更される可能性のあるものに公開されないようにする必要があります。

Java ハッシュ テーブルでクライアントが EqualityComparer を提供できる場合 (.NET 辞書が行うように)、ハッシュ テーブル内のオブジェクトの特定の側面が予期せず変更されないことを認識しているコードは、それらの側面を考慮したハッシュ コードを使用できますが、 Java でこれを実現する唯一の方法は、ハッシュコードに格納されている各項目をラッパーでラップすることです。このようなラッピングは世界で最も悪いことではないかもしれませんが、ラッパーはキャッシュEqualityComparerできない方法でハッシュ値をキャッシュすることができ、さらに等値関連の情報をキャッシュすることもできるからです [例えば、格納されているものがネストされたコレクションの場合、要素の詳細な検査を行う前に、複数のハッシュ コードを計算し、すべてのハッシュ コードが一致することを確認することをお勧めします]。

于 2013-12-26T16:48:29.630 に答える