各種容器解析

1容器は2種類あります:CollectionとMap
2それぞれの傘下の子関係:
 Collection:
----List:実装クラスはArrayList/Link edList/Vectorである.
特徴:特定の順序で要素を入れ、取り出す可能性と入れる順序が異なる.重複する要素があります.
 
----Set:インタフェースで、実装クラスは:HashSet/ThreeSet.
特徴:繰り返し要素を持つことはできません.その反復器で要素を巡ります.
 
使用方法:
----ArrayListは最長で検索効率が高い.配列形式で格納されると理解できる.LinkedListは、チェーンテーブル形式で格納され、挿入削除効率が高く、検索効率が低いことが理解できる.要素を得るためにget(int index)メソッドもありますが、内部はチェーンテーブルの接続順序で滴を探すため、get()の効率は高くありません.Vectorは常にArrayListより遅く、あまり使われません.
 
------HashSet:実際にはHashMapの例であり、ソースコードから内部インスタンス化がhashMapであることがわかる.setの反復順序を保証しません.特に、この順序が恒久的に変わらないことは保証されません.このクラスではnull要素を使用できます.その反復器が要素を遍歴することができます.TreeSet:内部要素のソート状態を維持できます.TreeSetは、通常、ソートされたシーケンスを生成する必要がある場合にのみ使用され、HashSetよりも検索削除効率が低下します.もっとよく使われるのはHashSet.
 
------TreeSet:TreeMapの例で、ソート後の順序を昇順にソートするか、setで提供される比較器でソートすることを保証します.
       
HashSetとTreeSetの違い:前者は順序がなく、後者は順序があり、繰り返すことができない.HashSetはHashアルゴリズムに基づいて実現され、その性能は通常TreeSetより優れており、私たちは通常HashSetを使用すべきであり、ソート機能が必要な場合、私たちのドアはTreeSetを使用する.
 
 
Map:
---はインタフェースで、実装クラスはHashMap/TreeMap/HashTableである.
特徴:キー値ペアが格納されます.「キー」はユニークな滴で、対応する「値」は繰り返すことができます.
使用方法:
------HashMap:添削などの基本的な操作があり、内部メカニズムは対象のHashCodeを利用して素早くkeyを見つける.
 
注:HashMapはhashテーブルのデータ構造を利用して、独自のhash関数によってキーワードkeyを唯一無二のint値、すなわちhash値に変換し、この数値でそのkeyがarray配列(長さ決定、デフォルト16、拡張できない、ArrayListとは異なる)中の位置を決定し、その位置に値があれば、位置の後ろにチェーンテーブルを接続し、同じhash値を置くための値、すなわち1つのarrayの値が複数のvalueに対応する.
 
付録:hashテーブル構造は、二次線形のハッシュなど、衝突を解決するための別の方法もあります.詳細を略す.
 
-----TreeMap:このマッピングは、そのキーのしぜんじゅんじょに従ってソートされるか、またはマッピングの作成時に提供されるComparatorに従ってソートされる.
 
----HashTable:HashMapはHashTableの代わりに使われるクラスで、一般的に現在は後者を使わない.後者はnull値をサポートしません.hash値の使用は異なり、HashTableはhashCodeを直接使用してhash値を得、コードは以下の通りである.

int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

HashMapはhash式がhash値を計算して、コードは

int hash = hash(k);
int i = indexFor(hash, table.length);
static int hash(Object x) {
　　 int h = x.hashCode();

　　 h += ~(h << 9);
　　 h ^= (h >>> 14);
　　 h += (h << 4);
　　 h ^= (h >>> 10);
　　 return h;
}
static int indexFor(int h, int length) {
　　 return h & (length-1);
}

 
HashMapはクイック検索に使用されます.