詳細解説︕ ArrayListの仕組みと実装 @YujiSoftware
目次 • ArrayList の概要 ◦ インタフェースについて ◦ Collections Framework について
• ArrayList のアルゴリズム • ArrayList の実装(ソースコードを読む) 本⽇の資料: https://yuji.software/arraylist/ ArrayList 以外のコレクションの話、ジェネリクスの話 スコープ外
1. ArrayList の概要
注目ポイント • ArrayList って何︖ • ArrayList が実装するインタフェースごとの特徴 ◦ List インタフェースとは︖
◦ SequencedCollection インタフェースとは︖ ◦ Collection インタフェースとは︖ ◦ マーカーインタフェースとは︖
ArrayList とは︖
Array を使って実装した List インタフェース
ArrayList の特徴 1. List インタフェースの実装クラスのひとつ ◦ 他には LinkedList(連結リスト)など 2. 複数のマーカーインタフェース(後述)がある
3. AbstractList を継承して実装されている p pu ub bl li ic c c cl la as ss s A Ar rr ra ay yL Li is st t< <E E> > e ex xt te en nd ds s A Ab bs st tr ra ac ct tL Li is st t< <E E> > i im mp pl le em me en nt ts s L Li is st t< <E E> >, , R Ra an nd do om mA Ac cc ce es ss s, , C Cl lo on ne ea ab bl le e, , S Se er ri ia al li iz za ab bl le e
ArrayList のメソッド • ArrayList 固有のメソッドのメソッドはほぼない ◦ e en ns su
ur re eC Ca ap pa ac ci it ty y( (i in nt t) ), t tr ri im mT To oS Si iz ze e( () ) のみが固有 • ArrayList を知るために ◦ List インタフェースのことを知る必要がある ◦ さらに、その親インタフェースも知る必要がある
List インタフェースとは • Collections Framework の⼀部 (↑オブジェクトの集合を操作するフレームワーク) 【 主なインタフェース 】
List インタフェースの継承階層 • Iterable ◦ Collection ▪ SequencedCollection ▪ List
List の実装 = 親も含めたすべてのインタフェースの実装 → これらのインタフェースの違いは︖
List インタフェースについて • 要素が順番に格納されているコレクション • インデックスでアクセスできる • 任意の位置に操作(追加、削除など)ができる
Listインタフェースの主なメソッド (1) 操作 戻り値 メソッド名と引数 追加 void add(int index, E
element) 取得 E get(int index) 削除 E remove(int index) 検索 int indexOf(Object o) 部分取得 List<E> subList(int fromIndex, int toIndex) ソート void sort(Comparator<? super E> c) • インデックスを指定しての操作が特徴的
Listインタフェースの主なメソッド (2) 操作 戻り値 メソッド名と引数 ⼀致 boolean equals(Object o) ⽐較
int hashCode() • List インタフェースとして e eq qu ua al ls s と h ha as sh hC Co od de e が定義さ れている ◦ 実装に関わらず、リスト内の要素がすべて同じなら e eq qu ua al ls s が t tr ru ue e で、h ha as sh hC Co od de e の値が等しくなる
SequencedCollectionインタフェース • 要素が連続したコレクション • 両端から連続してアクセスできる • 両端に対して操作できる
SequencedCollectionインタフェース • Java 21 で追加された ◦ Deque や SortedSet といった連続したコレクションを統⼀
的に扱えるようにするため
SequencedCollectionのメソッド 操作 戻り値 メソッドと引数 追加 void addFirst(E e) 追加 void
addLast(E e) 取得 E getFirst() 取得 E getLast() 削除 E removeFirst() 削除 E removeLast() • すべて デフォルトメソッド (インタフェースで実装が提供されている)
SequencedCollectionのメソッド 操作 戻り値 メソッドと引数 逆順View SequencedCollection<E> reversed() • 要素の内容を逆順にした View
を取得できる ◦ View に変更した内容は、元のコレクションに反映される ◦ この View は、for ループできる f fo or r ( (v va ar r e e : : l li is st t. .r re ev ve er rs se ed d( () )) ) { { S Sy ys st te em m. .o ou ut t. .p pr ri in nt tl ln n( (e e) ); ; } }
Collection インタフェース • 要素のコレクション ◦ 順序は規定されていない • Collections Framework のルートインタフェース
Collection の主なメソッド (1) 操作 戻り値 メソッドと引数 追加 boolean add(E element)
追加 boolean addAll(Collection<? extends E> c) 削除 E remove(Object element) 検索 boolean contains(Object element) • List インタフェースと異なる a ad dd d( (E E) ) がある ◦ インデックスの指定ができない ◦ 戻り値がある(Set でコレクションが変更されなかった場 合は f fa al ls se e になる。List の場合は常に t tr ru ue e になる)
Collection の主なメソッド (2) 操作 戻り値 メソッドと引数 ストリーム Stream<E> stream() 変換
Object[] toArray() 変換 T[] toArray() • 要素を⼀つ取得するメソッドはない ◦ s st tr re ea am m( () ) や i it te er ra at to or r( () ) を使う
Iterable インタフェース • イテレータを提供する ◦ イテレータにより、要素を⼀つずつ取り出せる ◦ このインタフェースを実装したクラスは、拡張for⽂ (foreachループ)で使えるようになる
Iterable インタフェース 操作 戻り値 メソッドと引数 イテレーターの取得 Iterator<T> iterator() • もともとは
Colleciton インタフェースにあったメソッド ◦ Java 5 で独⽴したインタフェースになった • この他に、Java 8 でデフォルトメソッドが追加された ◦ v vo oi id d f fo or rE Ea ac ch h( (C Co on ns su um me er r< <? ? s su up pe er r T T> > a ac ct ti io on n) ) ◦ S Sp pl li it te er ra at to or r< <T T> > s sp pl li it te er ra at to or r( () )
ArrayList の特徴 (再掲) 1. List インタフェースの実装クラスのひとつ ◦ 他には LinkedList(連結リスト)など 2.
複数のマーカーインタフェース(後述)がある 3. AbstractList を継承して実装されている p pu ub bl li ic c c cl la as ss s A Ar rr ra ay yL Li is st t< <E E> > e ex xt te en nd ds s A Ab bs st tr ra ac ct tL Li is st t< <E E> > i im mp pl le em me en nt ts s L Li is st t< <E E> >, , R Ra an nd do om mA Ac cc ce es ss s, , C Cl lo on ne ea ab bl le e, , S Se er ri ia al li iz za ab bl le e
マーカーインタフェース • ArrayList では3つ付与されている p pu ub bl li ic
c c cl la as ss s A Ar rr ra ay yL Li is st t< <E E> > e ex xt te en nd ds s A Ab bs st tr ra ac ct tL Li is st t< <E E> > i im mp pl le em me en nt ts s L Li is st t< <E E> >, , R Ra an nd do om mA Ac cc ce es ss s, , C Cl lo on ne ea ab bl le e, , S Se er ri ia al li iz za ab bl le e メソッドやフィールドが⼀切定義されていないインタフェース。 クラスの特徴を表すために⽤いる。 マーカーインタフェース
各マーカーインタフェースの意味 • RandomAccess ◦ ランダムアクセスが得意 ◦ ⼀部の処理(C Co ol ll
le ec ct ti io on ns s. .b bi in na ar ry yS Se ea ar rc ch h( () )など)で は、このインタフェースの有無によって使⽤するアルゴ リズムを変えている • Cloneable ◦ c cl lo on ne e( () ) メソッドに対応 • Serializable ◦ シリアライズ可能
ArrayList の親クラス • AbstractList を継承して実装されている p pu ub bl li
ic c c cl la as ss s A Ar rr ra ay yL Li is st t< <E E> > e ex xt te en nd ds s A Ab bs st tr ra ac ct tL Li is st t< <E E> > i im mp pl le em me en nt ts s L Li is st t< <E E> >, , R Ra an nd do om mA Ac cc ce es ss s, , C Cl lo on ne ea ab bl le e, , S Se er ri ia al li iz za ab bl le e
ArrayList の親クラス • インタフェースごとに抽象クラスが⽤意されている ◦ 実装を簡単に⽤意できるようになっている
2. ArrayList のアルゴリズム
注目ポイント • 操作(要素の追加、削除など)による内部の変化 • 初期容量の⼤事さ ◦ ⼤きいほうが良いが、メモリ消費量とのトレードオフ • 操作ごとの計算量(オーダー)の違い ◦
O(1)︓サイズによらず⼀定時間で処理(速い) ◦ O(n)︓サイズによって線形時間で処理(遅い) • マルチスレッド非対応の理由
今回説明する操作 • 初期状態 • 末尾に要素を追加 → O(1), O(n) • 途中に 〃
→ O(n) • 末尾の要素を削除 → O(1) • 途中の 〃 → O(n) • インデックス指定で要素を取得 → O(1) • ある要素が含まれているか → O(n) • リストが⼀致しているか → O(n)
ArrayList の初期状態 • 内部に配列と、現在使⽤中のサイズを持っている • 配列の⼤きさを容量(capacity)という ◦ リストの作成時に、初期容量を指定できる • リストに保持するデータを要素(element)という
末尾に要素を追加 → O(1) 配列に空きがある場合 1. 空いてる末尾にデータを⼊れる 2. サイズを + 1
末尾に要素を追加 → O(n) 配列に空きがない場合 1. より⼤きな新しい配列を⽤意し、データをコピー 2. 新しい配列の空いてる末尾にデータを⼊れる 3. サイズを
+ 1
途中に要素を追加 → O(n) 1. 追加したい要素以降を後ろにコピー 2. 空いた箇所にデータを⼊れる 3. サイズを +
1
末尾の要素を削除 → O(1) 1. 末尾の要素を n nu ul ll l
で上書き 2. サイズを - 1
途中の要素を削除 → O(n) 1. 削除したい要素以降を前にコピー 2. 末尾の要素を n nu ul
ll l で上書き 3. サイズを - 1
インデックスで要素を取得 → O(1) 1. 配列の指定されたインデックスにアクセス
ある要素が含まれているか → O(n) 1. 先頭から順番に、⼀致する要素があるか判定 ⼀致するかどうか要素の equals メソッドで判定 Java の場合
リストが⼀致しているか → O(n) 1. 先頭から順番に、すべての要素が⼀致しているか判定
マルチスレッド非対応の理由 • 要素の変更(追加、削除、etc...)は、内部の配列への変更 とサイズの変更を⾏う ◦ 2つの変更はアトミックに⾏われることを前提としている • 複数のスレッドから変更を⾏うと… ◦ 処理の割り込みにより、内部が⽭盾した状態になること
がある
マルチスレッドで壊れる例 複数のスレッドが同時に追加した場合 スレッド1 スレッド2 末尾に要素を追加 ↓ 末尾に要素を追加 サイズを +1 ↓
サイズを +1 この結果…(次ページ)
マルチスレッドで壊れる例 • 追加したはずのデータが消える ◦ どちらかが上書きしてしまう • 現在の状態とサイズが⽭盾する ◦ サイズと配列の要素数が⼀致しない
マルチスレッドで使う場合 • ArrayList を synchronizedList でラップする v va ar r
l li is st t = = n ne ew w A Ar rr ra ay yL Li is st t< <S St tr ri in ng g> >( (. .. .. .) ); ; v va ar r s sy yn nc cL Li is st t = = C Co ol ll le ec ct ti io on ns s. .s sy yn nc ch hr ro on ni iz ze ed dL Li is st t( (l li is st t) ); ; • または CopyOnWriteArrayList(スレッドセーフな ArrayList 実装)を使う
ArrayList の実装 (ソースコードを読む)
注目ポイント • 処理の流れ • 処理の⼯夫 ◦ どのような最適化が施されているか • 標準ライブラリゆえの苦悩 ◦
そんなことも考えなきゃいけないの︖という点
⚠ 注意 • ここからは Java 23 のコードを元に説明します。 ◦ 今後のバージョンで変わるかもしれません。 •
紹介するコードは、説明の都合で⼀部を省略したり、メ ソッドをまとめたりしています。 • ぜひ実際のコードもご確認ください。 https://github.com/openjdk/jdk/blob/master/src/java.base/ share/classes/java/util/ArrayList.java
実装を読むメソッド • フィールド変数 • コンストラクタ • 要素の追加(add) • 〃 取得(get) •
〃 削除(remove) • ある要素が含まれているか︖(contains) • リストが⼀致しているか︖(equals)
フィールド変数 / // / データ格納用の配列 t tr ra an ns
si ie en nt t O Ob bj je ec ct t[ [] ] e el le em me en nt tD Da at ta a; ; ↑ ↑ シリアル化の対象外にする修飾子 / // / 現在使用中のサイズ p pr ri iv va at te e i in nt t s si iz ze e; ; ( (A Ab bs st tr ra ac ct tL Li is st t) ) / // / 構造が変更された回数(ループ中の変更を検出するための変数) p pr ro ot te ec ct te ed d t tr ra an ns si ie en nt t i in nt t m mo od dC Co ou un nt t = = 0 0; ;
コンストラクタ • A Ar rr ra ay yL Li is
st t( () ) ◦ 初期容量10で空のリストを作成 • A Ar rr ra ay yL Li is st t( (i in nt t i in ni it ti ia al lC Ca ap pa ac ci it ty y) ) ◦ 指定された初期容量で空のリストを作成 • A Ar rr ra ay yL Li is st t( (C Co ol ll le ec ct ti io on n< <? ? e ex xt te en nd ds s E E> > c c) ) ◦ コピーコンストラクタ ◦ 指定されたコレクションをコピーしたリストを作成
ArrayList() - 古い実装 初期容量10で空のリストを作成 p pu ub bl li ic
c A Ar rr ra ay yL Li is st t( () ) { { t th hi is s( (1 10 0) ); ; } } • 初期容量を指定するコンストラクタを呼び出す ◦ t th hi is s. .e el le em me en nt tD Da at ta a = = n ne ew w O Ob bj je ec ct t[ [1 10 0] ] となる Java 7 Update 40 以降では、次ページの遅延初期化する実装に変更 この実装は Java 7 Update 25 まで
ArrayList() - 現在の実装 p pr ri iv va at te
e s st ta at ti ic c f fi in na al l O Ob bj je ec ct t[ [] ] D DE EF FA AU UL LT TC CA AP PA AC CI IT TY Y_ _E EM MP PT TY Y_ _E EL LE EM ME EN NT TD DA AT TA A = = { {} }; ; p pu ub bl li ic c A Ar rr ra ay yL Li is st t( () ) { { t th hi is s. .e el le em me en nt tD Da at ta a = =D DE EF FA AU UL LT TC CA AP PA AC CI IT TY Y_ _E EM MP PT TY Y_ _E EL LE EM ME EN NT TD DA AT TA A; ; } } • 配列を作成せず、Singleton な空配列を使う ◦ 最初に a ad dd d メソッドが呼ばれた際に作成(遅延初期化) ◦ ArrayList を作っても要素の追加が⾏われないことが多々 あるため(JDK-7143928)
ArrayList(int initialCapacity) 指定された初期容量で空のリストを作成 p pr ri iv va at te
e s st ta at ti ic c f fi in na al l O Ob bj je ec ct t[ [] ] E EM MP PT TY Y_ _E EL LE EM ME EN NT TD DA AT TA A = = { {} }; ; p pu ub bl li ic c A Ar rr ra ay yL Li is st t( (i in nt t i in ni it ti ia al lC Ca ap pa ac ci it ty y) ) { { i if f ( (i in ni it ti ia al lC Ca ap pa ac ci it ty y > > 0 0) ) { { t th hi is s. .e el le em me en nt tD Da at ta a = = n ne ew w O Ob bj je ec ct t[ [i in ni it ti ia al lC Ca ap pa ac ci it ty y] ]; ; } } e el ls se e i if f ( (i in ni it ti ia al lC Ca ap pa ac ci it ty y = == = 0 0) ) { { t th hi is s. .e el le em me en nt tD Da at ta a = = E EM MP PT TY Y_ _E EL LE EM ME EN NT TD DA AT TA A; ; } } e el ls se e { { t th hr ro ow w n ne ew w I Il ll le eg ga al lA Ar rg gu um me en nt tE Ex xc ce ep pt ti io on n( (… …s sn ni ip p… …) ); ; } } } }
ArrayList(int initialCapacity) 引数 i in ni it ti ia al
lC Ca ap pa ac ci it ty y が … 1. > 0 の場合 ◦ i in ni it ti ia al lC Ca ap pa ac ci it ty y の容量の配列を作成し、 t th hi is s. .e el le em me en nt tD Da at ta a に代⼊ 2. == 0 の場合 ◦ Singleton の空配列 E EM MP PT TY Y_ _E EL LE EM ME EN NT TD DA AT TA A を、 t th hi is s. .e el le em me en nt tD Da at ta a に代⼊ 3. < 0 の場合 ◦ I Il ll le eg ga al lA Ar rg gu um me en nt tE Ex xc ce ep pt ti io on n をスロー
ArrayList(Collection<? extends E> c) 指定されたコレクションをコピーしたリストを作成 p pu ub bl li
ic c A Ar rr ra ay yL Li is st t( (C Co ol ll le ec ct ti io on n< <? ? e ex xt te en nd ds s E E> > c c) ) { { O Ob bj je ec ct t[ [] ] a a = = c c. .t to oA Ar rr ra ay y( () ); ; i if f ( (( (t th hi is s. .s si iz ze e = = a a. .l le en ng gt th h) ) ! != = 0 0) ) { { i if f ( (c c. .g ge et tC Cl la as ss s( () ) = == = A Ar rr ra ay yL Li is st t. .c cl la as ss s) ) { { t th hi is s. .e el le em me en nt tD Da at ta a = = a a; ; } } e el ls se e { { t th hi is s. .e el le em me en nt tD Da at ta a = = A Ar rr ra ay ys s. .c co op py yO Of f( (a a, , s si iz ze e, , O Ob bj je ec ct t[ [] ]. .c cl la as ss s) ); ; } } } } e el ls se e { { t th hi is s. .e el le em me en nt tD Da at ta a = = E EM MP PT TY Y_ _E EL LE EM ME EN NT TD DA AT TA A; ; } }
ArrayList(Collection<? extends E> c) 1. c c. .t to oA
Ar rr ra ay y( () ) によりコレクションの配列を取得 2. 取得した配列の⻑さを t th hi is s. .s si iz ze e に代⼊ 3. t th hi is s. .s si iz ze e > 0 の場合 ◦ (次ページに記載) 4. t th hi is s. .s si iz ze e == 0 の場合 ◦ Singleton の空配列 E EM MP PT TY Y_ _E EL LE EM ME EN NT TD DA AT TA A を、 t th hi is s. .e el le em me en nt tD Da at ta a に代⼊
ArrayList(Collection<? extends E> c) t th hi is s. .s
si iz ze e > 0 の場合 1. 引数 c c が ArrayList の場合 ◦ 取得した配列 a a をt th hi is s. .e el le em me en nt tD Da at ta a に代⼊ 2. 引数 c c が ArrayList 以外の場合 ◦ 取得した配列 a a の中⾝を新しい O Ob bj je ec ct t[ [] ] にコピーして から、t th hi is s. .e el le em me en nt tD Da at ta a に代⼊(防御的コピー) → なぜ防御的コピーが必要︖ → なぜ ArrayList の場合は不要︖
防御的コピーをする理由 (1) • Collection の t to oA Ar rr
ra ay y( () ) の戻り値の型は O Ob bj je ec ct t[ [] ] → 任意の型の配列(S St tr ri in ng g[ [] ]など)を返すことができて しまう(配列の共変性) • もし O Ob bj je ec ct t[ [] ] 以外だったら︖ ◦ そのまま t th hi is s. .e el le em me en nt tD Da at ta a に使ってしまうと、リス トの変更時に ArrayStoreException のリスク︕ これを避けるため、新しく O Ob bj je ec ct t[ [] ] を作りコピーしている
防御的コピーをする理由 (2) • 配列の参照を、元のコレクションが保持してるかも︖ p pu ub bl li ic
c E Ev vi il lC Co ol ll le ec ct ti io on n i im mp pl le em me en nt ts s C Co ol ll le ec ct ti io on n< <E E> > { { p pu ub bl li ic c O Ob bj je ec ct t[ [] ] e el le em me en nt ts s = = n ne ew w O Ob bj je ec ct t[ [1 10 0] ]; ; p pu ub bl li ic c O Ob bj je ec ct t[ [] ] t to oA Ar rr ra ay y( () ) { { r re et tu ur rn n e el le em me en nt ts s; ; } } } } • この場合、EvilCollection の e el le em me en nt ts s を操作することで、 ArrayList の外部から変更ができてしまう︕ ◦ コンストラクタ内でコピーすることで、できなくする
ArrayList の場合、コピーは不要︖ • ArrayList の t to oA Ar rr
ra ay y( () ) の場合 ◦ 新しい O Ob bj je ec ct t[ [] ] にコピーしたものを返しているから、 そのまま使って⼤丈夫 p pu ub bl li ic c O Ob bj je ec ct t[ [] ] t to oA Ar rr ra ay y( () ) { { r re et tu ur rn n A Ar rr ra ay ys s. .c co op py yO Of f( (e el le em me en nt tD Da at ta a, , s si iz ze e) ); ; } }
boolean add(E e) 末尾に、指定された要素を追加 p pu ub bl li ic
c b bo oo ol le ea an n a ad dd d( (E E e e) ) { { m mo od dC Co ou un nt t+ ++ +; ; a ad dd d( (e e, , e el le em me en nt tD Da at ta a, , s si iz ze e) ); ; r re et tu ur rn n t tr ru ue e; ; } } p pr ri iv va at te e v vo oi id d a ad dd d( (E E e e, , O Ob bj je ec ct t[ [] ] e el le em me en nt tD Da at ta a, , i in nt t s s) ) { { i if f ( (s s = == = e el le em me en nt tD Da at ta a. .l le en ng gt th h) ) e el le em me en nt tD Da at ta a = = g gr ro ow w( (s si iz ze e + + 1 1) ); ; e el le em me en nt tD Da at ta a[ [s s] ] = = e e; ; t th hi is s. .s si iz ze e = = s s + + 1 1; ; } }
boolean add(E e) 1. t th hi is s. .m
mo od dC Co ou un nt t を + 1 2. 空きがない場合 ◦ g gr ro ow w( (s si iz ze e + + 1 1) ) で新しい容量の配列を作る(後述) 3. 最後尾にオブジェクトを追加 4. t th hi is s. .s si iz ze e を + 1 5. t tr ru ue e を return
void add(int index, E element) 指定された位置に、指定された要素を追加 p pu ub bl
li ic c v vo oi id d a ad dd d( (i in nt t i in nd de ex x, , E E e el le em me en nt t) ) { { r ra an ng ge eC Ch he ec ck kF Fo or rA Ad dd d( (i in nd de ex x) ); ; m mo od dC Co ou un nt t+ ++ +; ; f fi in na al l i in nt t s s; ; O Ob bj je ec ct t[ [] ] e el le em me en nt tD Da at ta a = = t th hi is s. .e el le em me en nt tD Da at ta a; ; i if f ( (( (s s = = s si iz ze e) ) = == = e el le em me en nt tD Da at ta a. .l le en ng gt th h) ) e el le em me en nt tD Da at ta a = = g gr ro ow w( (s s + + 1 1) ); ; S Sy ys st te em m. .a ar rr ra ay yc co op py y( (e el le em me en nt tD Da at ta a, , i in nd de ex x, , e el le em me en nt tD Da at ta a, , i in nd de ex x + + 1 1, , s s - - i in nd de ex x) ); ; e el le em me en nt tD Da at ta a[ [i in nd de ex x] ] = = e el le em me en nt t; ; s si iz ze e = = s s + + 1 1; ; } }
void add(int index, E element) 1. 範囲外(i in nd de
ex x < < 0 0 または i in nd de ex x > >= = s si iz ze e)の場合 ◦ IndexOutOfBoundsException をスロー 2. t th hi is s. .m mo od dC Co ou un nt t を + 1 3. 空きがない場合 ◦ g gr ro ow w( (s si iz ze e + + 1 1) ) で新しい容量の配列を作る(後述) 4. 指定されたインデックス + 1 以降を、⼀つ後ろにコピー 5. 指定されたインデックスにオブジェクトを追加 6. t th hi is s. .s si iz ze e を + 1
grow(int minCapacity) 新しい⻑さの配列を作り直す p pr ri iv va at te
e O Ob bj je ec ct t[ [] ] g gr ro ow w( (i in nt t m mi in nC Ca ap pa ac ci it ty y) ) { { i in nt t o ol ld dC Ca ap pa ac ci it ty y = = e el le em me en nt tD Da at ta a. .l le en ng gt th h; ; i if f ( (o ol ld dC Ca ap pa ac ci it ty y > > 0 0 | || | e el le em me en nt tD Da at ta a ! != = D DE EF FA AU UL LT TC CA AP PA AC CI IT TY Y_ _E EM MP PT TY Y_ _E EL LE EM ME EN NT TD DA AT TA A) ) { { / // / 省略:必要な容量を計算 r re et tu ur rn n e el le em me en nt tD Da at ta a = = A Ar rr ra ay ys s. .c co op py yO Of f( (e el le em me en nt tD Da at ta a, , n ne ew wC Ca ap pa ac ci it ty y) ); ; } } e el ls se e { { r re et tu ur rn n e el le em me en nt tD Da at ta a = = n ne ew w O Ob bj je ec ct t[ [M Ma at th h. .m ma ax x( (D DE EF FA AU UL LT T_ _C CA AP PA AC CI IT TY Y, , m mi in nC Ca ap pa ac ci it ty y) )] ]; ; } }
grow(int minCapacity) 1. 引数なしコンストラクタを実⾏し、まだ空の場合 1. 引数 m mi in nC
Ca ap pa ac ci it ty y か D DE EF FA AU UL LT T_ _C CA AP PA AC CI IT TY Y(= 10)の いずれか⼤きい⽅の容量で新しく配列を作成 このタイミングで遅延初期化する ポイント1
grow(int minCapacity) 1. 初期化済みの場合 1. 引数 m mi in nC
Ca ap pa ac ci it ty y か 現在の容量の 1.5倍の⼤きい⽅を 容量とする(例外あり、最後に解説) 2. 新しい配列に、現在の配列の内容をコピー 3. t th hi is s. .e el le em me en nt tD Da at ta a を新しい配列に差し替え 最低限必要な分ではなく、まとめて⼤きくする ポイント2
補⾜︓容量の拡⼤・縮⼩ • a ad dd d( (E E) )せずに容量を拡⼤したい場合 ◦
e en ns su ur re eC Ca ap pa ac ci it ty y( (i in nt t m mi in nC Ca ap pa ac ci it ty y) ) を使う ◦ ⼤量の要素を追加する前に使うと、配列のコピーを減ら せる • 容量は⾃動的に縮⼩しない ◦ 縮⼩するには、明⽰的に t tr ri im mT To oS Si iz ze e( () ) を実⾏する ◦ 要素をもう追加しないと確定したときに使うと、メモリ 使⽤量を減らせる
E get(int index) このリスト内の指定された位置にある要素を返す p pu ub bl li ic
c E E g ge et t( (i in nt t i in nd de ex x) ) { { O Ob bj je ec ct ts s. .c ch he ec ck kI In nd de ex x( (i in nd de ex x, , t th hi is s. .s si iz ze e) ); ; / // / 1 1 r re et tu ur rn n ( (E E) ) t th hi is s. .e el le em me en nt tD Da at ta a[ [i in nd de ex x] ]; ; / // / 2 2 } } 1. 範囲外(i in nd de ex x < < 0 0 または i in nd de ex x > >= = s si iz ze e)の場合 ◦ IndexOutOfBoundsException をスロー 2. t th hi is s. .e el le em me en nt tD Da at ta a[ [i in nd de ex x] ] を return
E remove(int index) 指定された位置にある要素を削除 p pu ub bl li ic
c E E r re em mo ov ve e( (i in nt t i in nd de ex x) ) { { O Ob bj je ec ct ts s. .c ch he ec ck kI In nd de ex x( (i in nd de ex x, , s si iz ze e) ); ; f fi in na al l O Ob bj je ec ct t[ [] ] e es s = = e el le em me en nt tD Da at ta a; ; E E o ol ld dV Va al lu ue e = = ( (E E) ) e es s[ [i in nd de ex x] ]; ; f fa as st tR Re em mo ov ve e( (e es s, , i in nd de ex x) ); ; / // / (次ページ参照) r re et tu ur rn n o ol ld dV Va al lu ue e; ; } }
void fastRemove(Object[] es, int i) 指定された位置にある要素を削除 p pr ri iv
va at te e v vo oi id d f fa as st tR Re em mo ov ve e( (O Ob bj je ec ct t[ [] ] e es s, , i in nt t i i) ) { { m mo od dC Co ou un nt t+ ++ +; ; f fi in na al l i in nt t n ne ew wS Si iz ze e; ; i if f ( (( (n ne ew wS Si iz ze e = = t th hi is s. .s si iz ze e - - 1 1) ) > > i i) ) S Sy ys st te em m. .a ar rr ra ay yc co op py y( (e es s, , i i + + 1 1, , e es s, , i i, , n ne ew wS Si iz ze e - - i i) ); ; e es s[ [s si iz ze e = = n ne ew wS Si iz ze e] ] = = n nu ul ll l; ; } }
void fastRemove(Object[] es, int i) 1. t th hi is
s. .m mo od dC Co ou un nt t を + 1 2. 指定されたインデックスが末尾でない場合 ◦ 指定されたインデックス + 1 以降を、⼀つ⼿前にコピー を代⼊ 3. サイズを更新 4. 末尾の要素に n nu ul ll l を代⼊
boolean contains(Object o) 指定された要素がこのリストに含まれているかどうか p pu ub bl li ic
c b bo oo ol le ea an n c co on nt ta ai in ns s( (O Ob bj je ec ct t o o) ) { { r re et tu ur rn n i in nd de ex xO Of f( (o o) ) > >= = 0 0; ; } } → i in nd de ex xO Of f( (O Ob bj je ec ct t o o) ) を呼ぶだけ
int indexOf(Object o) p pu ub bl li ic c
i in nt t i in nd de ex xO Of f( (O Ob bj je ec ct t o o) ) { { r re et tu ur rn n i in nd de ex xO Of fR Ra an ng ge e( (o o, , 0 0, , s si iz ze e) ); ; } } i in nt t i in nd de ex xO Of fR Ra an ng ge e( (O Ob bj je ec ct t o o, , i in nt t s st ta ar rt t, , i in nt t e en nd d) ) { { O Ob bj je ec ct t[ [] ] e es s = = e el le em me en nt tD Da at ta a; ; i if f ( (o o = == = n nu ul ll l) ) { { / // / 引数が n nu ul ll l の検索処理(次ページ) } } e el ls se e { { / // / 引数が n nu ul ll l 以外の検索処理(次々ページ) } } r re et tu ur rn n - -1 1; ; / // / 見つからなかった } }
o o = == = n nu ul ll l
の検索処理 f fo or r ( (i in nt t i i = = s st ta ar rt t; ; i i < < e en nd d; ; i i+ ++ +) ) { { i if f ( (e es s[ [i i] ] = == = n nu ul ll l) ) { { r re et tu ur rn n i i; ; } } } } • 先頭から順に、要素が n nu ul ll l か確認 ◦ n nu ul ll l なら、そのインデックスを return
o o ! != = n nu ul ll l
の検索処理 f fo or r ( (i in nt t i i = = s st ta ar rt t; ; i i < < e en nd d; ; i i+ ++ +) ) { { i if f ( (o o. .e eq qu ua al ls s( (e es s[ [i i] ]) )) ) { { r re et tu ur rn n i i; ; } } } } • 先頭から順に、引数のオブジェクトの e eq qu ua al ls s メソッドで 判定 ◦ 戻り値が t tr ru ue e なら、そのインデックスを return
boolean equals(Object o) p pu ub bl li ic c
b bo oo ol le ea an n e eq qu ua al ls s( (O Ob bj je ec ct t o o) ) { { i if f ( (o o = == = t th hi is s) ) { { r re et tu ur rn n t tr ru ue e; ; / // / 1 1 } } i if f ( (! !( (o o i in ns st ta an nc ce eo of f L Li is st t) )) ) { { r re et tu ur rn n f fa al ls se e; ; / // / 2 2 } } / // / 次ページへ 1. 同じオブジェクトなら t tr ru ue e 2. ⽐較対象が List でなければ f fa al ls se e
boolean equals(Object o) f fi in na al l i
in nt t e ex xp pe ec ct te ed dM Mo od dC Co ou un nt t = = m mo od dC Co ou un nt t; ; b bo oo ol le ea an n e eq qu ua al l = = ( (o o. .g ge et tC Cl la as ss s( () ) = == = A Ar rr ra ay yL Li is st t. .c cl la as ss s) ) ? ? e eq qu ua al ls sA Ar rr ra ay yL Li is st t( (( (A Ar rr ra ay yL Li is st t< <? ?> >) ) o o) ) : : e eq qu ua al ls sR Ra an ng ge e( (( (L Li is st t< <? ?> >) ) o o, , 0 0, , s si iz ze e) ); ; / // / 1 1 c ch he ec ck kF Fo or rC Co om mo od di if fi ic ca at ti io on n( (e ex xp pe ec ct te ed dM Mo od dC Co ou un nt t) ); ; / // / 2 2 r re et tu ur rn n e eq qu ua al l; ; } } 1. ⽐較対象が ArrayList かどうかで分岐 (Java 11 〜) 2. ⽐較処理中に m mo od dC Co ou un nt t が変わっていた場合 ◦ C Co on nc cu ur rr re en nt tM Mo od di if fi ic ca at ti io on nE Ex xc ce ep pt ti io on n をスロー
ArrayList との⽐較処理 p pr ri iv va at te e
b bo oo ol le ea an n e eq qu ua al ls sA Ar rr ra ay yL Li is st t( (A Ar rr ra ay yL Li is st t< <? ?> > o ot th he er r) ) { { f fi in na al l i in nt t o ot th he er rM Mo od dC Co ou un nt t = = o ot th he er r. .m mo od dC Co ou un nt t; ; f fi in na al l i in nt t s s = = s si iz ze e; ; b bo oo ol le ea an n e eq qu ua al l; ; i if f ( (e eq qu ua al l = = ( (s s = == = o ot th he er r. .s si iz ze e) )) ) { { / // / 1 1 / // / 各要素の比較処理(後述) } } o ot th he er r. .c ch he ec ck kF Fo or rC Co om mo od di if fi ic ca at ti io on n( (o ot th he er rM Mo od dC Co ou un nt t) ); ; / // / 2 2 r re et tu ur rn n e eq qu ua al l; ; } }
ArrayList との⽐較処理 1. ⽐較対象とのサイズが⼀致する場合 ◦ すべての要素が⼀致するか⽐較(次ページ) ◦ (不⼀致なら、f fa al
ls se e で確定) 2. ⽐較処理中に⽐較対象の m mo od dC Co ou un nt t が変わっていた場合 ◦ C Co on nc cu ur rr re en nt tM Mo od di if fi ic ca at ti io on nE Ex xc ce ep pt ti io on n をスロー
各要素との⽐較処理 f fi in na al l O Ob bj
je ec ct t[ [] ] o ot th he er rE Es s = = o ot th he er r. .e el le em me en nt tD Da at ta a; ; f fi in na al l O Ob bj je ec ct t[ [] ] e es s = = e el le em me en nt tD Da at ta a; ; i if f ( (s s > > e es s. .l le en ng gt th h | || | s s > > o ot th he er rE Es s. .l le en ng gt th h) ) { { / // / 1 1 t th hr ro ow w n ne ew w C Co on nc cu ur rr re en nt tM Mo od di if fi ic ca at ti io on nE Ex xc ce ep pt ti io on n( () ); ; } } f fo or r ( (i in nt t i i = = 0 0; ; i i < < s s; ; i i+ ++ +) ) { { i if f ( (! !O Ob bj je ec ct ts s. .e eq qu ua al ls s( (e es s[ [i i] ], , o ot th he er rE Es s[ [i i] ]) )) ) { { / // / 2 2 e eq qu ua al l = = f fa al ls se e; ; b br re ea ak k; ; } } } }
各要素との⽐較処理 1. 配列の⻑さが、サイズよりも⼤きい場合 ◦ C Co on nc cu ur
rr re en nt tM Mo od di if fi ic ca at ti io on nE Ex xc ce ep pt ti io on n をスロー 2. 配列をループ ◦ O Ob bj je ec ct ts s. .e eq qu ua al ls s( (e es s[ [i i] ], , o ot th he er rE Es s[ [i i] ]) ) で⽐較 引数 a, b が等しい場合は t tr ru ue e を返す(以下のいずれか) • 同じオブジェクト(a a = == = b b) • 引数が両⽅とも n nu ul ll l • a a ! != = n nu ul ll l かつ a a. .e eq qu ua al ls s( (b b) ) Objects.equals(a,b)
boolean equals(Object o) (再掲) 続いて、ArrayList 以外との⽐較の場合 f fi in na
al l i in nt t e ex xp pe ec ct te ed dM Mo od dC Co ou un nt t = = m mo od dC Co ou un nt t; ; b bo oo ol le ea an n e eq qu ua al l = = ( (o o. .g ge et tC Cl la as ss s( () ) = == = A Ar rr ra ay yL Li is st t. .c cl la as ss s) ) ? ? e eq qu ua al ls sA Ar rr ra ay yL Li is st t( (( (A Ar rr ra ay yL Li is st t< <? ?> >) ) o o) ) : : e eq qu ua al ls sR Ra an ng ge e( (( (L Li is st t< <? ?> >) ) o o, , 0 0, , s si iz ze e) ); ; c ch he ec ck kF Fo or rC Co om mo od di if fi ic ca at ti io on n( (e ex xp pe ec ct te ed dM Mo od dC Co ou un nt t) ); ; r re et tu ur rn n e eq qu ua al l; ; } }
ArrayList 以外との⽐較 b bo oo ol le ea an n
e eq qu ua al ls sR Ra an ng ge e( (L Li is st t< <? ?> > o ot th he er r, , i in nt t f fr ro om m, , i in nt t t to o) ) { { f fi in na al l O Ob bj je ec ct t[ [] ] e es s = = e el le em me en nt tD Da at ta a; ; v va ar r o oi it t = = o ot th he er r. .i it te er ra at to or r( () ); ; f fo or r ( (; ; f fr ro om m < < t to o; ; f fr ro om m+ ++ +) ) { { i if f ( (! !o oi it t. .h ha as sN Ne ex xt t( () ) | || | ! !O Ob bj je ec ct ts s. .e eq qu ua al ls s( (e es s[ [f fr ro om m] ], , o oi it t. .n ne ex xt t( () )) )) ) { { r re et tu ur rn n f fa al ls se e; ; } } } } r re et tu ur rn n ! !o oi it t. .h ha as sN Ne ex xt t( () ); ; } }
ArrayList 以外との⽐較 1. ⾃⾝の配列をループ 1. iterator から⽐較対象の要素を取得し、 要素がないか要素が不⼀致の場合、f fa al
ls se e を return 2. ループの終了時点で、 ◦ ⽐較対象の要素が残っている→ f fa al ls se e を return ◦ ⽐較対象の要素が残っていない → t tr ru ue e を return ⽐較対象のリストの s si iz ze e( () ) の実装が O(n) の可能性があるため サイズの⽐較はしない
まとめ • インタフェース ◦ それぞれに違いがある ◦ List, SequencedCollection, Collection, Iterable
• アルゴリズム ◦ ArrayList の変更 = 内部の配列とサイズの変更 ◦ 「速い操作」と「遅い操作」がある • 実装 ◦ 最適化がされた実装になっている ◦ 標準ライブラリの苦悩が垣間⾒える
詳細解説︕ ArrayListの仕組みと実装 @YujiSoftware
補⾜︓grow の新しい容量の決定⽅法 • 引数 m mi in nC Ca ap
pa ac ci it ty y か 現在の容量の 1.5倍(⼤きい⽅) • ただし、I In nt te eg ge er r. .M MA AX X_ _V VA AL LU UE E - - 8 8 を超える場合 ◦ I In nt te eg ge er r. .M MA AX X_ _V VA AL LU UE E - - 8 8 で、以降は現在の容量 + 1 • さらに I In nt te eg ge er r. .M MA AX X_ _V VA AL LU UE E(= 2,147,483,647)を超える なら、OutOfMemoryError をスロー 1 10 0 → 1 15 5 → 2 22 2 → 3 33 3 → 4 49 9 → … …中略… … → 1 17 79 96 63 35 57 74 45 52 2 → 2 21 14 47 74 48 83 36 63 39 9 → 2 21 14 47 74 48 83 36 64 40 0 → 2 21 14 47 74 48 83 36 64 41 1 → … …中略… … → 2 21 14 47 74 48 83 36 64 47 7 → O Ou ut tO Of fM Me em mo or ry yE Er rr ro or r
補⾜︓Integer.MAX_VALUE - 8 って︖ • S SO OF FT T_
_M MA AX X_ _A AR RR RA AY Y_ _L LE EN NG GT TH H という定数値 ◦ 作成できる配列の⻑さ上限ギリギリの値 (JDK-6933217) • Java ⾔語仕様上は I In nt te eg ge er r. .M MA AX X_ _V VA AL LU UE E まで • しかし、JVM の実装によっては I In nt te eg ge er r. .M MA AX X_ _V VA AL LU UE E に近い⻑さ の配列を割り当てようとした場合、ヒープの空きに関わらず OutOfMemoryError("Requested array size exceeds VM limit")をスロー する • I In nt te eg ge er r. .M MA AX X_ _V VA AL LU UE E - - 8 8 なら、どの JVM でも⼤丈夫 配列の⻑さの上限
◦ https://docs.oracle.com/javase/jp/22/docs/api/java.base/java/ util/doc-files/coll-index.html • Collections Framework ⼊門 - もちだ ◦ https://www.slideshare.net/mikeneck/jjugccc-2019-spring- collections-framework-jjug-jjugccc-cccc1 • Effective Java 第3版 | Joshua Bloch/著, 柴⽥ 芳樹/訳 ◦ https://www.amazon.co.jp/dp/4621303252
参考資料 • ArrayList の防御的コピーについて ◦ Is there a good reason
to split in two different cases the following ArrayList constructor in the OpenJDK code? - Stack Overflow ◦ https://stackoverflow.com/q/77574918/1932017