一般的に使用されるコレクションについては誰もがよく知っていますが、内部原理に関しては、ソース コードを読むだけでは少ししか理解できないかもしれません。
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 は内部的には 二重リンクリストでは、新しいデータを追加するときに、実際に linklast を呼び出してリンクリストの最後にデータを挿入します。削除するときに、対応するデータを直接見つけて前後を置き換えることができます。リンクリストのノード
時間計算量:
get() - トラバースする必要があります - O(n)
add(E) - 最後に直接追加するために linklast を呼び出します - O(1)
add (index, E) - 最初に元のインデックス位置でデータを見つけてから、リンクされたリストの前後のデータを再指定する必要があります - O(n)
remove() - 最後のデータを削除するには、removeLast を直接呼び出しますデータ - O(1)
remove(index) - 最初に元のインデックス位置でデータを見つける必要があります - O(n)
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以降で最適化されました: 一方向リンクリストの
クエリ
TreeMap
以上がJAVAの共通コレクションの内部メカニズム原理を分析するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。