JavaのCollectionとMap関連のインターフェースは以下。
Collection
|-- List
|-- Set ---- SortedSet ----- NavigableSet
|-- Queue -- BlockingQueue
`-- Deque -- BlockingDeque
Map
|-- SortedMap ------ NavigableMap
`-- ConcurrentMap -- ConcurrentNavigableMap
インターフェースだけで、14個も名前が出てくる。JavaDocのCollectionとMapからリンクしてるクラスを見ただけなので漏れもあるかもしれない。
これがそれぞれ1つ以上の実装クラスを持っているわけなので、全部の機能をちゃんと確認しようとすると軽く１週間くらいは潰せそうだ。老後は日永こういうことを調べて過ごしたいものだ。
実装クラスの中には使用を推奨されないクラスがDeprecatedマークもなしに闊歩していたりもするし、Googleが出してるJavaのCollectionであるgoogle-collections改め「Guava」がいたり、「Commons Primitives」にはプリミティブ型のまま値を入れられるCollectionが用意されたりもする。
ScalaプログラマはScalaのCollectionに加えてこれらの機能も全部把握しとくと良いのだろう。要件と性能的にそっちのが合ってるケースというのもありそうだし。
とりあえず、JDKにあるインターフェースだけは再確認してみた。けっこう知らないものもあって焦った。
・List
Listは順序を持つCollection。
主な実装クラスは、ArrayList、LinkedList、CopyOnWriteArrayList、Vector、Stack。
VectorとStackはあまり利用を推奨されていない。VectorはCollections.synchronizedListを利用し、StackはDequeを利用する。
ArrayListは内部的には配列で情報を保持して、必要に応じて配列のサイズを変更したりしてる。どの手の処理でもそれなりにこなしてくれるので、何も考えずに使う場合はこれを選択する。
LinkedListはQueue、Dequeも実装しているなど無駄に多機能。
CopyOnWriteArrayListは毎回内部的に持ってる配列を再生成する。
・Set
重複した要素を許可しないCollection。実装クラスによっては挿入した順序も保持される。
重複した要素が入ると問題になるような情報を取り扱う場合は、ListよりもSetを使った方が安全。
主な実装クラスは、HashSet、LinkedHashSet、CopyOnWriteArraySet。
HashSetは順序が保証されない。内部的にはHashMapを使って情報を保持している。LinkedHashSetはHashSetに順序を保持するようにしたもの。
・SortedSet / NavigableSet
SortedSetは名前の通り、ソートされたSet。コンストラクタにComparatorを渡すことで、任意の順序でソートされるようにすることもできる。
NavigableSetは、指定された値にもっとも近い要素を返してくれるSortedSet。例えば要素に、1.1、3.5、8.6が入っている場合に、set.floor(5.0)を実行すると、5.0と同じかそれより小さい数値の中で最も近い値（この例では3.5）を取得する。大きい数値を取得する場合はceiling。
主な実装クラスは、TreeSet、ConcurrentSkipListSet。この2つのクラスはSortedSetとNaigableSetの双方を実装している。
TreeSetはデフォルトだとTreeMapで情報を持っている。TreeMapはいわゆる赤黒木で情報を持ってるので、ソートされた状態が保てるし、直近の値を探索するのにも向いてる。
ConcurrentSkipListSetは内部的にはConcurrentSkipListMapで情報を保持している。concurrent（同時）の名の通り、マルチスレッド下での処理を想定している。データ構造は名前からするとスキップリストなのだろうけど、あまり詳しくは知らない。
・Queue
Queueは要素を出せと要求された場合に、先に入れた要素を先に出す形式（FIFO）のCollection。
Queueの先端を取得し、同時にその要素をQueueから削除するpollメソッドと、要素を削除しないpeekメソッドが用意されている。
主な実装クラスは、PriorityQueueと、なにげにLinkedListもQueueクラスを実装している。但しLinkedListはQueueでは推奨されていないnull要素を許可するなど、あまりQueueっぽくない。
あとはBlockingQueueやDeque関連のクラスはすべてQueueを実装している。その辺のクラスについては後述。
PriorityQueueは入れた要素がソートされるQueue。FIFOな動きではなくソート順が早いものから出てくるので、あまりQueueっぽくない。
Queueを使いたい時にどれを用いるのが一般的かはよく知らない。
・BlockingQueue
Queueは並列で処理されることが多いので、マルチスレッドでの動作に対応したBlockingQueue関連がけっこう充実している。
主な実装クラスは、ArrayBlockingQueue、DelayQueue、LinkedBlockingQueue、PriorityBlockingQueue、SynchronousQueue。
ArrayBlockingQueueとLinkedBlockingQueueは初期化時に容量を指定すると、容量を超えた要素を追加しようとした場合、addすると例外、offerだとfalseが返ってくる。putだと空きが出るまで待ち続ける。
DelayQueueはDelayedを継承したクラスだけ入れられる。Delayedには遅延時間が指定でき、指定された時間が経過しないとその要素はQueueから取り出すことができない。
SynchronousQueueはけっこう面白くて、Queueがサイズを持たない。他のスレッドが要素の取得待ち状態にある時だけ、要素を追加できる。メッセージ通信みたいな動きになる。
・Deque
デックと読む。昔、デキューと読むと勘違いしていた。Double Ended Queueの略で、Collectionの前方と後方、双方に対してQueueのようなpeekやpollの処理を実行できる。後方の要素を操作する場合は、peekLastやpollLastを使う。
後に入れた要素を先に出す（LIFO）処理を行いたい場合は、java.util.StackよりもDequeを使った方が良いとJavaDocに書いてある。
主な実装クラスは、ArrayDequeとLinkedList。ArrayDequeは名前の通り、ArrayListみたく配列で要素を持っている。
・BlockingDeque
マルチスレッドでの動作に対応したDeque。
要素の挿入には、add、addFirst、addLast、offer、offerFirst、offerLast、put、putFirst、putLastが、要素の削除には、remove、removeFirstOccurrence、removeLastOccurrence、take、takeFirst、takeLast、poll、pollFirst、pollLastが用意されている。
複雑過ぎて使いづらいような気もしなくもない。
主な実装クラスは、LinkedBlockingDeque。
・Map
KeyをValueにマッピングするオブジェクト。
挿入した順序が保証されるかは実装による。
主な実装クラスは、HashMap、LinkedHashMap、IdentityHashMap、WeakHashMap、Hashtable。
HashMapは挿入した順序を保持しない。LinkedHashMapは保持する。
Hashtableはマルチスレッドの処理を考慮しているけど、ConcurrentHashMapなりCollections.synchronizedMapなりがあるから使わなかった気がする。しかしこの辺りの話はイマイチ把握できていない。
IdentityHashMapはキーが同一かをequalsではなく==で判定するHashMap。ということは、new String(str)のように別のオブジェクトにして文字列を入れたら、同一の文字列のキーが複数存在する状態になる。
WeakHashMapは参照されなくなったキーがガベージコレクションの対象になるHashMap。例えば[Object, Integer]なWeakHashMapにmap.put(new Object(), 1)したあと、すぐにsizeを見ると1つ値が入っているけど、System.gc()して2秒間Thread.sleepとかすると、その間にガベージコレクションが働いてmapのsizeが0になっていたりする。
・SortedMap / NavigableMap
SortedMapはキー順にソートされたMap。NavigableMapはNavigableSetのように、指定した値に一番近いキーの値を取得してくれる。そういうシーンでは便利そう。
主な実装クラスは、TreeMap、ConcurrentSkipListMap。TreeMapもConcurrentSkipListMapも、SortedMap、NavigableMapの双方が実装されている。
ConcurrentSkipListMapは名前からして非同期処理にも対応しているはず。
・ConcurrentMap / ConcurrentNavigableMap
主な実装クラスは、ConcurrentHashMap、ConcurrentSkipListMap。
ConcurrentHashMapはHashtableと同じく、マルチスレッド下での動作を考慮したHashMap。
ConcurrentSkipListMapはスキップリストを利用していて、ConcurrentNavigableMapも実装している。ので、指定した値に近いキーを拾ってくることもできる。
・おまけ
DelayQueueを使ってみたメモ。ソースはScala2.9。
import java.util.concurrent.DelayQueue
import java.util.concurrent.{ TimeUnit, Delayed }
class DelayElem[T](val o: T, delay: Int) extends Delayed {
val time = System.currentTimeMillis + delay
def getDelay(unit: TimeUnit): Long = {
unit.convert(time - System.currentTimeMillis, TimeUnit.MILLISECONDS)
}
def compareTo(o: Delayed): Int = {
val x = o.asInstanceOf[DelayElem[T]].time
if (time < x) -1
else if (time > x) 1
else 0
}
}
// 5秒待て的なDelay要素を登録
val queue = new DelayQueue[DelayElem[Int]]()
queue.offer(new DelayElem(3, 5000))
// 0秒後、3秒後は取れないけど、6秒後は要素が取れる
println(queue.poll())
Thread.sleep(3000)
println(queue.poll())
Thread.sleep(3000)
println(queue.poll())