毎週、社内で勉強会を昼飯どきにやってますけど、今日は List についてああだ、こうだと話しました。まぁ、主に LinkedListとArrayListについてですけど、それぞれの特徴を考えればどう使えばいいとか、当たり前のことなのかもしれないけど、実際に JDK のソースコードを元に議論した。あれこれ話したけど、ArrayList で add したときに配列を越えていたらいくつ増やすのだろうとか、実際に見たりで 1.5 倍して +1 している感じでした。+1 って何だろうと考えたら、配列とか 1 とかだと 1.5 倍しても 1 だからだめじゃん、というわけの +1 ということで納得。実際の Java6 の対象のコードは、
public void 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);
}
}
で、真ん中らへんの newCapacity のところがそれ。その他の部分については、minCapacity は最低限増やさなきゃならない配列数、oldCapacity は現在の配列数、newCapacityはこれくらい増やそうよ、という配列候補の配列数。で、newCapacityとminCapacity の比較している if 文は、addAll とかでがっつり配列が増やされるときにnewCapacity じゃ足りない場合があるから、必要ならminCapacityに変更している。ざっと見た感じではそんな感じかな(ちなみにmodCountはシリアライズとかするときに非同期に配列が書き換えられたときにチェックするための値。modCountがintを越える変更をしたらどうなるのだろう・・・)。さらに気になったので、Apache Harmonyもちらっと見たら、そもそもやりかたがちょっと違う。Harmony の方は、size を見るんじゃなくて、配列の先頭と最後の位置で管理していた。つまり、先頭の削除とかに強いのだろうね。という感じで、ちょっと賢くなりました。