0から7まで番号が付けられた8つのバケットしかないLinkedHashMapオブジェクトがあるとします。 今、要素を追加します。私は7つの要素を追加し、結果は次のようになります。衝突の際にLinkedHashMapから要素を取得する時間の複雑さは何ですか?
1)Element_1:バケット番号2これは、LinkedHashMapが挿入順序を維持するために維持するリンクリストの開始となります。
1)Element_2:これはElement_1
2に連結されたバケット番号3)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。
私は、(a)LinkedHashMapはリンクオーダーを維持するためのリンクリストを保持しているので、その答えはと考えました。したがって、順序が(b)の場合は、特定の要素が2つの参照を格納していることを意味します。挿入順序の次の要素と、同じバケット内の次の要素の要素です。
答えが(b)の場合、特定の要素がどのように判断するのですか。 2つの参照のうち、どちらを選択するかを指定します。
ユースケースシナリオは仮想的なものであり、バケット数よりも少ない要素数では衝突の可能性が低いという事実とは相関していない可能性があります。 上記のシナリオに留意して回答してください。
ありがとうございます。
挿入順リンクリストは、キーでアイテムを検索するコストとはまったく関係がないようですか?言い換えれば、検索のコストは 'HashMap'のものと同じでなければなりません。 – NPE
結果がa)の場合は非常に奇妙です(そしてかなり無意味です)。それはリンクされたリストに過ぎません! – dlev
7つの要素がある場合、通常は16個のバケットがあります。しかし、この例はまだ有効です。 –