JAva容器の整理(version 0.1)
5904 ワード
この方面の内容はthinking in javaという本を基本参考資料として、まずjavaのContainerの簡略化図を見てみましょう.
thinking in java(4 th)の練習をする人もいるかもしれませんが、参考答案はここです.http://greggordon.org/java/tij4/solutions.htmこの兄貴の無私な貢献に感謝します.
1、ComparableとComparatorの違い:
public interface Comparableこのインタフェースは、実装された各クラスのオブジェクトを強制的に並べ替えます.このソートをクラスの自然ソートと呼び,クラスのcompareToメソッドをその自然比較メソッドと呼ぶ.このインタフェースを実装オブジェクトのリスト(および配列)はCollections.sort(およびArrays.sort)を自動ソートします.このインタフェースを実装するオブジェクトは、比較器を指定することなく、順序マッピングのキーまたは順序セットの要素として使用できます.public interface Comparatorオブジェクトcollectionを全体的にソートする比較関数.Collections.sortまたはArrays.sortなどのsortメソッドにComparatorを渡すことで、ソート順の正確な制御を実現できます.また、Comparatorを使用して、秩序set-TreeSetや秩序マッピングなどのデータ構造の順序を制御したり、自然な順序のないオブジェクトcollectionの順序を指定したりすることもできます.
Comparableの使用には限界があり、1つの与えられたクラスに対して、このインタフェースは1回しか実現できません.1つのセットで番号付けで部品をソートする必要がある場合、別のセットでこの部品を別の属性(説明情報など)でソートする必要があり、このクラスの作成者がComparableインタフェースを実装していない場合、ComparatorオブジェクトをTreeSetコンストラクタに渡すことで、ツリーセットに異なる比較方法を使用するように伝えることができます.
参考:http://zhanghu198901.iteye.com/blog/1575164(コメントを見て考える)
API: http://docs.oracle.com/javase/6/docs/api/java/lang/Comparable.html
http://docs.oracle.com/javase/6/docs/api/java/util/Comparator.html
2、Setと記憶順序
Set (interface)
Each element that you add to the Set must be unique; otherwise, the Set doesn’t add the duplicate element. Elements added to a Set must at least define equals( ) to establish object uniqueness. Set has exactly the same interface as Collection. The Set interface does not guarantee that it will maintain its elements in any particular order.
HashSet*
For Sets where fast lookup time is important. Elements must also define hashCode( ).
TreeSet
An ordered Set backed by a tree. This way, you can extract an ordered sequence from a Set. Elements must also implement the Comparable interface.
LinkedHashSet
Has the lookup speed of a HashSet, but internally maintains the order in which you add the elements (the insertion order) using a linked list. Thus, when you iterate through the Set, the results appear in insertion order. Elements must also define hashCode( ).
Set (interface)
Setに格納された各要素は、Setが重複要素を保存しないため、一意でなければならない.Setを追加する要素は、オブジェクトの一意性を確保するためにequals()メソッドを定義する必要があります.SetはCollectionと全く同じインタフェースを持っています.Setインタフェースはメンテナンス要素の順序を保証しません.
HashSet*
すばやく検索するために設計されたSet.格納された要素は、null要素を1つまで含むhashcode()メソッドを実装する必要があります.
TreeSet
順序のSetを保持し,下層はツリー構造である.Setから秩序化されたシーケンスを抽出するには、要素がSortedSetの唯一の実装であるComparableインタフェースを実装する必要があります.
LinkedHashSet
HashSetのクエリー速度があり、内部でチェーンテーブルを使用して要素の順序(挿入順序)を維持します.Setを巡回すると、結果は挿入順に表示され、要素もhashcode()メソッドを定義する必要があります.
ハッシュテーブル(hash table):オブジェクトをすばやく検索し、javaでハッシュをチェーンテーブル配列で実現します.各リストはバケツ(bucket)と呼ばれ、テーブル内のオブジェクトの位置を検索するには、まずそのハッシュコードを計算し、バケツの総数と残りを取り、その結果、この要素のインデックスを保存します.あるオブジェクトのハッシュコードが76268で、128個のバケツがある場合、オブジェクトは地108号バケツに保存されるべきである.バケツがいっぱいになることもありますが、これは避けられない現象で、ハッシュ衝突(hash collision)と呼ばれています.ハッシュ・リストはいくつかの重要なデータ構造を実現することができ、その中で最も簡単なのはsetタイプ(HashSet)である.
3、Queue
キュー(Queue)は典型的な先進的な先出し容器である.すなわち、容器の一端から物を入れ、他端から物を取り出し、物を容器に入れる順番が取り出す順番と一致する.キューは、プログラムのある領域から別の領域にオブジェクトを確実に転送する方法としてよく使用される.キューは、あるタスクから別のタスクにオブジェクトを安全に転送できるため、同時プログラミングで特に重要です.
異常を投げ出す
特殊値を返す
挿入
削除
けんさ
挿入操作の後の形式(特殊値を返す)は、容量制限のあるQueueのために設計されたものである.ほとんどのインプリメンテーションでは、挿入操作は失敗しません.詳細については、QueueのAPI:http://docs.oracle.com/javase/6/docs/api/java/util/Queue.htmlを参照してください.
LinkedListは、キューの動作をサポートする方法を提供し、Queueインタフェースを実現するので、LinkedListはQueueの実装として使用することができる.LinkedListをQueueに変換して使用できます.
LinkedList自体はスタックを実現するすべての機能方法を持っているので、LinkedListをスタックとして使用することができます(「スタック」通産は後進先出の容器を指し、あなたが類比できるものはスプリングが入ったメモリの中のバイキングトレイで、最後に入れたものは必ず最初に取り出して使用します).
4、Mapを理解する
HashMap*
Mapは、ハッシュテーブルの代わりにハッシュテーブルの実装に基づいている.キー値ペアの挿入とクエリーのオーバーヘッドは固定されます.コンテナのパフォーマンスを調整するには、コンストラクタで容量と負荷係数を設定します.HashMapのキーとして独自のクラスを使用する場合は、equals()メソッドとhashcode()メソッドを同時に上書きします.
LinkedHashMap
HashMapと似ていますが、反復する場合、「キー値ペア」を取得する順序は挿入順序、または最も最近使用されていない順序です.HashMapより少し遅いですが、反復する順序はチェーンテーブルを使用して内部順序を維持するため、逆に高速です.
TreeMap
赤と黒のツリーの実装に基づいて、「キー」または「キー値ペア」を表示すると、それらはソートされます(順序はComparableまたはComparatorによって決まります).TreeMapの特徴は、得られた結果がソートされていることです.
Mapにおけるキーの使用に対する要求はSetにおけるキーの使用に対する要求と一致する.任意のキーにはequals()メソッドが必要です.キーがハッシュMapに使用される場合、適切なhashcode()メソッドが必要である.キーがTreeMapに使用される場合は、Comparableを実装する必要があります.もう一度強調しますが、デフォルトのObjectです.equals()はオブジェクトのアドレスを比較するだけであり,自分のクラスをHashMapのキーとして使用するにはhashcode()とequals()を同時にリロードする必要はない.
ハッシュを使用する目的は、あるオブジェクトを使用して別のオブジェクトを検索することです.
(未完待機)
thinking in java(4 th)の練習をする人もいるかもしれませんが、参考答案はここです.http://greggordon.org/java/tij4/solutions.htmこの兄貴の無私な貢献に感謝します.
1、ComparableとComparatorの違い:
public interface Comparable
Comparableの使用には限界があり、1つの与えられたクラスに対して、このインタフェースは1回しか実現できません.1つのセットで番号付けで部品をソートする必要がある場合、別のセットでこの部品を別の属性(説明情報など)でソートする必要があり、このクラスの作成者がComparableインタフェースを実装していない場合、ComparatorオブジェクトをTreeSetコンストラクタに渡すことで、ツリーセットに異なる比較方法を使用するように伝えることができます.
SortedSet<Item> sortByDescription = new TreeSet<Item>(new
Comparator<Item>()
{
public int compare(Item a, Item b){
String descA = a.getDescription();
String descB = b.getDescription();
return descA.compareTo(descB);
}});
参考:http://zhanghu198901.iteye.com/blog/1575164(コメントを見て考える)
API: http://docs.oracle.com/javase/6/docs/api/java/lang/Comparable.html
http://docs.oracle.com/javase/6/docs/api/java/util/Comparator.html
2、Setと記憶順序
Set (interface)
Each element that you add to the Set must be unique; otherwise, the Set doesn’t add the duplicate element. Elements added to a Set must at least define equals( ) to establish object uniqueness. Set has exactly the same interface as Collection. The Set interface does not guarantee that it will maintain its elements in any particular order.
HashSet*
For Sets where fast lookup time is important. Elements must also define hashCode( ).
TreeSet
An ordered Set backed by a tree. This way, you can extract an ordered sequence from a Set. Elements must also implement the Comparable interface.
LinkedHashSet
Has the lookup speed of a HashSet, but internally maintains the order in which you add the elements (the insertion order) using a linked list. Thus, when you iterate through the Set, the results appear in insertion order. Elements must also define hashCode( ).
Set (interface)
Setに格納された各要素は、Setが重複要素を保存しないため、一意でなければならない.Setを追加する要素は、オブジェクトの一意性を確保するためにequals()メソッドを定義する必要があります.SetはCollectionと全く同じインタフェースを持っています.Setインタフェースはメンテナンス要素の順序を保証しません.
HashSet*
すばやく検索するために設計されたSet.格納された要素は、null要素を1つまで含むhashcode()メソッドを実装する必要があります.
TreeSet
順序のSetを保持し,下層はツリー構造である.Setから秩序化されたシーケンスを抽出するには、要素がSortedSetの唯一の実装であるComparableインタフェースを実装する必要があります.
LinkedHashSet
HashSetのクエリー速度があり、内部でチェーンテーブルを使用して要素の順序(挿入順序)を維持します.Setを巡回すると、結果は挿入順に表示され、要素もhashcode()メソッドを定義する必要があります.
ハッシュテーブル(hash table):オブジェクトをすばやく検索し、javaでハッシュをチェーンテーブル配列で実現します.各リストはバケツ(bucket)と呼ばれ、テーブル内のオブジェクトの位置を検索するには、まずそのハッシュコードを計算し、バケツの総数と残りを取り、その結果、この要素のインデックスを保存します.あるオブジェクトのハッシュコードが76268で、128個のバケツがある場合、オブジェクトは地108号バケツに保存されるべきである.バケツがいっぱいになることもありますが、これは避けられない現象で、ハッシュ衝突(hash collision)と呼ばれています.ハッシュ・リストはいくつかの重要なデータ構造を実現することができ、その中で最も簡単なのはsetタイプ(HashSet)である.
3、Queue
キュー(Queue)は典型的な先進的な先出し容器である.すなわち、容器の一端から物を入れ、他端から物を取り出し、物を容器に入れる順番が取り出す順番と一致する.キューは、プログラムのある領域から別の領域にオブジェクトを確実に転送する方法としてよく使用される.キューは、あるタスクから別のタスクにオブジェクトを安全に転送できるため、同時プログラミングで特に重要です.
異常を投げ出す
特殊値を返す
挿入
add(e)
offer(e)
削除
remove()
poll()
けんさ
element()
peek()
挿入操作の後の形式(特殊値を返す)は、容量制限のあるQueueのために設計されたものである.ほとんどのインプリメンテーションでは、挿入操作は失敗しません.詳細については、QueueのAPI:http://docs.oracle.com/javase/6/docs/api/java/util/Queue.htmlを参照してください.
LinkedListは、キューの動作をサポートする方法を提供し、Queueインタフェースを実現するので、LinkedListはQueueの実装として使用することができる.LinkedListをQueueに変換して使用できます.
LinkedList自体はスタックを実現するすべての機能方法を持っているので、LinkedListをスタックとして使用することができます(「スタック」通産は後進先出の容器を指し、あなたが類比できるものはスプリングが入ったメモリの中のバイキングトレイで、最後に入れたものは必ず最初に取り出して使用します).
4、Mapを理解する
HashMap*
Mapは、ハッシュテーブルの代わりにハッシュテーブルの実装に基づいている.キー値ペアの挿入とクエリーのオーバーヘッドは固定されます.コンテナのパフォーマンスを調整するには、コンストラクタで容量と負荷係数を設定します.HashMapのキーとして独自のクラスを使用する場合は、equals()メソッドとhashcode()メソッドを同時に上書きします.
LinkedHashMap
HashMapと似ていますが、反復する場合、「キー値ペア」を取得する順序は挿入順序、または最も最近使用されていない順序です.HashMapより少し遅いですが、反復する順序はチェーンテーブルを使用して内部順序を維持するため、逆に高速です.
TreeMap
赤と黒のツリーの実装に基づいて、「キー」または「キー値ペア」を表示すると、それらはソートされます(順序はComparableまたはComparatorによって決まります).TreeMapの特徴は、得られた結果がソートされていることです.
Mapにおけるキーの使用に対する要求はSetにおけるキーの使用に対する要求と一致する.任意のキーにはequals()メソッドが必要です.キーがハッシュMapに使用される場合、適切なhashcode()メソッドが必要である.キーがTreeMapに使用される場合は、Comparableを実装する必要があります.もう一度強調しますが、デフォルトのObjectです.equals()はオブジェクトのアドレスを比較するだけであり,自分のクラスをHashMapのキーとして使用するにはhashcode()とequals()を同時にリロードする必要はない.
ハッシュを使用する目的は、あるオブジェクトを使用して別のオブジェクトを検索することです.
(未完待機)