JAVAの共通コレクションの内部メカニズム原理を分析する

一般的に使用されるコレクションについては誰もがよく知っていますが、内部原理に関しては、ソース コードを読むだけでは少ししか理解できないかもしれません。

ArrayList

ArrayList は、内部的にはデフォルト サイズ 10 の動的オブジェクト配列コンテナです。新しいデータが追加されるたびに、元のコンテナー サイズよりも大きい場合は、Arrays.copyOf などによってコンテナー サイズが元のサイズの 1.5 倍に増加します。データ サイズが予測できる場合は、動的データを作成できます。デフォルトでは、initialCapacity.size によって設定され、拡張によるリソース消費を削減します。

時間計算量:

get() - 添字を直接読み取ります - O(1)

add(E) - 直後に追加します - O(1) )

add(idnex, E) - データを挿入した後、次のデータを移動する必要があります - O(n)

remove(index) - 削除した後、移動する必要があります - O(n)

LinkedList

LinkedList は内部的には 二重リンクリストでは、新しいデータを追加するときに、実際に linklast を呼び出してリンクリストの最後にデータを挿入します。削除するときに、対応するデータを直接見つけて前後を置き換えることができます。リンクリストのノード

時間計算量:

get() - トラバースする必要があります - O(n)

add(E) - 最後に直接追加するために linklast を呼び出します - O(1)

add (index, E) - 最初に元のインデックス位置でデータを見つけてから、リンクされたリストの前後のデータを再指定する必要があります - O(n)

remove() - 最後のデータを削除するには、removeLast を直接呼び出しますデータ - O(1)

remove(index) - 最初に元のインデックス位置でデータを見つける必要があります - O(n)

Hash Map

HashMapは実際には配列であり、それぞれHashMap の配列は、属性 (key、value、next) を含む一方向リンク リストです。規則は、配列の添字を hash(key)%len によって取得することです。配列に対応する配列の値も検索されます (デフォルトは 0.75)。配列内の配列が 75% 埋まると、元のサイズの 2 倍に拡張されます。 、put 時に hash(key)%len の値が等しい場合、競合は発生しませんか? HashMap の処理方法は、B がインデックス付きの場合、Entry[0] があります。 0、Entry[0] = B、B.next = A、C が来ると、Entry[0] = C、C.next = B などとなります。このようにして、Entry はリンク リストを形成し、フェッチするときにリンク リストを走査して値を取得します。

ここで注意が必要なのは、hashMapを使用する場合、導入したキーオブジェクトはhashCode()関数とequal()関数を書き換える必要があることです

その理由はソースコードの判定条件(if(e.hash ==)を参照することができます。 hash && ((k = e.key) == key || key.equals(k))) の場合、hashCode() を書き換えないと、equal() を書き換えないと、対応する配列が見つかりません。キー値の内容が等しいかどうかを判断できません。

public V put(K key, V value) {  
        if (key == null)  
            return putForNullKey(value); //null总是放在数组的第一个链表中  
        int hash = hash(key.hashCode());  
        int i = indexFor(hash, table.length);  
        //遍历链表  
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
            Object k;  
            //如果key在链表中已存在，则替换为新value  
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))){  
                V oldValue = e.value;  
                e.value = value;  
                e.recordAccess(this);  
                return oldValue;  
            }  
        }  
        modCount++;  
        addEntry(hash, key, value, i);  
        return null;  
}

補足:

ハッシュマップはJava8以降で最適化されました: 一方向リンクリストの
クエリ

時間計算量はO(n)であるため、極端な場合にはパフォーマンスの問題が発生する可能性があるため、Java8はリンクリストの長さをターゲットにしています8 より大きい この場合、ストレージ クエリの効率を向上させるために、時間計算量が O(log n) の赤黒ツリーがストレージに使用されます。

LinkedHashMap

LinkedHashMap と HashMap の内部二重リンク リストの組み合わせは、複数の反復順序をサポートします。デフォルトは挿入順序ですが、アクセス順序にすることもできます。

アクセス順序 (accessOrder=true): get の呼び出しによってアクセスされる要素はチェーンの最後に配置され、反復はチェーンの先頭から開始されます

挿入順序 (accessOrder=false):挿入順序

TreeMap

TreeMapは赤黒ツリーに基づいて内部実装されており、デフォルトではcompareToを通じてキータイプによって自然にソートされます。 TreeSet の下位レベルは TreeMap です。

以上がJAVAの共通コレクションの内部メカニズム原理を分析するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。