Javaベースのコンテナ編
8741 ワード
概要
[いい文章]http://www.cnblogs.com/skywang12345/p/3323085.html
緑色で塗りつぶされたクラスが一般的です
Collection
主にList,Set,Queueの3つのサブインタフェースCollectionインタフェースpublic interface Collection extends Iterableの主な方法があります.
Listインタフェース
ListインタフェースListインタフェースはCollectionダイレクトインタフェースである.Listは、ある特定の挿入順序で要素順序を維持する秩序化されたCollectionを表す.実装Listインタフェースの集合は,主にArrayList,LinkedList,Vector,Stackである.
順序付けられたCollection(シーケンスとも呼ばれる)で、要素は順序付けされているため、操作時にメソッドでインデックスを使用できます.
public interface List extends Collection
ArrayList ArrayListは動的配列であり,我々が最もよく用いる集合でもある.ルールに合致する要素をnullまで挿入できます.各ArrayListには初期容量があります(10)この容量は配列の大きさを表しています.容器内の要素が増えるにつれて、容器の大きさも大きくなります.容器内に要素を増やすたびに容量チェックが行われ、オーバーフローが近づくと拡張操作が行われます.したがって、挿入された要素の数を明確にするには、初期容量値を指定して、過剰な拡張を避けることが望ましいです操作を許容して時間、効率を浪費する.size、isEmpty、get、set、iterator、listIterator操作は、いずれも一定時間実行されます.add操作は、割り当てられた固定時間で実行されます.すなわち、n個の要素を追加するにはO(n)時間が必要です(拡張を考慮すると、要素を追加するだけでなく、割り当てられた固定時間のオーバーヘッドをもたらすほど簡単ではありません).
ArrayListはランダムアクセスが得意です.同時にArrayListは非同期です.
LinkedList
同様にListインタフェースを実装するLinkedListはArrayListとは異なり、ArrayListは動的配列であり、LinkedListは双方向チェーンテーブルである.したがって、ArrayListの基本的な操作方法に加えて、get、remove、insertメソッドがLinkedListのヘッダまたは末尾に追加されます.実装方法が異なるため、LinkedListはランダムにアクセスできず、すべての操作は二重チェーンテーブルの必要に応じて実行されます.リスト内のインデックスの操作は、リストの先頭または末尾(指定されたインデックスに近い端から)を巡回します.これにより、リスト内の挿入および削除操作を低コストで行うことができます.
ArrayListと同様にLinkedListも非同期である.複数のスレッドが同時にリストにアクセスする場合は、アクセス同期を自分で実現する必要があります.1つの解決策は、Listの作成時に同期するList:List list=Collectionsを構築することである.synchronizedList(new LinkedList(…));
VectorはArrayListと似ていますが、Vectorは同期しています.だからVectorはスレッドの安全な動的配列です.その動作はArrayListとほぼ同じです.
Stack StackはVectorから継承され、後進先出のスタックを実現します.Stackは、5つの追加の方法を提供し、Vectorをスタックとして使用することができる.基本的なpushとpop法、peek法はスタックトップの要素を得、empty法はスタックが空であるかどうかをテストし、search法はスタック内の要素の位置を検出する.Stackが作成されたばかりで空きスタックです.
Setインタフェース
public interface Set extends Collection
順序なしで繰り返すことはできません.したがって、インデックス操作オブジェクトを通過することはできません.通常、setはペアの要素setインタフェースを含まないので、独自の内部ソートを維持する特別な方法は定義されていません.したがって、ランダムアクセスは意味がありません.
Setインタフェースの具体的な実装クラスは,TreeSet,HashSet,LinkedHashSet,SortedSet,EnumSetである.
EnumSetは列挙された専用Setである.すべての要素は列挙タイプです.HashSet HashSetは、内部がHashCodeによって実現されるため、クエリ速度が最も速い集合と言える.その内部要素の順序はハッシュコードによって決定されるので、setの反復順序を保証しない.特に、この順序が恒久的に変わらないことは保証されません.TreeSetはTreeMapに基づいて、常にソート状態にあるsetを生成し、内部はTreeMapで実現する.これは、エレメントの自然な順序を使用してエレメントをソートするか、使用する構造方法に応じて、Setの作成時に提供されるComparatorに従ってソートします.
Queueインタフェース
public interface Queue extends Collection
Mapインタフェース
class Map implements Serializable
キー値ペアを格納し、Mapの値はコンテナであってもよい
Mapではkeyとvalueの対応関係を保証しています.すなわち、1つのkeyはvalueに対応するので、同じkey値は存在しません.
mapを実現するのは,HashMap,TreeMap,HashTable,Properties,EnumMapである.
HashMapはハッシュ・テーブルのデータ構造で実現され、オブジェクトを検索する際にハッシュ関数によってその位置を計算します.これは高速クエリーのために設計されています.内部にはhashテーブル配列(Entry[]table)が定義されており、要素はハッシュ変換関数によって要素のハッシュアドレスを配列に格納されたインデックスに変換し、競合がある場合はハッシュチェーンテーブルの形式で同じハッシュアドレスのすべての要素を直列に接続し、HashMap.Entryのソースコードを表示することで単一のチェーンテーブル構造である可能性がある.
キーはあるソート規則で並べ替えられ、内部はred-black(赤-黒)ツリーデータ構造で実現され、SortedMapインタフェースを実現した.
HashTableもハッシュテーブルデータ構造で実現されており,衝突を解決する際もHashMapと同様にハッシュチェーンテーブルとして採用されているが,HashMapよりも性能が低い.
異同点
1、VectorとArrayList
2、AarraylistとLinkedlist
3、HashMapとTreeMap
4、hashtableとhashmap
コレクションの選択
1、Listの選択
2、Setの選択
3、Mapの選択
[いい文章]http://www.cnblogs.com/skywang12345/p/3323085.html
緑色で塗りつぶされたクラスが一般的です
Collection
主にList,Set,Queueの3つのサブインタフェースCollectionインタフェースpublic interface Collection extends Iterableの主な方法があります.
boolean add(Object obj): , true boolean remove(Object o);
Iterator iterator(): Iterator
int size()
boolean isEmpty() //
boolean contains(Object obj) //
void clear()
Object[] toArray(); //
boolean equals(Object o);
int hashCode();
boolean retainAll(Collection<?> c);
boolean removeAll(Collection<?> c);
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
Listインタフェース
ListインタフェースListインタフェースはCollectionダイレクトインタフェースである.Listは、ある特定の挿入順序で要素順序を維持する秩序化されたCollectionを表す.実装Listインタフェースの集合は,主にArrayList,LinkedList,Vector,Stackである.
順序付けられたCollection(シーケンスとも呼ばれる)で、要素は順序付けされているため、操作時にメソッドでインデックスを使用できます.
public interface List extends Collection
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
int indexOf(Object o);
int lastIndexOf(Object o);
List<E> subList(int fromIndex, int toIndex);
ArrayList ArrayListは動的配列であり,我々が最もよく用いる集合でもある.ルールに合致する要素をnullまで挿入できます.各ArrayListには初期容量があります(10)この容量は配列の大きさを表しています.容器内の要素が増えるにつれて、容器の大きさも大きくなります.容器内に要素を増やすたびに容量チェックが行われ、オーバーフローが近づくと拡張操作が行われます.したがって、挿入された要素の数を明確にするには、初期容量値を指定して、過剰な拡張を避けることが望ましいです操作を許容して時間、効率を浪費する.size、isEmpty、get、set、iterator、listIterator操作は、いずれも一定時間実行されます.add操作は、割り当てられた固定時間で実行されます.すなわち、n個の要素を追加するにはO(n)時間が必要です(拡張を考慮すると、要素を追加するだけでなく、割り当てられた固定時間のオーバーヘッドをもたらすほど簡単ではありません).
ArrayListはランダムアクセスが得意です.同時にArrayListは非同期です.
LinkedList
同様にListインタフェースを実装するLinkedListはArrayListとは異なり、ArrayListは動的配列であり、LinkedListは双方向チェーンテーブルである.したがって、ArrayListの基本的な操作方法に加えて、get、remove、insertメソッドがLinkedListのヘッダまたは末尾に追加されます.実装方法が異なるため、LinkedListはランダムにアクセスできず、すべての操作は二重チェーンテーブルの必要に応じて実行されます.リスト内のインデックスの操作は、リストの先頭または末尾(指定されたインデックスに近い端から)を巡回します.これにより、リスト内の挿入および削除操作を低コストで行うことができます.
ArrayListと同様にLinkedListも非同期である.複数のスレッドが同時にリストにアクセスする場合は、アクセス同期を自分で実現する必要があります.1つの解決策は、Listの作成時に同期するList:List list=Collectionsを構築することである.synchronizedList(new LinkedList(…));
VectorはArrayListと似ていますが、Vectorは同期しています.だからVectorはスレッドの安全な動的配列です.その動作はArrayListとほぼ同じです.
Stack StackはVectorから継承され、後進先出のスタックを実現します.Stackは、5つの追加の方法を提供し、Vectorをスタックとして使用することができる.基本的なpushとpop法、peek法はスタックトップの要素を得、empty法はスタックが空であるかどうかをテストし、search法はスタック内の要素の位置を検出する.Stackが作成されたばかりで空きスタックです.
Setインタフェース
public interface Set extends Collection
順序なしで繰り返すことはできません.したがって、インデックス操作オブジェクトを通過することはできません.通常、setはペアの要素setインタフェースを含まないので、独自の内部ソートを維持する特別な方法は定義されていません.したがって、ランダムアクセスは意味がありません.
Setインタフェースの具体的な実装クラスは,TreeSet,HashSet,LinkedHashSet,SortedSet,EnumSetである.
EnumSetは列挙された専用Setである.すべての要素は列挙タイプです.HashSet HashSetは、内部がHashCodeによって実現されるため、クエリ速度が最も速い集合と言える.その内部要素の順序はハッシュコードによって決定されるので、setの反復順序を保証しない.特に、この順序が恒久的に変わらないことは保証されません.TreeSetはTreeMapに基づいて、常にソート状態にあるsetを生成し、内部はTreeMapで実現する.これは、エレメントの自然な順序を使用してエレメントをソートするか、使用する構造方法に応じて、Setの作成時に提供されるComparatorに従ってソートします.
Queueインタフェース
public interface Queue extends Collection
//
boolean add(E e);// , , IIIegaISlabEepeplian
boolean offer(E e); true, , false
//
E remove(); // , , NoSuchElementException
E poll(); // , , null
//
E element();// , , NoSuchElementException
E peek();// , , null
, , , , ArrayBlockQueue、PriorityBlockingQueue、LinkedBlockingQueue。 , 、 , :ArrayDeque、LinkedBlockingDeque、LinkedList。
Mapインタフェース
class Map implements Serializable
キー値ペアを格納し、Mapの値はコンテナであってもよい
Mapではkeyとvalueの対応関係を保証しています.すなわち、1つのkeyはvalueに対応するので、同じkey値は存在しません.
mapを実現するのは,HashMap,TreeMap,HashTable,Properties,EnumMapである.
HashMapはハッシュ・テーブルのデータ構造で実現され、オブジェクトを検索する際にハッシュ関数によってその位置を計算します.これは高速クエリーのために設計されています.内部にはhashテーブル配列(Entry[]table)が定義されており、要素はハッシュ変換関数によって要素のハッシュアドレスを配列に格納されたインデックスに変換し、競合がある場合はハッシュチェーンテーブルの形式で同じハッシュアドレスのすべての要素を直列に接続し、HashMap.Entryのソースコードを表示することで単一のチェーンテーブル構造である可能性がある.
キーはあるソート規則で並べ替えられ、内部はred-black(赤-黒)ツリーデータ構造で実現され、SortedMapインタフェースを実現した.
HashTableもハッシュテーブルデータ構造で実現されており,衝突を解決する際もHashMapと同様にハッシュチェーンテーブルとして採用されているが,HashMapよりも性能が低い.
異同点
1、VectorとArrayList
1,vector , , arraylist , 。 , arraylist 。
2, ,vector 100%, arraylist 50%. , vector 。
3, ,vector arraylist , 0(1), vector arraylist 。 0(n-i)n , linklist, 0(1), 0(i)。
ArrayList Vector , , , , ,Vector synchronized ( ) ArrayList ,LinkedList , , , !
2、AarraylistとLinkedlist
1.ArrayList ,LinkedList 。
2. get set,ArrayList LinkedList, LinkedList 。
3. add remove,LinedList , ArrayList 。
。 ,ArrayList LinkedList。 ,LinkedList ArrayList. ArrayList , 。
3、HashMapとTreeMap
1、HashMap hashcode , TreeMap , TreeMap(HashMap )。HashMap )。
2、 HashMap hashcode , TreeMap , TreeMap(HashMap )。 ” Map :HashMap TreeMap (TreeMap SortedMap )。
3、 Map 、 ,HashMap 。 , TreeMap 。 HashMap hashCode() equals() 。 TreeMap , 。
4、hashtableとhashmap
1、 :Hashtable Dictionary ,HashMap Java 1.2 Map 。
2、 :Hashtable , , HashMap , 。
3、 : HashMap key value 。
コレクションの選択
1、Listの選択
1、 , 。 ArrayList
2、LinkedList , ArrayList 。
3、 Vector , 。
4、 ArrayList , , List , LinkedList。
2、Setの選択
1、HashSet HashCode , TreeSet , 。
3、 TreeSet HashSet , , 。
3、Mapの選択
1、HashMap HashSet , 。 HashTable , HashMap , HashMap HashTable。
2、 TreeMap , HashMap HashTable 。