page13(update:2018/01/09)

 昔から良く研究されている「データ構造とアルゴリズム」ですが、いざ使おうとすると何かと面倒でした。しかし、javaのクラスライブラリーとして用意されたCollectionFramework用いると、簡単に使えてしまいます。

 Collections Frameworkではデータ構造の操作方法をインターフェイスで抽象的に定義し、データを格納する具体的クラスは、これを実装して作られています。これはクラスの継承やインターフェイスの実装機能を上手く使った良い例です。さらにjdk1.5からは総称（generics）と呼ばれる機能の実現により、使いやすく安全なデータ構造となっています。

※Ｃ言語でデータ構造を実現したライブラリーを作ると、インターフェイスの実装やクラスの継承機能が無いので、実装内容まで知らないと使えないものになります。

Collections Frameworkには、データ構造を実装した便利なクラスとしてVectorやHashtableが用意されています。この二つは利用することも多いので具体的な説明を最後に行っています。

目次

• 13.1　Collections Framework
  • 1)Collectionインタフェース
  • ２）インタフェースの拡張
    Set、List、および SortedSet
  • ３）コレクションの反復子　Iterator
  • 4）実装クラス
• 13.2  Map
• 13.3　java.util.Vector
• 13.4　総称：generics　（ｊｄｋ1.5からの機能）
• 13.5  java.util.Hashtable<K,V>
• 13.6　並べ替え

［目次 ］

13.1　Collections Framework

データ構造は可能な操作で分類することが出来ます。javaでは可能な操作をインターフェースとして定義できます。実際、Collection Frameworkはデータ構造をインターフェースの階層 で定義しています。

• Collection(Objectを格納する入れ物)
  • List リスト(配列のように1つめ２つめといった一列に並んだ順序付のコレクション)
  • Queue キュー
    • Deque ﾃﾞｯｸ 待ち行列など
  • Set 集合（要素の重複が無い）
  • SortedSet 要素が順番付されている（たとえば大きい順や小さい順） 

これを実装する形で具体的なクラスは用意されているので、目的に合う操作が可能なインターフェースを見つけ、それを実装した具体的なクラスを選んで利用する ことになります。　

Collectionは既定値ではObjeｃｔのインスタンスを格納する入れ物です。全てのクラスはObjeｃｔを継承しているので、全てのインスタンスがCollectionに格納できます。基本データ型の値についてもラッパークラスを利用すれば格納できます。

しかし、何でも入るのは危険です。そこで、総称機能を利用して格納するインスタンスのクラスを限定できるようになりました。総称を使うと、格納するインスタンスがチェックできるだけでなく、取り出すときも総称で指定したインスタンス型として取り出せます。

1)Collectionインタフェース

オブジェクトを格納する入れ物。要素数の取得、個々の要素の出し入れ、纏まった出し入れ等が行えます。主なメソッドは以下の通り。

●コレクションの要素数
   int size()コレクションの要素数を返します。
   boolean isEmpty()コレクションに要素がない場合に true を返します。  
  　
  
●１つの要素の追加、検索と削除
  　boolean add(Object o)指定された要素を格納
  　boolean contains(Object o)コレクションに指定された要素がある場合に true を返します。
  　boolean remove(Object o)指定されたインスタンスがこのコレクション内にある場合に1個削除
  　void clear()すべての要素を削除します

●入れ物単位での要素の追加、検索と削除　※異な型の入れ物の間でもできるのが便利
  　boolean addAll(Collection c)指定されたコレクションのすべての要素を追加
  　boolean containsAll(Collection c)このコレクション内に、指定されたコレクションのすべての要素がある場合に true を返します。
  　boolean removeAll(Collection c)指定されたコレクションに格納されているすべての要素を削除
  　boolean retainAll(Collection c)指定されたコレクションに格納されている要素だけを保持  
  
●要素の取り出し
  　Object[] toArray()コレクションのすべての要素が格納されている配列を返します。
  　Iterator iterator()コレクションの要素の反復子を返します。

２）Collectionを継承したインタフェース

List、リスト　

順序付のコレクションで、順番を指定してデータにアクセスするメソッドが追加されます

void	add(int index, Object element)指定インデックスに要素を挿入
Object	get(int index)指定インデックスの要素を返す
Object	remove(int index) 指定インデックスの要素を削除
Object	set(int index, Object element) 指定インデックスの要素を置き換
void    sort(Comparator c)　並べ替え

〇後半で説明するVectorなどで実装されています

Queue、

キュー。LIFO の　所謂スタック

例外を投げるメソッド
boolean add(Object o)指要素をこのキューに挿入
Object	remove() キューの先頭を取得し、かつ削除
Object	element() キューの先頭を取得、削除はしない

戻り値で失敗を判定するメソッド（失敗することが通常動作の範囲内であるようなキューの実装で使う）
boolean offer(Object o) 可能な場合、指要素をこのキューに挿入。
Object	peek() キューの先頭を取得、削除しません。
Object	poll() キューの先頭を取得し、かつ削除。

〇LinkedListなどで実装されています

Deque 　

線形リストの始端と終端の両方で要素の挿入/削除が可能なキュー。
始端で追加し終端から取り出せば　FIFOを実現可能です。

※他にも様々なキューがあります

Set、

重複要素のないコレクション（e1とe2が同じコレクションの要素ならe1.equals(e2)は常に偽 ）で集合に相当します。

〇HashSetなどで実装されています

SortedSet　

要素が「自然順序付け」 されて格納されたコレクションで関連するメソッドが追加されます。

Comparator comparator() Sorteに関連したコンパレータを返します
Object	first()ソートセット内に現在ある最初 (下端) の要素を返します
Object	last()現在ある最後 (上端) の要素を返します

//部分 SortedSetの取り出し
SortedSet headSet(Object to)to より小さい要素を持つ部分を返します
SortedSet subSet(Object from, Object to)from (含む) から to(含まない) までの要素範囲を返します
SortedSet tailSet(Object from)from 以上の要素を持つ部分を返します。

〇TreeSetなどで実装されています

３）コレクションの反復子　Iterator

これはインターフェイスですがコレクションから戻されるIteratorはこれを実装した具体的なオブジェクトです

boolean hasNext()次の要素がある場合に真を返す
Object next()次の要素を返す。。
void remove()基になるコレクションから、反復子のnext()で返された直前の要素を削除

Collectionを実装する全てのクラスでこの反復子を利用して全要素を順番に参照する操作が行えます

import java.util.Vector;
import java.util.Iterator;

public class TestVector
{ 
	static public void main(String args[])
	{
		Vector v=new Vector();//VectorはCollectionを実装している
		v.addElement(new String("One"));
		v.addElement(new String("ニ"));
		v.addElement(new String("参"));
		//
		Iterator ite=v.iterator();
		while(ite.hasNext())
			System.out.println((ite.next()).toString());
	}
}

上記のプログラムのように削除を行わない全要素の順次参照の場合は拡張for文を使うほうが簡便です。

拡張for文

Collection collection;
....
for(Object obj:collection)
{
	...
}

前の例題を拡張for文を使って書き直すと次のようになります。

import java.util.Vector;

public class TestVector
{ 
	static public void main(String args[])
	{
		Vector v=new Vector();//VectorはCollectionを実装している
		v.addElement(new String("One"));
		v.addElement(new String("ニ"));
		v.addElement(new String("参"));
		//
		for(Object obj:v)
			System.out.println(obj.toString());
	}
}

このままではobjはObject型の変数なので使いにくい部分が残ります。

※後で説明する、総称の機能を使うことでObject型としてではなく具体的なクラスの参照変数を拡張for文で使うことができます。

import java.util.Vector;

public class TestVector
{ 
	static public void main(String args[])
	{
		Vector<String> v=new Vector<String>();//総称機能を使いStringのみを格納するVectorを用意
		v.addElement(new String("One"));
		v.addElement(new String("ニ"));
		v.addElement(new String("参"));
		//
		for(String str:v)//総称機能によりString型で要素が取り出せる
			System.out.println(str);
	}
}

４）実装クラス

フレームワークにはCollectionを継承した下記のようなインターフェイスで分類される。このインターフェースを実装することで具体的なデータ構造のクラスが用意されている。

イ ンターフェイスス	実 装クラス例
List	Vector,　ArrayList。LinkedList※
Queue	LinkedList※
Deque	LinkedList※
Set	HashSet、TreeSet
SortedSet	TreeSet

※LinkdListはList、Dequeを実装している。DequeはQueueをSortedSetはSetを継承していることにも注意

13.2 Mapインターフェース

Collectionとは異なり、キーとオブジェクトの組を格納するデータ構造でキーにより値を参照できる。英単語の文字列をキーとして日本語の説明文を値として持てば英和辞典のようなデータ構造を実現できるので，このデータ構造は辞書と呼ばれることも有る。

void clear()すべて削除します
boolean containsKey(Object key)指定のキーのマッピングを保持する場合に真を返します
boolean containsValue(Object value)マップが、指定された値に 1 つ以上のキーをマッピングしている場合に true を返します
Set entrySet()マップに含まれているマッピングのセットビューを返します
boolean equals(Object o)指定されたオブジェクトがこのマップと等しいかどうかを比較します
Object get(Object key)マップが指定のキーをマップする値を返します
int hashCode()マップのハッシュコード値を返します
boolean isEmpty()マップがキーと値のマッピングを保持しない場合に true を返します
Set keySet()マップに含まれているキーのセットビューを返します
Object put(Object key, Object value)指定された値と指定されたキーをこのマップに関連付けます
void putAll(Map t)指定されたマップのすべてのマッピングをこのマップにコピーします 
Object remove(Object key)このキーにマッピングがある場合に、そのマッピングをマップから削除します (任意のオペレーション)
int size()マップ内のキーと値のマッピングの数を返します
Collection values()マップに含まれている値のコレクションビューを返します。

実装クラス

１）Map　キーを値にマッピングするオブジェクト java.util.Hashtable　java.util.HashMap

２）キーが「自然順序付け」順になるSortedMapの実装には　　java.util.TreeMap　などがある

Comparator comparator()関連したコンパレータを返します
Object firstKey()現在ある最初 (下端) のキーを返します
Object lastKey()現在ある最後 (上端) のキーを返す
  
//部分 SortedMap を戻す
SortedMap headMap(Object to)to より小さいキーを持つ部分を返します
SortedMap subMap(Object fromKey, Object toKey)from (含む) 〜 to(含まない) のキー範囲部分を返す
SortedMap tailMap(Object fromKey)from以上のキーを持つ部分を返します。

13.3　java.util.Vector

　オブジェクトを一列に並べて格納するVectorクラス 。列の先頭、途中、末尾にオブジェクトを挿入したり削除したりが可能。配列の様に先頭からの順番でオブジェクトを参照できる。

●コンストラクタ
Vector()　既定値の容量で作成する
Vector(int)　指定された初期容量で作成する
※容量が不足すると自動的にメモリーを確保する。しかし、予め容量が既知ならば
容量を指定するほうがメモリ確保の手間が省け、処理がより高速に行える。
  
●追加と削除
void	addElement(Object)最後の要素として追加
void	insertElementAt(Object, int)　指定インデックスから要素を後ろにずらして、新しい要素を挿入する。
boolean	removeElement(Object)　先頭から検索し最初に見つけた要素を削除する。 
void	removeElementAt(int)　指定インデックスの要素を削除し、要素を前につめる。


●可変長配列の要素数
int	size()　要素数を返す。

●インデックスによる要素の参照
Object	elementAt(int)　指定インデックスの要素を返す。 
Object	firstElement()　最初の要素を返す。
Object	lastElement()　最後の要素を返す。
        
●検索
boolean	contains(Object)指定オブジェクトを含むときに真 
int	indexOf(Object)　オブジェクトを検索しインデックスを戻す

●並べ替え
void    sort(Comparator c)　並べ替え

用例

import java.util.Vector;
public class TestVector
{
	static public void main(String args[])
	{
 		Vector v=new Vector();
 		v.addElement(new String("One"));
 		v.addElement(new String("2"));
 		v.addElement(new String("参"));
 		//
 		for(int i=0;i<v.size();i++){
			/*戻り値はObject型なのでString型に変換して使う*/
			String string=(String)(v.elementAt(i));
			/*文字列を要素番号つきで書き出す*/
 			System.out.println("要素"+i+":"+string);
 		}
 	}
}
/* 実行結果
要素0:One
要素1:2
要素2:参
*/

［目次］

13.4　 総称：generics　（ｊｄｋ1.5からの機能）

クラスライブラリーで用意されたデータ構造は基本的にはObjectを格納するように作られているが、このままでは全てのオブジェクトが格納できるために、意図しないオブジェクトが格納されるかも しれない。また、取り出すデータもObjectクラスの型になるため、実際のオブジェクトメンバーを参照するには型変換（キャスト）が必要になる。このような不都合を解消するためにjdk1.5から総称と呼ばれる言語機能が追加された。

Vectorのクラス名もVector<T>のように変わっていて、Tは格納するオブジェクトのクラスを指定 する変数（型パラメータ）。この指定を行うことで格納するオブジェクトのクラスがコンパイル時点でチェックされる。さらに参照したり、取り出したりしたオブジェクトのクラス がTクラスになるようにコンパイルされる。

フレームワークのインターフェイスは総称を使えるように変更され，Collection<T>を継承したインターフェースは下記のようになった。

イ ンターフェイスス	実 装クラス例
List<T>	Vector<T>,　ArrayList<T> LinkedList<T>
Queue<T>	LinkedList<T>
Deque<T>	LinkedList<T>
Set<T>	HashSet<T>、TreeSet<T>
SortedSet<T>	TreeSet<T>

注意：総称で追加された<T>の情報はコンパイル時点でのみ使われ、作られるバイトコードには残らない。
　このため総称を使わない従来のプログラムと混在が可能。（旧javaVMが使える）

プログラムで格納するデータのクラスをTクラスと指定したVector<T>クラスのオブジェクトをnew Vector<T>（）の様に生成することが可能。ここで 型パラメータTの部分は具体的にはどんなクラス名でも対応する。 このときにメンバの引数や戻り値も対応するTクラスに変わるが、変化するのは以下のようなメソッド。

●追加と削除　TおよびTを継承したクラスのオブジェクトしか追加できない
void	addElement(T)
void	insertElementAt(T, int)　

●インデックスによる要素の参照　
T	elementAt(int)　 
T	firstElement()
T	lastElement()

たとえば文字列のみを格納するVector<String>であれば次に示す様にしてインスタンスを作る。要素の追加部分は引数がString型に、また参照部分は戻り値がString型のオブジェクトとなる。 上の用例を総称を使う形に変えてみる。

import java.util.Vector;
public class TestVector
{
	static public void main(String args[])
	{
 		Vector<String> v=new Vector<String>();
 		v.addElement(new String("One"));
 		v.addElement(new String("2"));
 		v.addElement(new String("参"));
 		//
 		for(int i=0;i<v.size();i++){
			/*戻り値はString型なのでキャストは不要*/
			String string=v.elementAt(i);
			/*文字列を要素番号つきで書き出す*/
 			System.out.println("要素"+i+":"+string);
 		}
 	}
}
/* 実行結果
要素0:One
要素1:2
要素2:参
*/

注意：ここで紹介する全てのクラスでｊｄｋ1.5（javaSE 5）から総称が利用できる。

※総称を使うクラスを自分で作ることも、もちろん可能。ここでは紹介しないが興味があるならjava5.0以降の参考資料を探してみよう。元になるのはhttp://java.sun.com/のドキュメントである。ここで言語仕様やチュートリアルを見るのがお勧め。これらの中には日本語に翻訳されて出版されているものも多いので本屋で探してみよう。

注意： 総称を使ったインスタンスの参照配列

総称と配列を組み合わせて使うときは注意が必要だ。

総称を使ったクラスVector<String>の参照配列を作りたい場合、以下のような配列生成の記述はエラーになってしまう。

Vector<String> list[ ] = new  Vector<String>[100];

「エラー: 汎用配列を作成します」と言われる。Vector<String>のような総称を使ったオブジェクトの参照配列は生成出来ないことが分かります。

しかし、次のように総称クラスを継承したクラスの配列なら生成できる。つまり、Vector<String>のような総称を使った名前には対応できないが、総称を使わない名前にしてくれれば対応できるということらしい。

    //継承したクラスを作っておく
   class VectorString extends Vector<String> { } 
........
   // VectorStringを参照する配列は作れてしかも Vector<String>の配列を参照する変数に代入可となる
   Vector<String> list[ ] = new  VectorString [100]; 
   // しかし、配列の要素にはVectorStringの参照しか代入できない。
   list[0]=new VectorString();
   // list[0]=new Vector<String>(); はlist[0]がVectorStringへの参照なのでクラス名が違うのでエラーになる
........
   // 要素の生成やクラス名の違いを除けば、配列の要素はVector<String>のオブジェクトと同様に使える。
   liat[0].add("ABCDE");
   System.out.println(list[0].elementAt(0));

トリッキーですが、有効なので知っておいて損はないかも？

［目次］

13.5　java.util.Hashtable<K,V>

総称の話をしたので，ここからは総称を使ったプログラム例を用います

Mapインターフェイスを実装した代表的なクラスがHashtableです。　キー・オブジェクトの型をK，対応付けて保持するオブジェクトの型をVとする。

オブジェクトvalueの格納にはハッシュテーブルの手法が使われています。キーとするオブジェクトkeyのhashCode()メソッドが戻す値でハッシュしvalueを格納します。高速にオブジェクトを検索できるのが特徴です。

注意
１） キーはオブジェクトでななければいけない。
　　基本データ型の値はキーに使えない。この場合はラッパークラスを使うようにしましょう。javaSE5から自動で基本データ型と対応するラッパークラスの変換を行うオートボクシング（Autoboxing）と呼ばれる機能が使えます。

２） キーとなるオブジェクトはhashCode() と equals() メソッドを 正しく実装することが必要。
　　Stringや基本データ型のラッパークラスなどでは実装済みなので，これらはキーに使えます。

●コンストラクタ
 Hashtable<K,V>()デフォルトの容量でハッシュテーブルを作成する
 Hashtable<K,V>(int)指定された容量でハッシュテーブルを作成する
      
●要素の追加と削除<
 V put(K key, V obj)指定されたキーを使用して、ハッシュテーブルに指定された要素を入れる。
 V remove(K key)キーに対応する要素を削除する。
 void clear()ハッシュテーブルの要素を全部クリアする。
      
●要素数
 boolean isEmpty()テーブルが空の場合真を返す。
 int size()テーブルに格納されている要素の数を返す。
      
●検索
 boolean containsValue(V obj)オブジェクトがテーブルの要素である場合true  
 boolean containsKey(K key)指定されたキーがテーブルに含まれるとき真を戻す
 V get(K key)キーと関連づけられたオブジェクトの参照を取得する

用例

import java.util.Hashtable;
public class TestHashtable
{
	static public void main(String arg[])
	{
		Hashtable<String,String> table=new Hashtable<String,String>();
		table.put("890-0011","鹿児島市玉里団地（１丁目)");
		table.put("890-0022","鹿児島市小野町（その他）");
		table.put("890-0033","鹿児島市西別府町");
		//
		System.out.println("〒890-0011＝＞"+table.get("890-0011"));
		System.out.println("〒890-0022＝＞"+table.get("890-0022"));
		System.out.println("〒890-0033＝＞"+table.get("890-0033"));
	}
}

13.6　並べ替え

データ構造は単にデータを保持するだけでなく検索や並べ替えを容易に行えることも重要だ。前記のHashtableは検索を高速に行うために工夫されたデータ構造を実現している。しかし，データをあいうえお順などの順番に並べて保持する機能は持たない。

順序付きコレクションのインターフェイス はListで，そのメソッドには並べ替えを行うsortメソッドが用意されている。ただし，sortを呼ぶためには大小比較を行うComparatorインターフェイスを実装したオブジェクトを引数で渡すことで必要だ。

実行環境（ロケール）に合った文字列比較を行うオブジェクトは
Collator collator=Collator.getInstance();
で入手できるので，これを使って，プログラムの実行環境の値をキー順に書き出すプログラムを作ってみた。

例題　実行環境の値をキー順に書き出すSystemProperties.java

実行環境の情報はキーと値の文字列の組として取り出すことができる。
Properties properties=System.getProperties();
ここでPropertiesはHashtableを継承したキーと値がともに文字列のクラスです。

Propertiesにはキー順に値を取り出すメソッドはないので，Listを実装したVector<String>にキーの値だけを入れて，ソートを使うことにする。

ソート後のVectorから順番にキーを取り出し，propertiesからキーに対応する値を得て書き出す。

/*プログラムを実行している環境の情報取得*/
import java.util.Properties;//Hashtableを継承して文字列のkeyとvalueの対を保持するMapのクラス
import java.util.Vector;//リスト構造を具体化したクラスの一つ
import java.text.Collator;//Comparator実装した抽象クラス

public class SystemProperties
{
	static public void main(String arg[])
	{
		//プログラムを実行している環境の情報を取得
		Properties properties=System.getProperties();

		//propertiesのkeyセットを取り出してlistを作る
		Vector<String> list=new Vector<String>(properties.stringPropertyNames());

		//listのkeyの並びをソートする
		//地域に準拠した文字列比較を行うインスタンスを取得し
		Collator collator=Collator.getInstance();//具体化したクラスのインスタンスはクラスメソッドで取得
		list.sort(collator);//文字列を比較するインスタンスを渡してソート

		//ソート後のlistの順にkeyとvalueを書き出す
		System.out.println("------------------------------sort-----------------------------");
		for(String key: list){
			System.out.printf("%s=\"%s\"\n", key ,properties.get(key));
		}
		System.out.println("---------------------------------------------------------------");
	}
}