Java/Collections/Hash, Linked, Treeの違い

• [ Prev ]
• [ Next ]
• [ Java ]

Javaプログラミングに10年近く携わっていて、今までまじめにHashMap/TreeMap/LinkedHashMapの違いを勉強したことがなかったので、簡単にまとめてみました。Oracle JDK 1.7.0.25 のソースも参照しています。
なお、あんまり学術的に突っ込んで調べてないので、話半分程度に考えて、正確な情報についてはJDKのJavaDocやソースコードを参照してください。

HashMap, HashSet

• キーとなるオブジェクトのhashCode()をハッシュテーブルに振り分けて格納してく実装。
• JDK 1.7.0.25の内部実装としては、hashCode()を元にして配列アクセス出来る"table"が用意されてる。配列アクセス＝Javaの配列として用意されていて、どの配列要素にも一定のコスト（あんまり厳密に書いてないので、パフォーマンスというか感覚的な話）でアクセス出来る。hashCode()の計算量に引きずられるのかな？
• デフォルトのコンストラクタではそれほど広大なハッシュテーブルを用意しているわけではなく、埋まり具合に応じて拡張・再構築される。一応、ハッシュテーブルの初期容量と、拡張・再構築を実施する埋まり具合を指定するコンストラクタも用意されている。
• HashSetは内部的にはHashMapをそのまま使っていて、単に値としてダミーのオブジェクトを入れて、キーとしての操作だけをSetインターフェイスの実装として公開してるようです。

HashMapでput()にかかる時間、get()にかかる時間を見てみるサンプル：

• https://github.com/msakamoto-sf/javasnack/blob/master/src/main/java/javasnack/snacks/perfs/map/PerfHashMapFinePutGet.java
  • put()では、最初から14回目位で若干時間がかかってます。バケット数16, スレッショルド 0.75 に設定してますので、多分ココらへんでハッシュテーブルの拡張と再構築が発生してると思われます。以降も、時々時間がかかるput()があります。
  • 全体傾向としてはput()もget()も大体コンスタントな計算量になってるようです。ただ、若干後ろの方にいくとハッシュテーブルのアクセス時間が伸びるのか、なんとなーく時間がかかり気味な感じもします。

TreeMap, TreeSet

• 赤黒木・・・つまり平衡2分探索木の一種で、それを使ってソートされた状態でキー（と値）を保存出来る。
• キーを指定する containsKey(), get(), put(), remove() メソッドは、使用されているアルゴリズムの特性から時間コストはlog(n)になる・・・つまり、平衡2分探索になりますよーということらしいです・・・。
• やはり特徴としては、要素を追加すると自動的に自然順序 or コンストラクタで指定するComparatorによってソートされ、iteratorなどで要素を取り出すときもソートされた順序で取り出される点でしょうか。
• 赤黒木の実装はそれなりに大変で、JDK 1.7.0.25 の内部実装でもコメント含めておよそ2,400行になっています。HashMapがおよそ1,100行ですから、その2倍のソースコードが必要になっています。
• 内部の赤黒木に対して複雑な操作が必要になってくるため、要素の追加ではHashMapより計算量が多くなってしまっています。
• HashSetと同様、TreeSetも内部的にはTreeMapを使っていて、単に値としてダミーのオブジェクトを入れて、キーとしての操作だけをSetインターフェイスの実装として公開してるようです。

参考：

• 赤黒木 - Wikipedia
  • http://ja.wikipedia.org/wiki/%E8%B5%A4%E9%BB%92%E6%9C%A8
• Red-Black Tree by Java -- これで分かった赤黒木
  • http://www.moon.sannet.ne.jp/okahisa/rb-tree/

TreeMapでput()にかかる時間、get()にかかる時間を見てみるサンプル：

• https://github.com/msakamoto-sf/javasnack/blob/master/src/main/java/javasnack/snacks/perfs/map/PerfTreeMapFinePutGet.java
  • put()は全体的に時間が凸凹になってます。get()は若干の偏りがあるものの、そんなに大きな凸凹はありません。恐らく、put()により内部の赤黒木の更新処理でばらつきが出てしまっていると思われます。
  • 全体的に、HashMapよりも時間はかかってます。

LinkedHashMap, LinkedHashSet

• HashMapですと、hashCode()を元に順番が並べ替えられてしまいますが、LinkedHashMapを使うと、要素を追加した順番で値を取り出すことが出来ます。
• 仕掛けとしては要素（エントリ）に対して二重リンク・リストを保持しておき、Iteratorなどで取り出すときに二重リンク・リストを辿るようにしている。
• なお、要素を追加した順序ではなく、要素に「アクセス」(get()含む)した順を保持するよう指定できるコンストラクタが提供されている。これを使うと、単にget()するだけでも、要素が入っていればアクセス順として内部のリンクリストの構成が更新される。
• LinkHashSetについては、上と同様、LinkedHashMapを使って実現してます。

LinkedHashMapでput()にかかる時間、get()にかかる時間を見てみるサンプル：

• https://github.com/msakamoto-sf/javasnack/blob/master/src/main/java/javasnack/snacks/perfs/map/PerfLinkedHashMapFinePutGet.java
  • 傾向としてはHashMapの時とほぼ同じっぽい感じです。
  • ただ、リンクリストの操作が入っている分、HashMapより若干時間がかかってるかな・・・程度です。TreeMapよりは軽いです。

Java配列, ArrayList, LinkedList

ちょっと脇道にそれますが、リスト管理の仕組みとしてJavaの配列, ArrayList, LinkedListを比べてみました。

Java配列のデモ：

• https://github.com/msakamoto-sf/javasnack/blob/master/src/main/java/javasnack/snacks/perfs/list/PerfJavaArrayFinePutGet.java
  • やはり圧倒的に速く、ナノ秒の世界で値のset, getが行われてます。

ArrayListのデモ：

• https://github.com/msakamoto-sf/javasnack/blob/master/src/main/java/javasnack/snacks/perfs/list/PerfArrayListFinePutGet.java
  • 初期容量を20に設定しています。そのため、20個位要素を追加した後の追加では、容量を増やすために若干時間がかかってます。
  • 内部的には配列なだけあり、put()もget()もコンスタントに速いです。

LinkedListのデモ：

• https://github.com/msakamoto-sf/javasnack/blob/master/src/main/java/javasnack/snacks/perfs/list/PerfLinkedListFinePutGet.java
  • リンクリストによるListの実装になります。配列要素による管理はしてないため、初期容量がどうのこうのとか、容量が足りなくなった場合の拡張が～とかのコストがありません。そのため、put()の時間がかなりコンスタントになっています。
  • また、面白いのがget()の特性で、アクセスするindexが全体サイズで前から辿ったほうが速いか、後ろから辿ったほうが速いかチェックされています。そのため、0-499までのindexにアクセスしてみると真ん中の0 -> 250までは徐々に時間がかかってくるんですが、250 -> 499までは徐々に時間が減ってきてます。恐らく250以降になってくると、最後からたどっているためと思われます。

簡単なベンチマークプログラムを組んでみますと、HashMap/TreeMap/LinkedHashMapの実装による差異が目で見えるようになり、面白かったです。
今回は時間だけに着目したベンチマークプログラムを作ってみましたが、メモリ容量に着目してみるのも面白いかもしれません。

• [ Prev ]
• [ Next ]
• [ Java ]