2

0 から 7 までの番号が付けられた 8 つのバケットのみを持つ LinkedHashMap オブジェクトがあるとします。次に、要素を追加します。7 つの要素を追加した結果は次のようになります。

1) Element_1: バケット番号 2。これは、LinkedHashMap が挿入順序を維持するために維持するリンクされたリストの開始になります。
1) Element_2: バケット番号 3. これは Element_1 にリンクされています
2) Element_3: バケット番号 1. これは Element_2 にリンクされています
3) Element_4: バケット番号 4. これは Elemetn_3 にリンクされています
4) Element_5: バケット番号 5. これはリンクされていますElement_4 へ
5) Element_6: バケット番号 3. これは Element_5 にリンクされています (衝突が発生しました)
6) Element_7: バケット番号 3. これは Element_6 にリンクされています (再び衝突)

ここで、Element_7 を取得するとします。この要素のハッシュにより、バケット番号 3が得られます。バケット番号 3の要素はElement_2、Element_6、Element_7です。
次の 2 つのトラバーサルの順序は次のとおりです
。a) Element_2 -> Element_3 -> Element_4 -> Element_5 -> Element_6 -> Element_7。
または
b) Element_2->Element_6->Element_7。

LinkedHashMap はリンクされたリストを保持して挿入順序を維持しているため、答えは (a) になると思いました。したがって、順序が (b) の場合、特定の要素が 2 つの参照を格納していることを意味します。1 つは挿入順の次の要素用で、もう 1 つは同じバケット内の次の要素用です。

答えが (b) の場合、特定の要素はどのようにアクセスするか、つまり 2 つの参照からどちらを選択するかを決定します。

ユースケースのシナリオは仮説であり、要素の数がバケットの数よりも少ない場合、衝突の可能性が低くなるという事実とは相関しない可能性があります。上記のシナリオを念頭に置いて回答してください。
前もって感謝します。

4

2 に答える 2

2

LinkedHashMap は HashMap を拡張するため、リンクは とは無関係ですget。そのため、リンクを追加しても LinkedHashMap の効率が低下するgetことはありません。get はそのリンクを必要としないためです。

于 2012-04-11T17:08:48.937 に答える
1

LinkedHashMap は HashMap を拡張し、そのgetメソッドは HashMap のgetEntryメソッドを呼び出します。HashMap の実装では、各バケットが個別の配列に格納されるため、データセット全体をループする必要はなく、そのバケット内のデータに対してのみループする必要があります。Oracle JDK 7 から取得:

final Entry<K,V> getEntry(Object key) {
    int hash = (key == null) ? 0 : hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

編集

e.nextで定義されHashMap.Entry、同じバケット内にあるのとは対照的に、どのバケットe.afterでe.before定義されLinkedHasMap.Entry、異なるバケットにある可能性があります。

于 2012-04-11T17:10:19.050 に答える