JAvaのデータ構造整理
線形テーブル、チェーンテーブル、ハッシュテーブルはよく使われるデータ構造であり、Java開発を行う際、JDKは基本的なデータ構造を実現するために一連の対応するクラスを提供してくれた.これらのクラスはjava.utilパッケージにあります.
*Collectionインタフェース
Collectionは最も基本的な集合インタフェースであり、1つのCollectionはObjectのセット、すなわちCollectionの要素(Elements)を表す.いくつかのCollectionは同じ要素を許可し、他のいくつかはできません.いくつかはソートできますが、他のいくつかはできません.Java SDKはCollectionから直接継承されるクラスを提供しません.Java SDKが提供するクラスは、リストやSetなどのCollectionから継承される「サブインタフェース」です.
Collectionインタフェースを実装するすべてのクラスには、2つの標準的なコンストラクション関数が必要です.パラメータのないコンストラクション関数は、空のCollectionを作成するために使用され、入力されたCollectionと同じ要素を持つ新しいCollectionを作成するために使用されるCollectionパラメータのコンストラクション関数があります.次のコンストラクション関数では、ユーザーがCollectionをコピーできます.
Collectionの各要素を巡回するにはどうすればいいですか?Collectionの実際のタイプにかかわらず、Collectionの各要素に1つずつアクセスできる反復子を返すiterator()メソッドがサポートされています.典型的な使い方は以下の通りです.
Iterator it = collection.iterator();//反復子while(it.hasNext(){Object obj=it.next();//次の要素を取得
}
Collectionインタフェースから派生した2つのインタフェースはListとSetである.
*Listインタフェース
Listは秩序化されたCollectionであり、このインタフェースを使用して各要素が挿入される位置を正確に制御することができる.ユーザは、Javaの配列に類似したリスト内の要素にアクセスするために、リスト内の要素(リスト内の要素の位置)を使用することができる.
リストは、後述するSetとは異なり、同じ要素を許可する.
Collectionインタフェースに必要なiterator()メソッドに加えて、ListはlistIterator()メソッドを提供し、ListIteratorインタフェースを返します.標準的なIteratorインタフェースに比べて、ListIteratorにはadd()などのメソッドが多く、追加、削除、設定要素を許可し、前後に遍歴することができます.
Listインタフェースを実装する一般的なクラスはLinkedList,ArrayList,Vector,Stackである.
**LinkedListクラス
LinkedListはListインタフェースを実現しnull要素を許可する.さらにLinkedListは、LinkedListの先頭または末尾に追加のget、remove、insertメソッドを提供する.これらの操作により、LinkedListはスタック、キュー、または双方向キューとして使用することができる.
LinkedListには同期方法がありません.複数のスレッドが同時にリストにアクセスする場合は、アクセス同期を自分で実現する必要があります.1つの解決策は、リストの作成時に同期リストを作成することである.
List list = Collections.synchronizedList(new LinkedList(...));
**ArrayListクラス
ArrayListは可変サイズの配列を実現している.nullを含むすべての要素を許可します.ArrayListは同期していません.
size,isEmpty,get,setメソッドの実行時間は定数です.しかしadd法のオーバーヘッドは割り当てられた定数であり,n個の要素を追加するにはO(n)の時間が必要である.他のメソッドの実行時間は線形です.
各ArrayListインスタンスには、要素を格納する配列のサイズである容量(Capacity)があります.この容量は、新しい要素を追加するにつれて自動的に増加することができるが、成長アルゴリズムは定義されていない.大量の要素を挿入する必要がある場合、挿入前にensureCapacityメソッドを呼び出してArrayListの容量を増やして挿入効率を向上させることができる.
LinkedListと同様にArrayListも非同期である(unsynchronized).
Vectorクラス
VectorはArrayListによく似ていますが、Vectorは同期しています.Vectorによって作成されたIteratorは、ArrayListによって作成されたIteratorと同じインタフェースであるが、Vectorが同期しているため、1つのIteratorが作成され使用されている場合、別のスレッドがVectorの状態を変更し(例えば、いくつかの要素を追加または削除した場合)、Iteratorのメソッドを呼び出すとConcurrentModificationExceptionが投げ出され、そのため、この例外をキャプチャする必要があります.
Stackクラス
StackはVectorから継承され、後進先出のスタックを実現します.Stackは、5つの追加の方法を提供し、Vectorをスタックとして使用することができる.基本的なpushとpop法、peek法はスタックトップの要素を得、empty法はスタックが空であるかどうかをテストし、search法はスタック内の要素の位置を検出する.Stackが作成されたばかりで空きスタックです.
Setインタフェース
Setは、重複する要素を含まないCollectionである.すなわち、任意の2つの要素e 1およびe 2にe 1.equals(e 2)=falseがあり、Setにはnull要素が最大1つある.
明らかに、Setのコンストラクション関数には、入力されたCollectionパラメータに重複する要素を含めることができない制約があります.
注意:可変オブジェクト(Mutable Object)の操作に注意してください.Setの可変要素が自身の状態を変更した場合、Object.equals(Object)=trueになると、いくつかの問題が発生します.
Mapインタフェース
MapはCollectionインタフェースを継承していません.Mapはkeyからvalueへのマッピングを提供します.1つのMapに同じキーを含めることはできません.各キーには1つのvalueしかマッピングできません.Mapインタフェースは、3つのセットのビューを提供し、Mapの内容は、keyセット、valueセット、またはkey-valueマッピングのセットとして使用することができる.
主な方法:
boolean equals(Object o)比較対象
オブジェクトを削除
put(Object key,Object value)keyとvalueを追加
Hashtableクラス
HashtableはMapインタフェースを継承し、key-valueマッピングのハッシュテーブルを実現する.空でないオブジェクトはkeyまたはvalueとして使用できます.
追加データはput(key,value)、取り出しデータはget(key)を使用し、この2つの基本動作の時間オーバーヘッドは定数である.
Hashtableはinitial capacityとload factorの2つのパラメータで性能を調整します.通常、デフォルトのload factor 0.75は、時間と空間の等化をより良く実現する.load factorを大きくすると、スペースを節約できますが、対応する検索時間が大きくなり、getやputのような操作に影響します.Hashtableを使用する簡単な例は、1,2,3をHashtableに配置し、keyはそれぞれ「one」、「two」、「three」である.
keyとしてのオブジェクトは、そのハッシュ関数を計算することによって対応するvalueの位置を決定するので、keyとしてのオブジェクトはhashCodeおよびequalsメソッドを実装する必要があります.hashCodeメソッドとequalsメソッドはルートクラスObjectから継承されます.カスタムクラスをkeyとして使用する場合は、ハッシュ関数の定義に従って、obj 1.equals(obj 2)=trueの2つのオブジェクトが同じである場合、hashCodeは同じである必要がありますが、2つのオブジェクトが異なる場合、hashCodeは必ずしも異なるとは限りません.2つの異なるオブジェクトのhashCodeが同じである場合、この現象は衝突と呼ばれ,衝突はハッシュテーブルを操作する時間のオーバーヘッドを増大させるため,ハッシュテーブルの操作を速めるためにできるだけ良いhashCode()メソッドを定義することができる.
同じオブジェクトに異なるhashCodeがある場合、ハッシュ・テーブルの操作で予想外の結果が得られます(期待されるgetメソッドはnullを返します).このような問題を回避するには、equalsメソッドとhashCodeメソッドを同時に複写し、そのうちの1つだけ書かないでください.
Hashtableは同期しています.
HashMapクラス
HashMapはHashtableと同様であり、HashMapが非同期でありnull、すなわちnull valueおよびnull keyを許容する点が異なる.ただし、HashMapをCollectionと見なす場合(values()メソッドはCollectionを返します)、反復サブオペレーション時間のオーバーヘッドはHashMapの容量に比例します.したがって,反復動作の性能がかなり重要であれば,HashMapの初期化容量を高すぎる,あるいはload factorが低すぎるようにしてはならない.
WeakHashMapクラス
WeakHashMapは、keyに対して「弱い参照」を実行する改良されたHashMapであり、1つのkeyが外部に参照されなくなった場合、そのkeyはGCで回収することができる.
まとめ
スタック,キューなどの操作に関しては,リストを用いること,要素の迅速な挿入,削除が必要な場合はLinkedList,要素への迅速なランダムアクセスが必要な場合はArrayListを用いることを考慮すべきである.プログラムが単一スレッド環境にある場合、または1つのスレッドでのみアクセスされる場合、非同期クラスを考慮すると効率が高く、複数のスレッドが1つのクラスを同時に操作できる場合は、同期クラスを使用する必要があります.ハッシュ・テーブルの操作に特に注意し、keyのオブジェクトとしてequalsメソッドとhashCodeメソッドを正しく複写します.実際のタイプではなくインタフェースをできるだけ返します.例えば、ArrayListではなくListを返します.これにより、後でArrayListをLinkedListに変更する必要がある場合、クライアントコードは変更されません.これが抽象プログラミングです.
Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│ └Stack
└Set
Map
├Hashtable
├HashMap
└WeakHashMap
*Collectionインタフェース
Collectionは最も基本的な集合インタフェースであり、1つのCollectionはObjectのセット、すなわちCollectionの要素(Elements)を表す.いくつかのCollectionは同じ要素を許可し、他のいくつかはできません.いくつかはソートできますが、他のいくつかはできません.Java SDKはCollectionから直接継承されるクラスを提供しません.Java SDKが提供するクラスは、リストやSetなどのCollectionから継承される「サブインタフェース」です.
Collectionインタフェースを実装するすべてのクラスには、2つの標準的なコンストラクション関数が必要です.パラメータのないコンストラクション関数は、空のCollectionを作成するために使用され、入力されたCollectionと同じ要素を持つ新しいCollectionを作成するために使用されるCollectionパラメータのコンストラクション関数があります.次のコンストラクション関数では、ユーザーがCollectionをコピーできます.
Collectionの各要素を巡回するにはどうすればいいですか?Collectionの実際のタイプにかかわらず、Collectionの各要素に1つずつアクセスできる反復子を返すiterator()メソッドがサポートされています.典型的な使い方は以下の通りです.
Iterator it = collection.iterator();//反復子while(it.hasNext(){Object obj=it.next();//次の要素を取得
}
Collectionインタフェースから派生した2つのインタフェースはListとSetである.
:
boolean add(Object o)
boolean remove(Object o)
int size()
boolean contains(Object o)
boolean isEmpty()
Iterator iterator()
boolean containsAll(Collection c) c
boolean addAll(Collection c) c
void clear()
void removeAll(Collection c) c
void retainAll(Collection c) c
*Listインタフェース
Listは秩序化されたCollectionであり、このインタフェースを使用して各要素が挿入される位置を正確に制御することができる.ユーザは、Javaの配列に類似したリスト内の要素にアクセスするために、リスト内の要素(リスト内の要素の位置)を使用することができる.
リストは、後述するSetとは異なり、同じ要素を許可する.
Collectionインタフェースに必要なiterator()メソッドに加えて、ListはlistIterator()メソッドを提供し、ListIteratorインタフェースを返します.標準的なIteratorインタフェースに比べて、ListIteratorにはadd()などのメソッドが多く、追加、削除、設定要素を許可し、前後に遍歴することができます.
Listインタフェースを実装する一般的なクラスはLinkedList,ArrayList,Vector,Stackである.
:
void add(int index,Object element)
boolean addAll(int index,Collection c) c
Object get(int index) List
int indexOf(Object o) o .
Object removeint(int index)
Object set(int index,Object element) element index ,
**LinkedListクラス
LinkedListはListインタフェースを実現しnull要素を許可する.さらにLinkedListは、LinkedListの先頭または末尾に追加のget、remove、insertメソッドを提供する.これらの操作により、LinkedListはスタック、キュー、または双方向キューとして使用することができる.
LinkedListには同期方法がありません.複数のスレッドが同時にリストにアクセスする場合は、アクセス同期を自分で実現する必要があります.1つの解決策は、リストの作成時に同期リストを作成することである.
List list = Collections.synchronizedList(new LinkedList(...));
**ArrayListクラス
ArrayListは可変サイズの配列を実現している.nullを含むすべての要素を許可します.ArrayListは同期していません.
size,isEmpty,get,setメソッドの実行時間は定数です.しかしadd法のオーバーヘッドは割り当てられた定数であり,n個の要素を追加するにはO(n)の時間が必要である.他のメソッドの実行時間は線形です.
各ArrayListインスタンスには、要素を格納する配列のサイズである容量(Capacity)があります.この容量は、新しい要素を追加するにつれて自動的に増加することができるが、成長アルゴリズムは定義されていない.大量の要素を挿入する必要がある場合、挿入前にensureCapacityメソッドを呼び出してArrayListの容量を増やして挿入効率を向上させることができる.
LinkedListと同様にArrayListも非同期である(unsynchronized).
:
Boolean add(Object o)
Boolean add(int index,Object element)
Boolean addAll(Collection c)
Boolean addAll(int index,Collection c)
Boolean clear()
Boolean clone()
Boolean contains(Object o)
Boolean ensureCapacity(int m) , , m
Object get(int index)
Int indexOf(Object elem)
Int size()
Vectorクラス
VectorはArrayListによく似ていますが、Vectorは同期しています.Vectorによって作成されたIteratorは、ArrayListによって作成されたIteratorと同じインタフェースであるが、Vectorが同期しているため、1つのIteratorが作成され使用されている場合、別のスレッドがVectorの状態を変更し(例えば、いくつかの要素を追加または削除した場合)、Iteratorのメソッドを呼び出すとConcurrentModificationExceptionが投げ出され、そのため、この例外をキャプチャする必要があります.
Stackクラス
StackはVectorから継承され、後進先出のスタックを実現します.Stackは、5つの追加の方法を提供し、Vectorをスタックとして使用することができる.基本的なpushとpop法、peek法はスタックトップの要素を得、empty法はスタックが空であるかどうかをテストし、search法はスタック内の要素の位置を検出する.Stackが作成されたばかりで空きスタックです.
Setインタフェース
Setは、重複する要素を含まないCollectionである.すなわち、任意の2つの要素e 1およびe 2にe 1.equals(e 2)=falseがあり、Setにはnull要素が最大1つある.
明らかに、Setのコンストラクション関数には、入力されたCollectionパラメータに重複する要素を含めることができない制約があります.
注意:可変オブジェクト(Mutable Object)の操作に注意してください.Setの可変要素が自身の状態を変更した場合、Object.equals(Object)=trueになると、いくつかの問題が発生します.
Mapインタフェース
MapはCollectionインタフェースを継承していません.Mapはkeyからvalueへのマッピングを提供します.1つのMapに同じキーを含めることはできません.各キーには1つのvalueしかマッピングできません.Mapインタフェースは、3つのセットのビューを提供し、Mapの内容は、keyセット、valueセット、またはkey-valueマッピングのセットとして使用することができる.
主な方法:
boolean equals(Object o)比較対象
オブジェクトを削除
put(Object key,Object value)keyとvalueを追加
Hashtableクラス
HashtableはMapインタフェースを継承し、key-valueマッピングのハッシュテーブルを実現する.空でないオブジェクトはkeyまたはvalueとして使用できます.
追加データはput(key,value)、取り出しデータはget(key)を使用し、この2つの基本動作の時間オーバーヘッドは定数である.
Hashtableはinitial capacityとload factorの2つのパラメータで性能を調整します.通常、デフォルトのload factor 0.75は、時間と空間の等化をより良く実現する.load factorを大きくすると、スペースを節約できますが、対応する検索時間が大きくなり、getやputのような操作に影響します.Hashtableを使用する簡単な例は、1,2,3をHashtableに配置し、keyはそれぞれ「one」、「two」、「three」である.
Hashtable numbers = new Hashtable();
numbers.put(“one”, new Integer(1));
numbers.put(“two”, new Integer(2));
numbers.put(“three”, new Integer(3));
， 2， key：
Integer n = (Integer)numbers.get(“two”);
System.out.println(“two = ” + n);
keyとしてのオブジェクトは、そのハッシュ関数を計算することによって対応するvalueの位置を決定するので、keyとしてのオブジェクトはhashCodeおよびequalsメソッドを実装する必要があります.hashCodeメソッドとequalsメソッドはルートクラスObjectから継承されます.カスタムクラスをkeyとして使用する場合は、ハッシュ関数の定義に従って、obj 1.equals(obj 2)=trueの2つのオブジェクトが同じである場合、hashCodeは同じである必要がありますが、2つのオブジェクトが異なる場合、hashCodeは必ずしも異なるとは限りません.2つの異なるオブジェクトのhashCodeが同じである場合、この現象は衝突と呼ばれ,衝突はハッシュテーブルを操作する時間のオーバーヘッドを増大させるため,ハッシュテーブルの操作を速めるためにできるだけ良いhashCode()メソッドを定義することができる.
同じオブジェクトに異なるhashCodeがある場合、ハッシュ・テーブルの操作で予想外の結果が得られます(期待されるgetメソッドはnullを返します).このような問題を回避するには、equalsメソッドとhashCodeメソッドを同時に複写し、そのうちの1つだけ書かないでください.
Hashtableは同期しています.
HashMapクラス
HashMapはHashtableと同様であり、HashMapが非同期でありnull、すなわちnull valueおよびnull keyを許容する点が異なる.ただし、HashMapをCollectionと見なす場合(values()メソッドはCollectionを返します)、反復サブオペレーション時間のオーバーヘッドはHashMapの容量に比例します.したがって,反復動作の性能がかなり重要であれば,HashMapの初期化容量を高すぎる,あるいはload factorが低すぎるようにしてはならない.
WeakHashMapクラス
WeakHashMapは、keyに対して「弱い参照」を実行する改良されたHashMapであり、1つのkeyが外部に参照されなくなった場合、そのkeyはGCで回収することができる.
まとめ
スタック,キューなどの操作に関しては,リストを用いること,要素の迅速な挿入,削除が必要な場合はLinkedList,要素への迅速なランダムアクセスが必要な場合はArrayListを用いることを考慮すべきである.プログラムが単一スレッド環境にある場合、または1つのスレッドでのみアクセスされる場合、非同期クラスを考慮すると効率が高く、複数のスレッドが1つのクラスを同時に操作できる場合は、同期クラスを使用する必要があります.ハッシュ・テーブルの操作に特に注意し、keyのオブジェクトとしてequalsメソッドとhashCodeメソッドを正しく複写します.実際のタイプではなくインタフェースをできるだけ返します.例えば、ArrayListではなくListを返します.これにより、後でArrayListをLinkedListに変更する必要がある場合、クライアントコードは変更されません.これが抽象プログラミングです.