Javaコレクションフレームワーク復習
List
ArrayList
次のコードを使用して、ArrayListクラスのオブジェクトをインスタンス化します.
ArrayList list=new ArrayL
JDKソースコードを調べると、ArrayList空のコンストラクション関数は実際に次のコンストラクション関数を呼び出していることがわかります.
public
ArrayList(
int
initialCapacity) {
super();
if(initialCapacity < 0)
thrownewIllegalArgumentException("Illegal Capacity:"+
initialCapacity);
this.elementData =newObject[initialCapacity];
}
その中で最も重要なオブジェクトが現れたのはelementDataであり、Object配列であり、
後で「add」するオブジェクトを保存するために使用します.
次にaddメソッドを見てみましょう.
/**
* Appends the specified element to the end of this list.
*
* @parame element to be appended to this list
* @returntrue (as specified by {@link Collection#add})
*/
publicboolean add(E e) {
ensureCapacity(size + 1); //Increments modCount!!
elementData[size++] = e;
returntrue;
}
まず、ensureCapacityという名前のメソッドを呼び出します.
まずmodCountを見てみましょう.現在のlistオブジェクトが変更された回数を記録するために使用されます.
addメソッドが最初に呼び出され、elementDataのsizeが0の場合、minCapacity
の値は1で、10回目にaddを呼び出すまで、ensureCapacityメソッドは本当に
elementDataの容量を大きくします.11回目にaddメソッドが呼び出されるまで:modCountは記録しました
リストを11回修正し、次のoldCapacity(10)「新しい容量」(newCapacity)は16に割り当てられ、最後にArrays.copyOfを呼び出して古い配列に対して
コピー1部.
ArrayList内部では配列を用いて実装されるため,ランダムアクセスよりも長く,これは他の集合オブジェクトに対してのみであり,配列に比べて効率が非常に低い.
LinkedList
LinkedList部分のソースコードは以下の通りです.
チェーンテーブルに基づいて実装され、各entryオブジェクト(ノード)には、前後の2つのノードへの参照と独自の値が含まれます.
addとremoveの2つの方法に重点を置いてみましょう.
まずadd:
双方向ループチェーンテーブルは、ハンドルのように、各ノードが接続されており、add、removeのオーバーヘッドは小さい.Removeメソッドは次のとおりです.
その代価はランダムアクセスよりも短い.
Map
Mapは強力なプログラミングツールで、オブジェクトを別のオブジェクトにマッピングする能力(key---->value)を提供します.
HashMap
mapではkey--->valueというキー値がペアであるため、keyは繰り返してはいけないことを要求し、valueは繰り返してもよい.次の例のように、
前の例ではMapのkeyとしてStringを使用していましたが、「a」がmapに2回目に入ったときは無視されました.(この例を引用すると、文字列配列内の要素の出現回数を統計するために使用できます.)
mapを正しく使用できる前に、なぜそのkeyが繰り返してはいけないのか、どのように繰り返してはいけないのかを知っておく必要があります.
JDKのHashMapのソースコードを見ると、オブジェクト「put」をmapに入れるたびに、JDKはこのオブジェクトとmapにすでに存在するオブジェクトを比較します.以下のようにします.
次の例では、equalsメソッドとhashCodeメソッドを書き換えます.
TreeMap
ArrayList
次のコードを使用して、ArrayListクラスのオブジェクトをインスタンス化します.
ArrayList
JDKソースコードを調べると、ArrayList空のコンストラクション関数は実際に次のコンストラクション関数を呼び出していることがわかります.
public ArrayList(intinitialCapacity) {
super();
if(initialCapacity < 0)
thrownewIllegalArgumentException("Illegal Capacity:"+
initialCapacity);
this.elementData = newObject[initialCapacity];
}
public
ArrayList(
int
initialCapacity) {
super();
if(initialCapacity < 0)
thrownewIllegalArgumentException("Illegal Capacity:"+
initialCapacity);
this.elementData =newObject[initialCapacity];
}
その中で最も重要なオブジェクトが現れたのはelementDataであり、Object配列であり、
後で「add」するオブジェクトを保存するために使用します.
次にaddメソッドを見てみましょう.
/**
* Appends the specified element to the end of this list.
*
* @parame element to be appended to this list
* @return<tt>true</tt> (as specified by {@link Collection#add})
*/
publicboolean add(E e) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = e;
returntrue;
}
/**
* Appends the specified element to the end of this list.
*
* @parame element to be appended to this list
* @returntrue (as specified by {@link Collection#add})
*/
publicboolean add(E e) {
ensureCapacity(size + 1); //Increments modCount!!
elementData[size++] = e;
returntrue;
}
まず、ensureCapacityという名前のメソッドを呼び出します.
/**
* Increases the capacity of this <tt>ArrayList</tt>instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
publicvoid ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity= minCapacity;
//minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
/**
* Increases the capacity of this <tt>ArrayList</tt>instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
publicvoid ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity= minCapacity;
//minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
まずmodCountを見てみましょう.現在のlistオブジェクトが変更された回数を記録するために使用されます.
addメソッドが最初に呼び出され、elementDataのsizeが0の場合、minCapacity
の値は1で、10回目にaddを呼び出すまで、ensureCapacityメソッドは本当に
elementDataの容量を大きくします.11回目にaddメソッドが呼び出されるまで:modCountは記録しました
リストを11回修正し、次のoldCapacity(10)
コピー1部.
ArrayList内部では配列を用いて実装されるため,ランダムアクセスよりも長く,これは他の集合オブジェクトに対してのみであり,配列に比べて効率が非常に低い.
LinkedList
LinkedList部分のソースコードは以下の通りです.
privatetransient Entry<E> header = new Entry<E>(null, null, null);
privatetransientintsize =0;
/**
* Constructs an empty list.
*/
public LinkedList() {
header.next = header.previous = header;
}
privatetransient Entry<E> header = new Entry<E>(null, null, null);
privatetransientintsize =0;
/**
* Constructs an empty list.
*/
public LinkedList() {
header.next = header.previous = header;
}
チェーンテーブルに基づいて実装され、各entryオブジェクト(ノード)には、前後の2つのノードへの参照と独自の値が含まれます.
addとremoveの2つの方法に重点を置いてみましょう.
まずadd:
publicbooleanadd(E e) {
addBefore(e, header);
returntrue;
}
addBefore :
private Entry<E> addBefore(Ee, Entry<E> entry) {
Entry<E>newEntry = newEntry<E>(e, entry, entry.previous);
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}
双方向ループチェーンテーブルは、ハンドルのように、各ノードが接続されており、add、removeのオーバーヘッドは小さい.Removeメソッドは次のとおりです.
private E remove(Entry<E> e) {
if (e == header)
thrownewNoSuchElementException();
E result = e.element;
e.previous.next = e.next;
e.next.previous = e.previous;
e.next =e.previous = null;
e.element = null;
size--;
modCount++;
returnresult;
}
その代価はランダムアクセスよりも短い.
Map
Mapは強力なプログラミングツールで、オブジェクトを別のオブジェクトにマッピングする能力(key---->value)を提供します.
HashMap
mapではkey--->valueというキー値がペアであるため、keyは繰り返してはいけないことを要求し、valueは繰り返してもよい.次の例のように、
String[] strs={"a","b","c","c","d","a","e"};
Map<String,Integer> result=new HashMap<String, Integer>();
for(int i=0;i<strs.length;i++){
result.put(strs[i], new Integer(1));
}
System.out.println(result);
前の例ではMapのkeyとしてStringを使用していましたが、「a」がmapに2回目に入ったときは無視されました.(この例を引用すると、文字列配列内の要素の出現回数を統計するために使用できます.)
mapを正しく使用できる前に、なぜそのkeyが繰り返してはいけないのか、どのように繰り返してはいけないのかを知っておく必要があります.
JDKのHashMapのソースコードを見ると、オブジェクト「put」をmapに入れるたびに、JDKはこのオブジェクトとmapにすでに存在するオブジェクトを比較します.以下のようにします.
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
では、2つのkeyが同じかどうかは、equal法とhashCode法に依存する.よく知られているように、HashSetに格納されている要素も重複せず、mapに基づいて実現されています.次の例では、equalsメソッドとhashCodeメソッドを書き換えます.
package com.lemon.map;
import java.util.HashSet;
import java.util.Iterator;
public class HashSetTest2 {
public static void main(String[] args) {
HashSet<StudentModel> set=new HashSet<StudentModel>();
set.add(new StudentModel(new Integer(1),"Bill"));
set.add(new StudentModel(new Integer(1),"Bill"));
set.add(new StudentModel(new Integer(1),"Bill"));
Iterator<StudentModel> it=set.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
}
}class StudentModel {
private Integer id;
private String name;
public StudentModel(Integer id,String name) {
this.id=id;
this.name=name;
}
@Override
public String toString() {
return "I am a student which id is["+id.intValue()+"] and name is["+name+"]";
}
@Override
public boolean equals(Object obj) {
return obj instanceof StudentModel&&((StudentModel)obj).id.equals(id)&&((StudentModel)obj).name.equals(name);
}
@Override
public int hashCode() {
int result=17;
int c=new Integer(id).hashCode()+name.hashCode();
result=37*result+c;
return result;
}
}
TreeMap