Java HashSetのremove（）は、ArrayListのremove（）がO（n）を取るとき、なぜO（1）時間かかるのですか？

Question

私は、JavaのHashSetのremove（Object o）はO（1）一定時間を取るが、ArrayListのremove（Object o）操作はO（N）を取るが、NはArrayListのサイズである。

誰でも詳細に説明してください、それはなぜですか？

Answer 1

HashSetさんremove()削除する要素を検索するO(1)予想時間がかかる - hashCode()要素が含まれているビンに移動します、そして各ビンは、エントリの数が少ないことが予想されるので、内の要素を見つけますビンとそれを取り除くには一定の時間がかかるはずです。

一方、ArrayListでは、削除する要素を見つけるまですべての要素を反復する必要があります。その要素にはO(n)が必要です。要素の位置を特定した後でも、削除自体には、削除された要素よりも高いインデックスを持つすべての要素が移動することが含まれます。その場合は、O(n)も必要です。

Answer 2

のArrayList： -

ArrayListのJavaでは、配列によってバックアップされる一覧です。

remove（i）arraylistは、リスト内の指定された位置にある要素を削除し、後続の要素をすべて左にシフトします。

したがって、最悪の場合のシナリオでは、最初の要素を削除する場合、残りのn-1要素を左にシフトする必要があります。したがって、複雑さはo（n）である。

HashSetの： -

Javaは内部的にセットの要素を格納するハッシュマップを使用しています。ハッシュマップの要素はハッシュマップのキーであり、値はダミーオブジェクトです。

ハッシュマップでの削除操作は、のように動作します： -

1. は、キーのハッシュ値を検索します。
2. エントリテーブルのキーのインデックスを検索します。
3. バケットを反復してキーを見つけます。
4. バケットリンクリストからキーを削除します。

バケットはすべての鍵を含むことができ、複雑さはo（n）と思われます。しかし実際の生活では、ハーフ・デシェント・ハッシュ関数と結合された信頼できるハッシュ・マップの実装は、期待されるケースでは非常に小さな要因（実際には2）を伴う検索パフォーマンスO（1）を非常に狭いマージン。