10周くらい遅れている感がありますが気にせず紹介します。なお実装はJDKによって異なる可能性があるので、お手元のJDKに付属しているコードをご覧になることをおすすめします。
java.util.concurrent.atomic.AtomicInteger
ロックフリーでスレッドセーフな実装を実現ことで有名なjava.util.concurrent.atomicパッケージの代表格。そんなすごいことをどう実装しているのか？というのは誰もが1度は気になるはず。openjdk7のコードを読むとこんな感じです。
public final int incrementAndGet() { for (;;) { int current = get(); int next = current + 1; if (compareAndSet(current, next)) return next; } }
CASと呼ばれる見慣れないメソッドがありますが、それ以外は「うまく行くまで何度でもやり直す」という非常に単純な実装です。
java.math.BigInteger
Javaの便利な点にAPIの充実さが挙げられますが、中でもBigIntegerの便利さは素晴らしいものです。私もTopCoderでたまにお世話になります。
ちなみに似たクラスにBigDecimalがありますが、こちらはBigIntegerに処理を委譲する事で比較的シンプルな実装になっています。
java.util.Properties
「これはひどい」的なエントリ。
InputStreamやReaderを受け取るloadメソッドがあるのですが、受け取ったStreamなどをcloseするかどうかがjavadocに記載されておらず、実装を読まなければ確認できません。このクラスを使った経験をお持ちの方は、実装確認の衝動にかられたのではないでしょうか。
java.io.BufferedWriter
I/O高速化のために必ずと言っていいほど使われるクラスですので、「バッファ」とは何でありなぜ高速化に繋がるのか？を理解しておきたいところです。
これを読んで初めてコンストラクタのintの意味がわかるようになりますし、常にメモリに大きめの配列（=連続領域）を保持するということもわかります。
似たクラスとして、BufferedOutputStreamもあります。
java.util.ArrayList
みんな大好き自動拡張機能付き配列。オブジェクトをラップして使いやすいインタフェースを提供するためのサンプルとして優秀ですし、よく使うクラスなのでJavaプログラミングの支えとなる知識も得られます。コードリーディング一押しのクラスです。
ArrayListは高速なget(int)が可能なので配列の延長として使うには便利ですが、末尾以外の要素をremove(int)するとSystem.arraycopyが走るという特徴があります。add(int, E)も同様の実装であり、読むことで「削除や挿入は遅そうだ」という感覚を得ることができます。
java.util.LinkedList
ArrayListに次いで有名なListインタフェースの実装。ArrayListが苦手なケース（QueueとかDeque*1とか）をうまくカバーできるので、双方の実装を理解して使い分けてやりたいところです。
こちらはget(int)が遅く、配列の延長として使うと痛い目を見ます。では反面remove(int)が高速か？というと、残念ながらそんなことはありません。privateメソッドであるnode(int)メソッドがリンクを辿って線形探索するためです。
/** * Returns the (non-null) Node at the specified element index. */ Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
LinkedListで大量にremoveを実行する場合は、Iteratorからremoveすることを検討したいところです。こちらは探索が不要（getNext()する時点ですでに実行済み）なので、より高速に行うことができます。
java.util.HashMap
キーと値を紐付けて記録できる便利クラス。tableフィールドの使われ方を読めばなぜ高速な検索が可能なのか理解できますが、ハッシュ法を学んでから読んだ方が良いでしょう。
このクラスの実装を読んで初めてhashcode()メソッドをオーバーライドしなければならない理由が理解できますので、DTOやEntityなどMapにキーとしてつっこむクラスを実装する機会の多い方はぜひご一読ください。
