19

過去 1 時間で多くの投稿を読みましたが、不変オブジェクトを Hashmap のキーとして使用するという概念はまだよくわかりません。キーを文字列として持つハッシュマップがあります。ハッシュマップの値は MyStore で、MyStore は私が所有するストアに関する情報を表します。文字列は住所を表します。私のコードでは、私が持っているロジックは、最初にそのキーのマップを調べ、存在する場合は->その値を取得し、存在しない場合はハッシュマップに入れます。私のマネージャーは、キーが将来変更される、つまり私の店舗の住所が将来変更されることを教えてくれました。その場合、キーが存在するかどうかを最初に確認するという私のロジックは機能しないと彼は言いました。彼がここで言っている意味がわかりません。以下の点を非常に明確に理解したい-

  1. ハッシュマップの可変キーと不変キーの違い。
  2. 変更可能な不変キーを使用するとどうなりますか? - 意味がわからないことはわかっていますが、マネージャーがここで話していることを明確に理解したいのです。
  3. 一部の投稿では、ハッシュマップ キャッシュのハッシュコードでキーとして使用される文字列について説明しています。これはどういう意味ですか?
  4. ハッシュコードとイコールを実装したハッシュマップで変更可能なオブジェクトをキーとして使用したとしたら、それは機能しますか? キーが変更された場合、contains メソッドはキーが存在するかどうかを調べるため、そうなると思います。存在しない場合は、エントリを配置して、将来取得できるようにします。

これが以前に議論された場合、重複した投稿を作成するつもりはありません. すべての質問への回答が記載されている投稿を読み逃した場合は、その投稿を教えてください。そうでない場合は、私が持っている上記の質問を素人の言葉で説明してください。そうすれば、将来他の読者に役立ちます:)。私の投稿の件名を自由に編集してください。将来、誰かが同様の質問をした場合は、ここに直接着陸します:)

4

5 に答える 5

29

最初: HashMap はどのように機能しますか?

基本的に配列を持ち、キーと値のペアをマップに配置すると、配列内のいずれかの位置に格納されます。hashCode()配列内の位置は、ハッシュ メソッドに渡されたキーの結果に基づいて選択されます。何故ですか？特定のキーの値を要求した場合、キーを見つけるための配列内のインデックスとそれに関連付けられた値を単純に再計算して、配列内のインデックスを再度見つけることができます。(同じインデックスにマップされるキーを処理するには、さらにいくつかのロジックが必要ですが、基本的なメカニズムを理解してもらいたいだけです) 次にequals()、計算されたインデックスのキーが実際に要求されたキーであるかどうかを確認するために使用されます。

  1. このことから、不変キーが可変キーよりも優れている理由がもう少し明確になるはずです。不変のキーは常に同じhashCode()値を保持し、ハッシュ関数は正しいバケット ( = hashMap の配列内のインデックス) を再び見つけます。

    これは、変更可能なキーが機能しないという意味ではありません。変更可能なキーは、キーの変更がハッシュ コードに影響しない場合、または hashMap が使用されている限りキーが変更されない場合に機能します。

  2. 不変の鍵はどのように変更できますか? キー自体は変更できない可能性がありますが、キーと値のマッピングはビジネス ロジックで変更できます。住所をキーとしてマップを作成する場合、店舗の住所は変更されないという事実に依存します。店舗の住所が変更された場合、新しい住所をキーとしてマップに表示されなくなります。あなたのマネージャーは有効なポイントを持っています。

  3. Map でキーを見つける速度は、hashCode の計算速度に大きく依存します。文字列の場合、この計算は文字列内のすべての文字をループします。長い文字列をキーとして使用し、マップへのアクセスが多い場合、パフォーマンスのボトルネックにつながる可能性があります。したがって、Java の String 実装はハッシュ値をキャッシュするため、一度だけ計算されます。ただし、同じインスタンスを再度使用する場合にのみ、ハッシュ コードの計算を回避できますString(新しいインスタンスにはキャッシュされた値がありません)。キーを使用することはできますが、インターンには独自のオーバーヘッドが伴うためintern()、実際にパフォーマンスのボトルネックがあることが示される場合にのみ、これを検討してください。String

  4. 1 で説明したように: 変更可能なキーは、ハッシュ コードが変更の影響を受けない場合に機能します。たとえば、顧客の名前のみに基づく Customer をキーとして使用する場合hashCode()、名前の変更のみを許可せず、他の値の変更を許可する Customer 実装は、信頼できるキーです。

于 2013-08-03T06:58:47.640 に答える
2

  1. キーとして使用される変更可能なオブジェクトを変更すると、問題が発生する可能性があります。map.containsKey(modifiedKey)キーがそこにある場合でも返される可能性falseがあります。キーを見つけるには、キーを反復処理する必要があります。したがって、不変を使用するか、キーである間は変更しないでください。

  2. 不変オブジェクトは変更されません。オブジェクトを変更しているように見えるメソッドがありますが、代わりに新しいコピーが作成されます。例：

    文字列 a = "A";

    文字列 b = a.substring(0); // 部分文字列は、まったく変更されていない "A" のコピーを作成しました。

    a = a + b; // a+b は、以前のものを変更せずに新しい文字列 "AA" を作成します。

  3. これはcaching-hashes-in-java-collectionsにも役立つかもしれません

  4. String にはすでに and の実装がequalsありhashcode、必要であると確信していない限り、代わりに使用する別のクラスを発明する必要はありません。

    ポイント1で述べたように、それを行うことはできますが、可変オブジェクトを変更しないように注意する必要があります。しかし、それはあまり良い習慣ではありません。

于 2013-08-03T06:25:17.117 に答える
1

  1. 不変キーは変更できません。したがって、挿入時に計算されるハッシュコードは変更できません。したがって、マップから要素を取得しようとすると、取得するオブジェクトのハッシュコードが既知のハッシュコードに対して計算されます。キーが外部から変更された場合 (変更可能)、新しいキーのハッシュコードは挿入したものとは異なります。

  2. 例を見てみましょう。for(2と4)

    public class RandomPair {
    int p;
    int q;

    public RandomPair(int p, int q) {
        this.p = p;
        this.q = q;
    }
    @Override
    public int hashCode() {
        return 31 * p + q;
    }

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof RandomPair)) {
            return false;
        }
        if (obj == this) {
           return true;
        }

        RandomPair other = (RandomPair) obj;
        if (p != other.p)
            return false;
        if (q != other.q)
            return false;
        return true;
    }

    public static void main(String[] args) {
        RandomPair pair = new RandomPair(10, 10);
        Map<RandomPair, Integer> map = new HashMap<RandomPair, Integer>();

        map.put(pair, 1);
        System.out.println(map.get(pair)); //returns 1

        //someone somewhere just changed the value of pair
        pair.p = 20;
        //the object was the same, someone somewhere just changed value of pair and now you can't 
        //find it in the map
        System.out.println(map.get(pair));

        //had you made p and q final, this sort of modification wouldn't be possible
       //Strings are immutable and thus prevent this modification
    }
}

  3. 文字列は不変であるため、一度計算されたハッシュコード値は再び再利用できます。ハッシュコードは遅延計算されます。つまり、hashcode の最初の呼び出しで、hashcode の値がキャッシュされます。

于 2013-08-03T06:48:36.820 に答える
0

一般に、ハッシュマップのキーは immutable にする必要があります。

これを見る

注: 変更可能なオブジェクトをマップ キーとして使用する場合は、細心の注意を払う必要があります。オブジェクトがマップ内のキーである間に、等値比較に影響を与える方法でオブジェクトの値が変更された場合、マップの動作は指定されません。

キーのハッシュは挿入中に一度計算され、ハッシュマップに保存され、キーが変更されると自動的に更新されません。そのため、キーは不変であるという前提があります。

選択肢は次のとおりです。 1. 変更可能なオブジェクトをキーとして使用しないでください。別のキーを探すか、以前のキー オブジェクトの不変部分を使用してください。 2. キーとして使用されている可変オブジェクトを変更しないでください。

于 2013-08-03T06:25:02.957 に答える
0

  1. 変更可能なキーまたはオブジェクトとは、オブジェクトを変更できることを意味します [変更とは、オブジェクトによって表される値を変更できることを意味します]。HashMapequals および hashcode で記述されたロジックがこれらの変更可能な値を使用する場合、これはストレージに影響を与えます。

  2. 不変性とは、理想的には、一度初期化されたオブジェクトはその後変更できないことを意味します。しかし、equals および hashcode メソッド内で使用されるすべての変数に関して具体的に話すHashMap場合、それらが変更できる場合、そのオブジェクトはキーとして使用されるべきではありません。

  3. about だけStringでなく、 about はそのハッシュコードをキャッシュします。ハッシュコードは、ほぼすべてのオブジェクトに対して何度も何度も生成されます [場合によっては変更される可能性があると言うのには理由があります]。ハッシュコードは Object ヘッダーにキャッシュされます。

  4. 変更可能なオブジェクトをキーとして使用したい場合は、IdentityHashMap. それらについて読むだけで、そのような場合に役立ちます。

于 2013-08-03T07:04:09.983 に答える