コレクションと配列

配列はJavaの言語仕様で規定された機能であり、Javaの最初のバージョンから存在する機能。一方、コレクションはJavaのバージョン1.2から導入された標準ライブラリ。

コレクションフレームワークの種類

（インタフェース）リスト
　具象クラス　→　ArrayList,LinkedList

（インタフェース）マップ
　具象クラス　→　HashMap,TreeMap,LinkedHashMap

（インタフェース）セット
　具象クラス　→　HashSet,TreeSet,LinkedHashSet

（インタフェース）デック
　具象クラス　→　ArrayDeque,LinkedDeque

コレクション型オブジェクトの生成

コレクションのインタフェース型＜要素の型＞ 変数 = new コレクションのインタフェースを実装した具象クラス<>(コンストラクタの引数);

例）
List slist = new ArrayList<>();
//List slist = new ArrayList(); // Java7以前の書き方

要素の型に、基本型(char,intなど)は指摘できない。ラッパークラス(String,Integerなど)を使う。

リスト(java.util.List)

抽象的な意味は、順番通りに並んだ集まり。主な具象クラスとしてArrayListとLinkedListがある。

ArrayList

インデックスを指定して各要素にアクセスする処理は理論上、どの要素へのアクセスも一定速度で動作する。
一方、挿入や削除は、処理をした一から後ろのすべての要素の移動が必要になるため、処理速度が劣化する。
要素の交換であれば、他の要素移動は必要ないため、速い。
末尾への要素追加、削除は基本的には高速だが、確保したメモリ領域を超える場合、新たにメモリ領域確保のため遅くなることがある。
あらかじめ、上限がわかっていれば、初期サイズをコンストラクタで指定して、再確保によるタイムロスを防ぐことができる。

良い点
インデックスを指定して要素を読み出す速度が速い。（get処理）
インデックスを指定して要素を書き換える速度が速い。（set処理）
先頭から順にすべての要素を羅列する速度が速い。（リニアサーチ）

悪い点
先頭に近いほど、要素の挿入が遅くなる。(add処理)
先頭に近いほど、要素の削除が遅くなる。ただし、末尾の削除は速い。(remove処理)
条件に合致した要素の検索はあまり早くない。ただし、工夫により早くすることも可能。（contains,indexOf,lastIndexOf）

LinkedList

インデックスを指定して要素にアクセスする場合、先頭の要素からひとつづつ参照先のリンクをたどる。
つまりn番目の要素にアクセスする場合、n個のリンクをたどる処理が必要になる。
要素数が多いと、リンクをたどる回数が増えるため効率が落ちる。
先頭から、もしくは最後尾からたどるため、真ん中へのアクセスが最も遅い。
一方、要素の追加、削除は、対象となる要素の前後のリンクを書き換えるだけのため、高速に動作する。
（ただし、追加、削除処理の前に前述のリンクをたどる処理は必要であり、そちらのほうが処理速度への影響が大きい）
要素ごとにメモリ確保がされるため、ArrayListのようなメモリ再確保による遅延は発生しない。

良い点
要素の挿入が速い。(add処理)
要素の削除が速い。(remove処理)

悪い点
インデックスを指定して要素を読み出す速度が遅い。（get処理）
インデックスを指定して要素を書き換える速度が遅い。（set処理）
条件に合致した要素の検索はあまり早くない。（contains,indexOf,lastIndexOf）

まとめ
要素の読み込みが中心の場合は、ArrayListの方が効率的。
要素の挿入や削除の頻度が高い場合は、LinkedListの方が効率的。
要素の書き換え処理が多い場合は、ArrayListの方が効率的。

マップ(java.util.Map)

マップの抽象的な意味は、キーと値のペアの集まりを管理するもの。キーと値のペアが要素となる。
具象クラスとしては、HashMap,TreeMap,LinkedHashMapがある。

HashMap

HashMapは内部にハッシュ表と呼ばれる配列を確保する。初期サイズはコンストラクタで指定する。
キーと値のペアをHashMapにputすると、内部でキーをハッシュ関数に通す。得られた値をハッシュ表のインデックスとし、その位置にキーと値のペアを格納する。
getする場合も、検索キーをハッシュ関数に通し、得られた値をハッシュ表のインデックスとして、配列から要素であるキーと値のペアを取り出す。要素がない場合はnullとなる。

ハッシュ関数は、入力値を一定の決まった範囲の数値に変換する関数。同じ入力に対して、常に同じ出力を返す。異なる入力に対して、同じ出力になることがあり得る。（ハッシュ関数の衝突/コンフリクト）衝突が生きると、HashMapの内部にリンクリストもしくはバランス木を作成する。getする際には、このリンクリスト、バランス木をたどって、キーの完全一致で値を求めるため、処理が重くなる。コンフリクトによる処理速度の劣化を防ぐため、HashMapは自動的にハッシュ表のサイズ拡張を行うが、すべての既存要素のハッシュ関数の再計算を行うため、処理は軽くはないので、最初に適切なハッシュ表のサイズを指定すること。

LinkedHashMap

LinkedHashMapはHashMapを拡張継承したクラスで、ハッシュ表に加えてLinkedListと同じリストを内部に保持する。
HashMapですべての要素を列挙する場合、順序はハッシュ関数に依存しているため、利用者側から見れば規則性がない。
意味のある順序での要素列挙が必要な場合、LinkedHashMap、TreeMapを使用する。
LinkedHashMapで得られる順序は、追加した順序もしくは、アクセスした順序の２種類。

TreeMap

ソートの基準（数値の大小順、文字列の辞書順）などの順番が欲しい場合に使用する。
そのため、キーは比較可能なものでなければならない。
JavaのTreeMapが採用しているアルゴリズムは赤黒木(red-black tree)と呼ばれるツリー構造。２分探索木(binary serch tree)の一種。
Mapの主な利用シーンとしては要素の検索であり、ツリーの検索処理の速さは、２分探索木の深さに反比例する。深いほど、比較する要素が増える。

Java6以降、TreeMapはNavigableMapインタフェースを実装している。これにより、通常のマップはキーの完全一致でしか検索できないが、NavigableMapにより近いキーでの検索が可能になっている。

まとめ

順序が不要な場合、追加や検索が速いHashMapが適している。
追加した順序やアクセス順が必要な場合、LinkedHashMapが適している。
任意のソート基準が必要な場合、TreeMapが適している。

セット

数学の「集合」の概念をプログラミングに持ち込んだもので、重複のない要素の集まり。リストでは順序で並んだ集まりで重複する要素を持つが、セットでは、順序は無関係で要素は重複しない。
具象クラスは、HashSet,TreeSet,LinkedHashSetがある。

マップのキーと動作は同じ。要素の持ち方がキーと値のペアでなく、キー＝値になった形になる。

スタック、キュー、デック

スタックは最新要素から順に取り出しを行う処理。
キューは最古要素から順に取り出しを行う処理。
デックはそれらの両方を行う。Dequeという名前は、「double ended queue」両端キューという意味。