Javaコレクション操作の基礎
Javaのアドベントカレンダー2020の記事になります。
Javaでは配列操作するためにいくつかの方法(コレクションライブラリ)が用意されています。
ですが、普段業務で利用するものは意外と限られているので、違いがあまり分からない人がいらっしゃるのかなと思います。
なので、それぞれの使い方や違いをまとめてみようと思います。
代表的な配列操作の種類
Javaには配列操作を行うために大きく3種類の方法があります。
- Array
- Collection
- Map
もう少し具体的には以下の図のような階層構造になっています。
画像参考: Java™チュートリアル -> Trail: Collections -> Lesson: Interfaces
上記を具体的に掘り下げて見ていきます。
Array
Arrayは作成時に決めた大きさで配列を保持します。
String[] books = new String[1]; // 初期化時に配列の大きさ「0」を指定します。
books[0] = "Java パフォーマンス";
System.out.println(books[0]); // Java パフォーマンス
最初に指定した大きさを超えて値をセットすることはできません。
books = new String[2];
books[0] = "Java パフォーマンス";
books[1] = "みんなのJava";
books[2] = "Effective Java";
// ここで以下のエラーが出力する
// Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 2 out of bounds for length 2
ですので、途中で配列の大きさが変わるような場合には以下のように配列を作り直す必要があります。
String[] books = new String[1];
books[0] = "Java パフォーマンス";
books = Arrays.copyOf(books, 2); // 配列を2の大きさで作成して、元の配列に存在した内容をコピーして格納する
books[1] = "みんなのJava";
System.out.println(books[0]); // Java パフォーマンス
System.out.println(books[1]); // みんなのJava
最初から長さがわかっている場合は良いですが、途中で追加・削除されたり、または配列の中で同じ値は許可しないなどの場合にはArrayだけだと実装量が増えてしまいます。
そこでよりシンプルに書けるのがこれから記載するCollection・Mapになります。
Collection
JavaのCollectionは最初に説明した通り、Collectionインターフェースを頂点に目的に応じていくつかのインターフェースが用意されています。
Collectionを継承している代表的なインターフェースは以下です。
- List
順序付けられたコレクションです。シーケンスとも呼ばれます。 - Set
重複要素のないコレクションです。 - Queue
処理の前に要素を保持するために設計されたコレクション。 - Deque
両端で要素の挿入および削除をサポートする線形コレクションです。
Collectionで定義されている代表的なメソッドは以下になります。
- add, addAll
要素を追加する - contains
指定された要素が含まれているか確認する - isEmpty
コレクションが空の場合はtrueを返却する - remove, removeAll, removeIf
コレクションから指定した要素を削除する - size
コレクション内の要素の数を返す
List
ではコレクションの具体的な中身を見ていこうと思います。
まずはListです。
Listもインターフェースとなっており、具体的な実装はListを継承したクラスで用意されています。
よく使われるListを継承したクラスは以下になります。
- ArrayList
- LinkedList
ArrayList
ArrayListはArray(配列)を便利に扱いやすくしたクラスです。
Arrayでは、作成時に決めた配列の大きさを変えることはできず、追加などでサイズを変更したい場合には新しく配列を作り直す必要がありました。
ArrayListでは、ArrayListを使う側が配列のサイズを意識せずに扱うことが出来るようになります。
List<String> books = new ArrayList<>();
books.add("Java パフォーマンス");
books.add("みんなのJava");
System.out.println(books.get(1)); // みんなのJava
new ArrayList<>() でArrayListのインスタンスを作成していますが、配列のサイズは指定していません。
その後、addメソッドで要素を追加していますが、問題なく要素が追加されgetで値が取得できています。
ArrayListは以下のような動きとなっています。
初回のbooks.add実行時
ある程度の大きさで配列が 作成されて、その1番目の要素に指定した値が格納される。
初回に決めた配列の大きさを超えた場合のbooks.add実行時
元々の配列をコピーしてかつ、より大きなサイズで配列を作成して次の要素に値を格納する。
LinkedList
LinkedListは双方向連結リストのことで、LinkedList内に保持する要素は、値とは別に前後の要素への参照(ポインタ)を保持します。
普通に使う分にはArrayListと同様です。(Listインターフェースを継承しているためそれはそう)
List<String> books = new LinkedList<>();
books.add("Java パフォーマンス");
books.add("みんなのJava");
System.out.println(books.get(1)); // みんなのJava
LinkedListは以下のような動きとなっています。
値の持ち方
LinkedListとしては、最初の要素と最後の要素への参照だけを保持します。
中身の要素はNodeとして、それぞれの要素が要素の値と前後への参照を保持しています。
つまりそれぞれの要素がリンクしてListとしての順番を保持しています。
値を追加するとき
値を追加するときは、追加したい場所の前後の要素が持つ参照を、追加した要素へ変更するだけです。
ArrayList/LinkedListの計算量
上記の特徴を踏まえたうえで、それぞれの計算量を比較してみます。
結果は以下になります。
| メソッド | アクセスする場所 | ArrayList | LinkedList |
|---|---|---|---|
| get | ランダムな要素 | O(1) | O(N/2) |
| get | 最初の要素 | O(1) | O(1) |
| get | 最後の要素 | O(1) | O(1) |
| add | ランダムな要素 | O(N) | O(N/2) |
| add | 最初の要素 | O(N) | O(1) |
| add | 最後の要素 | O(1) | O(1) |
| set | ランダムな要素 | O(1) | O(N/2) |
| set | 最初の要素 | O(1) | O(1) |
| set | 最後の要素 | O(1) | O(1) |
| remove | ランダムな要素 | O(N) | O(N/2) |
| remove | 最初の要素 | O(N) | O(1) |
| remove | 最後の要素 | O(1) | O(1) |
具体的に説明していきます。
get
ArrayListの場合は、メンバ変数でArrayを保持しているため各要素へのアクセスはArrayの場所をそのまま指定するだけで可能です。そのためO(1)でのアクセスになります。
LinkedListの場合、メンバ変数で最初と最後の要素への参照を保持しているため、最初と最後の要素に対してはO(1)でのアクセスになります。
しかし途中の要素へのアクセスの場合は、最初もしくは最後の要素から順番にリンクを辿っていく必要があるため、O(N/2)でのアクセスになります。
ロジックとしては最初か最後近い方のロジックから辿るようになっています。
add
ArrayListの場合は、最後の要素への追加の場合は基本的にはすでに用意されているArrayに対して追加するだけのため、O(1)です。
参考となりますが、ArrayListのメンバ変数で保持するArrayサイズの拡張は、Arrayのサイズが大きくなるに連れて一回の拡張量も増えるため気にしなくても問題ありません。
最後以外の要素へ追加する場合は、指定した箇所以降の要素を1つずつ後ろに移動する必要があるため、配列の作り直しが必要になります。
その作り直しにかかるコストがO(N)となってしまいます。
System.arraycopy(elementData, index, elementData, index + 1, s - index);
elementData[index] = element;
LinkedListの場合は、最初と最後の要素へのアクセスは要素を追加して元々存在した要素の前または後の参照に、追加した要素を追加するだけになります。そのためO(1)で追加ができます。
途中の要素の場合には、getメソッドと同様に指定した場所を探すまでにO(N/2)が必要となることからO(N/2)の計算量です。追加自体は指定した場所の前後の要素の参照を追加した要素に変更するだけです。
LinkedList.Node<E> pred = succ.prev;
LinkedList.Node<E> newNode = new LinkedList.Node(pred, e, succ);
succ.prev = newNode;
if (pred == null) {
this.first = newNode;
} else {
pred.next = newNode;
}
set
setはArrayList, LinkedListともにgetの計算量と同じになります。
ArrayListの場合は指定した箇所へのアクセスがO(1)で更新はアクセスした要素を上書きするだけなので、結果O(1)です。
LinkedListの場合はaddと同様に最初と最後の要素へのアクセスにO(1)、途中の要素へのアクセスはO(N/2)です。
remove
ArrayListの場合は、最後の要素の削除については削除するだけで良いので、O(1)になります。
それ以外の場所の要素を削除する場合は、削除した場所以降の要素を1つずつ前に詰める必要があり、配列の作り直しが必要になります。
その作り直しにかかるコストがO(N)となってしまいます。
以下が実際のコードです。最初のif文は最後の要素かどうかを判定しています。
if ((newSize = this.size - 1) > i) {
System.arraycopy(es, i + 1, es, i, newSize - i);
}
es[this.size = newSize] = null;
LinkedListの場合は、addとほぼ同じです。
最初・最後の要素の削除はO(1)です。
それ以外の場所の要素の削除は、指定した場所を探すまでにO(N/2)が必要となり、削除した後の処理としては、削除した要素の前後の要素の参照を更新するだけです。
LinkedList.Node<E> next = x.next;
LinkedList.Node<E> prev = x.prev;
if (prev == null) {
this.first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
this.last = prev;
} else {
next.prev = prev;
x.next = null;
}
List実装クラスの使い分け
以上を踏まえると、リストへの参照が多い場合にはArrayListを、ランダムな要素への追加・削除などが多い場合はLinkedListの方が使い方としては効率が良いということになります。
ちなみに最後の要素にしか追加がない場合にはArrayListの方が若干速いです。
ImmutableList
最後にJava9から導入されたImmutableListを紹介しておきます。
これまで紹介したArrayList, LinkedListともにadd,set,removeなどリストの中身を変更することが可能でした。
しかしImmutableListを利用するとそれらを利用することができなくなります。
参考となるコードをお見せします。
List<String> books = new ArrayList<>();
books.add("Java パフォーマンス");
books = Collections.unmodifiableList(books);
books.add("Effective Java"); // Exception in thread "main" java.lang.UnsupportedOperationException
immutableListにする方法としてはCollections.unmodifiableListを利用するものがあります。
これにより、addメソッドなどを利用してリストを更新しようとした際にUnsupportedOperationExceptionが出力するようになります。
その他、List.ofメソッドなども用意されているので、まだ利用していない方は是非利用してみてください。
Set
Setは重複した要素を持たないコレクションになります。
また、Listでは追加した順番を保持していましたが、Setにおいては追加した順番は持っておりません。
代表的なSetを継承したクラスは以下になります。
- HashSet
- TreeSet
- LinkedHashSet
Setの各クラスは内部でMapを移譲して利用しているため、具体的な実装はMapに依存しています。
そのため具体的なロジックはMapにて説明としてざっくりの違いだけを記載します。
HashSet
ハッシュテーブルを利用した重複なし配列になります。
実装としてはHashMapを利用しています。
順序付けはありません。
ハッシュテーブルを利用しているため、アクセスは高速で基本的にはO(1)でのアクセスが可能です。
イメージ図
TreeSet
キーを利用して常にソートされた状態のまま保持しています。
実装はTreeMapを利用しており、中では赤黒木というアルゴリズムで行なっています。
HashSetと比較すると若干遅くO(logN)となります。
イメージ図
LinkedHashSet
基本的にはHashSetと同じですが、こちらはListのように挿入した順序を保持しています。
実装はLinkedHashMapを利用しています。
中身としては、ハッシュテーブルを持ちつつ、各Entityでリンクさせるイメージになります。
イメージ図
Queue
通常はFIFO(先入れ先出し)で要素の順序付けを行うコレクションになります。
Queue<String> books = new ArrayBlockingQueue<>(2);
books.offer("Javaパフォーマンス");
books.offer("みんなのJava");
System.out.println(books.poll()); // Javaパフォーマンス
System.out.println(books.poll()); // みんなのJava
代表的なクラスにはPriorityQueueがあります。
PriorityQueue
QueueはFIFOと記載しましたが、PriorityQueueの場合は事前順序付けによって並び替えられたキューになります。
Queue<Integer> numbers = new PriorityQueue<>();
numbers.offer(5);
numbers.offer(4);
numbers.offer(6);
System.out.println(numbers.poll()); // 4
System.out.println(numbers.poll()); // 5
上記のコードでは、5, 4, 6の順番でキューに格納しましたが、pollで返却される値は 4, 5の順番になります。
つまり小さい値が先頭に並び替えられていることがわかります。
PriorityQueueは二分ヒープで実現しています。
計算量は、offer・pollともにO(logN)になります。
内部はこんなイメージになっています。
Queue<Integer> numbers = new PriorityQueue<>();
numbers.offer(5);
numbers.offer(4);
numbers.offer(6);
numbers.offer(3);
numbers.offer(4);
Deque
配列の先頭・末尾双方から要素の挿入・削除をサポートする線形コレクションです。
代表的なクラスにはArrayDequeがあります。
ArrayDeque
ArrayDequeは先頭・末尾双方から要素の追加・削除が可能です。
Deque<String> books = new ArrayDeque<>();
books.offer("Java パフォーマンス");
books.offerFirst("みんなのJava");
books.offerLast("Effective Java");
System.out.println(books.pollFirst()); // みんなのJava
System.out.println(books.pollLast()); // Effective Java
Map
Mapはキーを値にマッピングするオブジェクトになります。
Mapでは同一のキーは登録できず、またキーには1つの値しかマッピングできません。
| key | value |
|---|---|
| Taro | 25 |
| Hanako | 20 |
| Yamao | 30 |
名前をキーに持ち、値に年齢を持つMapのイメージ
Mapの代表的なクラスは以下になります。
- HashMap
- TreeMap
- LinkedHashMap
HashMap
HashSetでの説明と同様ですが、ハッシュテーブルを利用したMapになります。
HashSetで記載したハッシュテーブルについて少しだけ補足すると、ハッシュ値の衝突が起こり得ます。
ハッシュ値が衝突すると、最初に保持したハッシュ値の後続の要素として要素をリンクさせる仕組みとなっています。
衝突したハッシュ値のデータを取得する際には、同じハッシュ値かつ同じキーのものを取得するため、取り間違えることはありません。
TreeMap
TreeSetでの説明と同様になりますが、キーで並び替えされた状態で保持します。
Map<Integer, String> treeMap = new TreeMap<>();
treeMap.put(25, "Taro");
treeMap.put(20, "Hanako");
treeMap.put(30, "Yamao");
treeMap.entrySet().forEach(entry -> System.out.println(entry.getKey() + ":" + entry.getValue()));
// 20:Hanako
// 25:Taro
// 30:Yamao
LinkedHashMap
LinkedHashSetの説明と同様になります。
挿入した要素がそれぞれリンクされ、順番の保持が可能になります。
以下のようにforEachで値を取得するとputした順番に値が返却されることがわかります。
Map<Integer, String> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put(25, "Taro");
linkedHashMap.put(20, "Hanako");
linkedHashMap.put(30, "Yamao");
linkedHashMap.entrySet().forEach(entry -> System.out.println(entry.getKey() + ":" + entry.getValue()));
Discussion