Java コレクション フレームワーク ArrayList ソース コードの詳細な分析 (写真)
- 黄舟オリジナル
- 2017-03-28 10:55:141579ブラウズ
全体紹介
ArrayListは、シーケンシャルコンテナであるListインターフェースを実装します。つまり、要素に格納されるデータは、要素に格納される順序と同じであり、null 要素を配置することができます。 最下層は配列によって実装されます。このクラスは同期を実装していないことを除けば、その他は null元素，底层通过数组实现。除该类未实现同步外，其余跟Vector大致相同。每个ArrayList都有一个容量（capacity），表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。前面已经提过，Java泛型只是编译器提供的语法糖，所以这里的数组是一个Object数组，以便能够容纳任何类型的对象。
size(), isEmpty(), get(), set()方法均能在常数时间内完成，add()方法的时间开销跟插入位置有关，addAll()方法的时间开销跟添加元素的个数成正比。其余方法大都是线性时间。
为追求效率，ArrayList没有实现同步（synchronized），如果需要多个线程并发访问，用户可以手动同步，也可使用Vector替代。
方法剖析
set()
既然底层是一个数组ArrayList的set()方法也就变得非常简单，直接对数组的指定位置赋值即可。
public E set(int index, E element) {
rangeCheck(index);//下标越界检查
E oldValue = elementData(index);
elementData[index] = element;//赋值到指定位置，复制的仅仅是引用
return oldValue;
}get()
get()方法同样很简单，唯一要注意的是由于底层数组是Object[]，得到元素后需要进行类型转换。
public E get(int index) {
rangeCheck(index);
return (E) elementData[index];//注意类型转换
}add()
跟C++ 的vector不同，ArrayList没有bush_back()方法，对应的方法是add(E e)，ArrayList也没有insert()方法，对应的方法是add(int index, E e)。这两个方法都是向容器中添加新元素，这可能会导致capacity不足，因此在添加元素之前，都需要进行剩余空间检查，如果需要则自动扩容。扩容操作最终是通过grow()方法完成的。
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//原来的3倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);//扩展空间并复制
}由于Java GC自动管理了内存，这里也就不需要考虑源数组释放的问题。
空间的问题解决后，插入过程就显得非常简单。
add(int index, E e)需要先对元素进行移动，然后完成插入操作，也就意味着该方法有着线性的时间复杂度。
addAll()
addAll()方法能够一次添加多个元素，根据位置不同也有两个把本，一个是在末尾添加的addAll(Collection <a href="http://www.php.cn/wiki/166.html" target="_blank">extends</a> E> c)方法，一个是从指定位置开始插入的addAll(int index, Collection extends E> c)方法。跟add()方法类似，在插入之前也需要进行空间检查，如果需要则自动扩容；如果从指定位置插入，也会存在移动元素的情况。addAll()的时间复杂度不仅跟插入元素的多少有关，也跟插入的位置相关。
remove()
remove()方法也有两个版本，一个是remove(int index)删除指定位置的元素，另一个是remove(Object o)删除第一个满足o.equals(elementData[index])的元素。删除操作是add()操作的逆过程，需要将删除点之后的元素向前移动一个位置。需要注意的是为了让GC起作用，必须显式的为最后一个位置赋nullVector
🎜🎜size(), isEmpty(), get() メソッドと set() メソッドは一定の時間で完了できます。add() メソッドの時間コストは挿入位置に関係し、addAll() メソッドの時間コストは追加された要素の数に比例します。 。他のメソッドのほとんどは線形時間です。 🎜🎜効率を追求するため、ArrayList は同期されません。複数のスレッドによる同時アクセスが必要な場合、ユーザーは手動で同期するか、代わりに Vector を使用できます。 🎜🎜メソッド分析🎜set()
🎜最下層は配列🎜ArrayList🎜であるため、set() メソッドは非常にシンプルになり、値を直接代入します。配列の指定位置 以上です。 🎜public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; //清除该位置的引用，让GC起作用
return oldValue;
}get()
🎜get() メソッドも非常に簡単です。唯一注意すべき点は、基になる配列が Object[] であるため、型変換🎜。 🎜rrreeeadd()
🎜 は C++ の 🎜vector🎜 とは異なり、🎜ArrayList🎜 にはbush_back() メソッドがなく、対応するメソッドは add( E e) では、🎜ArrayList🎜 にも insert() メソッドがありません。対応するメソッドは add(intindex, E e) です。どちらの方法でもコンテナに新しい要素を追加するため、🎜容量🎜が不足する可能性があるため、要素を追加する前に残りのスペースをチェックし、必要に応じて自動的に拡張する必要があります。展開操作は、grow() メソッドによって最終的に完了します。 🎜rrreee🎜 Java GC は自動的にメモリを管理するため、ここでソース配列の解放の問題を考慮する必要はありません。 🎜🎜🎜🎜スペースの問題が解決された後、挿入プロセスは非常に簡単なようです。 🎜🎜🎜🎜add(intindex, E e)最初に要素を移動してから挿入操作を完了する必要があります。これは、このメソッドの時間計算量が線形であることを意味します。 🎜addAll()
🎜addAll() メソッドは、位置に応じて 2 つのハンドルが追加されます。 Collectionextends🎜 E> メソッドから 1 つが挿入されます。指定された位置の addAll(int index, Collection extends E> c) メソッド。 add() メソッドと同様に、挿入前にスペース チェックも必要です。指定した位置から挿入すると、必要に応じて容量が自動的に拡張され、要素も移動される可能性があります。 addAll() の時間計算量は、挿入される要素の数だけでなく、挿入位置にも関係します。 🎜remove()
🎜remove() メソッドにも 2 つのバージョンがあります。1 つは、指定された位置にある要素を削除する remove(int index) です。もう 1 つは remove(Object o) で、o.equals(elementData[index]) を満たす最初の要素を削除します。削除操作は add() 操作の逆のプロセスであり、削除ポイントの後の要素を 1 つ前に移動する必要があります。 GC が機能するには、最後の位置に明示的に null 値を割り当てる必要があることに注意してください。 🎜りー以上がJava コレクション フレームワーク ArrayList ソース コードの詳細な分析 (写真)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。