[雑談] 試験の役に立たないJava講座 (14)

ということで引き続きインプレス社の「徹底攻略Java SE 11 Silver問題集」の章立てに沿って、少し雑談していきたいと思います。

以前よりお話ししているとおり問題集の内容に沿ったものではなく抜けているところも多々ありますので、認定資格を取得しようというのであれば問題集を購入して、そちらをしっかり勉強してください。

こちらは章立てに沿って適当に書き散らかしているものですので、試験の役には立ちません。

今回は第9章APIについてですが、試験に出そうなAPIは書籍を見ていただくとして、コレクションについて今回は考えていこうかと思います。

Java Collections Framework

プログラムを書く上で関連するデータをひとつのまとまりとして扱うことがよくあります。

例えば従業員の氏名、従業員番号、就業日などを一つにまとめて従業員データとして扱うといった場合、Javaではオブジェクトで表現しています。

それとは別にすべての従業員の一覧のように同じ種類のデータをまとめて扱うといったこともよくあり、これにはリストや配列といったデータ構造がよく用いられます。

こういったデータ構造は頻繁に用いられるため、JavaではCollections Frameworkとしてよく用いられるデータ構造を汎用的に利用できるようにしています。

もちろん、リストなどのデータ構造はそれほど難しいものではないので、自分で作っても構わない、例えば簡単なリストであれば配列を使って容易に実装できますが、汎用的なものを提供することで、ありがちな失敗による不具合の発生を避ける、効率的なアルゴリズムによる性能改善を図るといったことが可能となるとの考えからJavaではCollections Frameworkを提供しています。

提供されるデータ構造

Collections Frameworkでは大きく以下のデータ構造が提供されています。

• 集合 (Set)
  重複のないオブジェクトの集まりを扱います。
• リスト (List)
  配列のようにインデクスでアクセスできるオブジェクトの集まりを扱います。
• マップ (Map)
  名前などのキーと、キーに対応するオブジェクトの組の集まりを扱います。
  マップは辞書、連想配列といった呼び方をされることがあります。

Collections Frameworkの構成

Collections Frameworkはデータ構造を扱うためのインタフェースと、いくつかの実装方法でインタフェースを実装したクラスで構成されています。

例えばリスト (List) であれば、リストを扱うためのjava.util.Listインタフェースが用意され、その実装クラスとしてリストを配列で実装したjava.util.ArrayListクラスと、双方向の連結リストで実装したjava.util.LinkedListクラスがあります。

後でも少し触れますが、これらのデータ構造を使用する際に外部にはインタフェースだけを見せることで後々実装を変更することを可能にしておくことが基本的な使い方になります。

集合 (Set)

集合 (Set) は重複のないオブジェクトの集まりです。

Setには以下のような操作が用意されています。

add: オブジェクトを追加する。

引数で与えられたオブジェクトがSetに存在していなければ、そのオブジェクトをSetに追加します。

引数で与えられたオブジェクトとSet内のオブジェクトが同じかどうかはequalsメソッドによって判定します。

このため、equalsメソッドを適切に実装していないとSet期待通りに動作しない場合があります。

remove: オブジェクトを削除する

引数で与えられたオブジェクトがSet内にあれば、それをSetから削除しtrueを返します。

引数で与えられたオブジェクトがSet内に存在していなくてもエラーにはならず、falseを返します。

なお、removeメソッドは実装必須ではないため、使用には注意が必要です。

contains: オブジェクトの有無を判定する

引数で指定されたオブジェクトがSet内にあればtrueを返し、なければfalseを返します。

iterator: イテレータを返す

Setに含まれるオブジェクトを逐次読み出すためのイテレータを取得します。

イテレータはSet内にあるすべてのオブジェクトを読み取ることができますが、その順序は原則として保証されません (順序保証が必要な場合はSequencedSetを使用してください)。

イテレータでの読み取りを行っている途中でSetに対するオブジェクトの追加、削除が発生するとイテレータはエラーになります (Setの実装クラスを自分で作成する場合にはこの点に注意が必要です)。

toArray: 配列を生成する

Setに含まれるすべてのオブジェクトを含む配列を生成します。

配列内のオブジェクトの順序は原則として保障されません (順序保証が必要な場合はSequencedSetを使用してください)。

isEmply: 空集合の判定

Set内にオブジェクトがない場合にtrueを返します。

of: Setの生成

スタティックメソッドofは引数で与えられたオブジェクトを含む変更不可能なSetを生成します。

例えばコンパイラのキーワードのようにシステムとして固定されたデータの集合を保持する場合などに使えると思います。

addメソッドのところでも触れましたが、Setはオブジェクトの同一性判定にオブジェクトのequalsメソッドを使用します。

equalsメソッドの実装が不適切な場合、Setは期待された動作を行わない可能性があります。

Setの実装クラス

Setは機能的にはシンプルですが、同じオブジェクトが登録済みかを短時間で判断しないと性能面に影響が出ますので、実装自体はかなり面倒なものになっています。

主要なSetの実装クラスとして以下のものが用意されています。

HashSet: ハッシュテーブルによる実装

オブジェクトを高速に探す手法として、ハッシュテーブルと呼ばれる技法があります。

ハッシュテーブルを使用してSetを実装したものがHashSetになります。

実際にはハッシュテーブルを実装したHashMapを使用して実装を行っています。

HashMapとハッシュテーブルについては後ほどマップのところで考えていきたいと思います。

TreeSet: 探索木による実装

ざっくりいうとオブジェクトをソートしておくことで高速にオブジェクトを検索できるようにしようという考え方で作られたSetです。

こちらもTreeMapを使用して実装しているので探索木についてはマップのところで調べていこうと思います。

EnumSet: 列挙型専用の実装

列挙型専用のSetなのでプログラミングの時点で設定できる値は確定してしまいますが、例えばオプション機能のオン・オフなどでは有効に使えそうです。

あえてSetを使わない

HashSetにしろTreeSetにしろ検索のためのデータ構造が必要で、検索にはそれなりの時間がかかります。

例えばソフトウエア全体で1個のオブジェクト群に対して1組のSetしか使わないことが明らかな場合にはSetを使用する代わりにオブジェクトにフラグを持ち、フラグのオンオフで判断するといった実装も可能です。

将来の拡張性なども考えて技術選択を行っていく必要があるでしょう。

リスト (List)

Listは配列のように先頭から何番目のデータという形でアクセスできるデータ構造です。

Listには以下のような操作が用意されています。

add: 要素の追加

引数で指定された位置、もしくはリストの最後にオブジェクトを追加・挿入します。追加・挿入された数だけリストが長くなります。

get: 要素の取得

引数で指定された位置のオブジェクトを読み取ります。取り出しではないので指定されたオブジェクトはリストから削除されることはありません。

set: 要素の設定

引数で指定された位置にオブジェクトを設定します。指定された位置の要素は書き換えられるのでリストのサイズは変わりません。

remove: 要素の削除

引数で指定された位置のオブジェクトをリストから削除します。削除したオブジェクトが戻り値として返され、リストは短くなります。

contains: 要素の探索

引数で指定された要素がオブジェクト内にある場合はtrueが返されます。

オブジェクトの比較にはequalsメソッドが使用されますので、equalsメソッドが適切に実装されている必要があります。

そのほかSet同様にiterator, isEmpty, toArray, ofなどの操作が用意されています。

Listの実装クラス

Listの主要な実装クラスには以下のものがあります。

ArrayList: 配列による実装

配列に要素数を管理する情報などを付加し、かつ配列のサイズを超えた場合にはより長い配列に切り替えるといった仕組みで可変長リストを実現する実装です。

配列が基礎になっているので、指定された位置のオブジェクトを読み取るのは容易ですが、リストの途中で要素の追加、削除が発生した場合には指定された位置以降の要素をすべて移動する必要があるので、特に長いリストに対する挿入・削除が発生するような用途にはあまり向いていません。

LinkedList: 連結リストによる実装

LinkedListは双方向リンクを使用した連結リストによる実装です。

連結リストは各要素が自分の前後の要素への参照を保持するもので、先頭要素から順次参照をたどっていくことでリストのすべての要素にアクセスすることができます。

リストへの要素の追加、削除は対象要素の前後の要素に設定されている参照を書き換えるだけでできるため、リストの途中への要素の追加削除が高速に実行できるという利点がありますが、インデクスに基づいた要素へのアクセスには要素を順にたどっていく必要があるため、ArrayListに比較して負荷がかかります。

配列とリスト

配列とリストの違いについて考えてみたいと思います。

配列とリストの両方ともオブジェクト列にインデクスでアクセスするという点では同じですが、いくつか重要な違いがありますので、そこを踏まえた選択が必要と思います。

まず、配列は固定長、配列を生成する時点でサイズを決めておく必要があり、サイズを後で変更することはできません。

このため、サイズが変化するオブジェクト列を扱う場合はリストを使用する方が容易になります。

リストは要素としてオブジェクトしか使用できませんが、プリミティブ型の配列を作ることができます。

Javaのボックス化の機能によりプリミティブ型データをリストで扱うことも面倒ではありませんが、プリミティブ型のデータと対応するオブジェクトとの間での相互変換が発生するため、期待する性能が出ない可能性があります。

こういった違いを踏まえて配列とリストのどちらを使うかを検討すべきと考えています。

リストの整列 (ソート)

Listインタフェースは整列のためのsortメソッドを用意しています。

sortメソッドは引数にリスト要素のオブジェクトを比較するためのメソッドcompareを持つComparatorインタフェースのオブジェクトを取り、リストの各要素に対してcompareメソッドを適用することで整列を行います。

よほど特殊な状況でなければリスト要素の整列にはこのメソッドを使用するのがいいと思います。

マップ (Map)

配列やリストはその先頭から順番に振られた整数値、インデクスで要素を指定しますが、マップは整数値の代わりに任意の型のオブジェクトを用いて要素を指定するものです。

例えば、名前付きの値を扱う場合に名前の文字列をインデクス (マップでは「キー」と呼びます) としてマップに登録することで値を名前で取り出すことができるようになります。

マップには以下のような操作が用意されています。

put: 値の登録

引数で渡したキーと値を組としてマップに登録します。

すでにキーと値がマップに登録されている場合には値が置き換えられます。

get: 値の取得

引数で与えられたキーに対応付けられている値を返します。

引数で指定されたキーが登録されていない場合にはnullが返されます。

containsKey: キーの登録有無

引数で指定されたキーが登録されているかを判定します。

キーが登録済みであればtrue、みとうろくであればfalseが返されます。

remove: 値の削除

引数で指定されたキーと対応する値をマップから削除します。

値の削除に成功した場合は削除した値を返し、キーが未登録の場合はnullを返します。

そのほかにも様々な操作が用意されています。

Mapの実装クラス

Mapの主要な実装クラスには以下のものがあります。

HashMap: ハッシュテーブルによる実装

キーの検索用にハッシュテーブルを使用した実装です。

キーとなるオブジェクトの値を要約した容量の小さい値をハッシュ値と呼んでいます。

Javaのすべてのオブジェクトはint型のハッシュ値を持っており、各オブジェクトのhashCodeメソッドにて取得することができます。

実際にはクラスを実装する際に適切な要約値を返すhashCodeメソッドを実装することが仕様として期待されています。

ハッシュ値として要求されているのはequalsメソッドがtrueとなるオブジェクトはhashCodeが同じハッシュ値を返すことだけですが、期待されているのはハッシュ値が偏りなくばらけることです。

ハッシュテーブルはハッシュ値 (のサブセット) でインデクスされる配列またはリストを用意することで、キーの検索時にハッシュ値による絞り込みを行えるようにしています。

ハッシュ値に偏りがある場合には絞り込みの効果が低くなるため、キーの検索に時間がかかることになります。

HashMapはハッシュテーブルでキー検索の効率化を図ったマップの実装で、多くの場合効率的に動作します。

TreeMap: 探索木による実装

キーをソートしておくことで高速にキーを検索できるようにしようという考え方で作られたマップです。

探索木にはいくつかの種類がありますが、ここでは最も簡単な平衡二分木を例に説明していきます。

平衡二分木の各要素は値と2個の子要素への参照を保持しています。

そして一方は自分より小さい値を持つ要素を参照し、他方は自分より大きい値を持つ要素を参照するようにします。

このような要素を積み上げていくと一番上に1個の要素があり、その下に2個ずつ子要素がぶら下がるピラミッド型のデータ構造が出来上がります。

これが二分木です。

二分木での検索は検索対象の値と最上位の要素の値を比較し、一致したら検索終了、小さければ一方の参照をたどって次の要素を調べ、大きければ他方の参照をたどって次の要素を調べるというように順次要素参照をたどって検査を行っていきます。

そして最後まで一致する値を持った要素が見つからなかった場合には検索失敗となります。

二分木はそれぞれの要素の左右にほぼ同じ数の子要素がぶら下がってきれいな三角形となっている場合には効率的な検索ができますが、どちらかに偏ってしまった場合には検索効率が落ちてしまいます。

二分木への値の登録・削除で工夫を行って左右にバランスよく要素を配置するようにしたものが平衡二分木で、効率よい値の検索が可能となります。

TreeMapは平衡二分木のような値の検索方法をキーの検索に使用しているので、キーには値の大小を判定できるオブジェクトを使用する必要があります。

具体的にはComparableインタフェースを実装したオブジェクトをキーとするか、キーのオブジェクトを比較するためのComparatorオブジェクトが用意されていることが必要となります。

キーとして順序がつけられないオブジェクトを使用する場合はHashMap一択となりますが、順序付けが可能なオブジェクトを使用する場合にはHashMapとTreeMapのどちらも利用が可能ですので、使用するキーの値の特性に合わせて選択する、あるいはテストや運用の結果に応じて差し替えを行えるようにするといった対応がいいかもしれません。

以上、Set、List、MapというCollections Frameworkでよく使われるAPIについてみてきました。

関連としてイテレータとストリームについて後ほど見ていきたいと思います。