今回は、JavaのHashMapのパフォーマンスにおいて、その注意点およびパフォーマンスを出すための実装法を話したいです。
システム開発は常に可読性、保守性、パフォーマンスのバランスを取る必要があります。ただ、昨今では、ハードウェアの性能の飛躍的な向上および安価化によって、プログラムの細かいところのパフォーマンス向上よりも、可読性保守性が重視されるようになっています。そのため、可読性保守性が向上できれば、一定のパフォーマンスの犠牲も許容される傾向があります。
HashMapも同様で、一部特殊なケースを除く、ほとんどの場合、利用時のパフォーマンスを意識しなくてもパフォーマンスのボトルネックになることがありません。
ただ、実装上可読性保守性の犠牲がなしで、パフォーマンスのよい実装方もありますので、パフォーマンスの良い実装という意識が常に持つ必要があります。それが習慣になっていれば一番理想です。つまり、特にわざと考慮しなくても自然にパフォーマンスの良い実装となることです。プログラムの品質は求めている業務要件を実現することのように狭義的ではなく、可読性、保守性、パフォーマンスなども含め、広義的なことを考えるべきだと思います。日々の開発の中で、そのような意識を持って、研鑽しながら良い習慣として身に付けることが大事であります。
さて、話は戻りますが、HashMapのパフォーマンスにおいて、その注意点およびパフォーマンスを出すための実装法はなんでしょうか？
まずは、HashMapの以下のコンストラクタを見てみましょう。
public HashMap(int initialCapacity, float loadFactor){}
HashMap生成時のパラメータとして、initialCapacity：初期容量とloadFactor：負荷係数があります。
- 初期容量
- HashMapが内部的にデータを保持するためのテーブル自体のサイズ（デフォルトで16）です。
- 負荷係数
- テーブルがどの程度埋まるとテーブルの拡張を行うかという割合を表したもの（デフォルトで0.75）です。
例えば、デフォルトの場合、初期容量(16)*負荷係数(0.75)=12となるので、*12個目の要素がマップにputされるタイミングで、テーブルの拡張が行われます。
というわけで、要素数がテーブルサイズの現在値に負荷係数を乗じた数になった度にテーブルサイズの拡張が行われ、保持されている要素を拡張後のテーブルに配置しなおされるので、コストがかかります。
それでは、なぜテーブルがいっぱいになってから拡張を行わないのか？そうすれば、拡張回数が少なくなるわけで、パフォーマンスが良くなるのではないか？
理由はテーブルのどの位置にその要素を保持するかの仕組みによるものです。
新しい要素をテーブルにputされる場合、以下の式で保持する位置を計算することとなります。
i = (n - 1) & hash
nはテーブルの現在サイズ、hashはputする要素のキーのハッシュ値、iは(n - 1)とキーのハッシュ値とのビットAND演算で算出したインデックスとなります。
これでわかると思いますが、
- キーが違っても、ハッシュ値が同じになることがあるため、その場合、インデックスが同じになる
- ハッシュ値が違っても、ビットAND演算で算出したインデックスが同じになる
とのことがありえますので、同じインデックスの位置に複数の要素を保持することがあり、それらの要素を別のツリー構造で保持することとなります。
そのため、テーブルがすべて埋まることはほとんどありませんし、ツリー構造に要素の追加、およびツリー構造に保持する要素の検索処理で、インデックスを特定した後に、更にツリー構造への追加または走査が必要となりますので、パフォーマンスが劣化します。
テーブルの初期サイズが大きければ大きいほど、パフォーマンスの劣化を軽減することができるが、その場合、要素を保持しないテーブルの無駄空間が増えることとなりますので、メモリの無駄となります。
つまり、HashMapを利用する場合、初期容量および負荷係数を調整することでパフォーマンスまたは使用するメモリ量に影響を与えることができ、これがHashMap利用時の重要な考慮要素となります。デフォルト値はある意味でパフォーマンスとメモリの使用量のバランスが取れた数値といえますので、冒頭にも話したように普段HashMapを利用する場合、ほとんどデフォルト値のままで問題ありません。
ただ、以下の前提条件が満たせれば、
- HashMapに保持する要素数が最初からわかる
- HashMapのキーの仕組みが自由に決めることができる
パフォーマンス劣化もなく、メモリも無駄がない対応が可能となる。
具体的な対応方法は以下となる。
- 初期容量が保持する予定の要素数にする
- 負荷係数がテーブルの拡張が絶対発生しない数字にする（例えば2）
- キーは最初から作成しておいて、各キーのハッシュ値は0～(要素数―1)までの数値を順にセットする(独自のキークラスを作成＊1)
＊1 独自のキークラスを作成することで余分のメモリが必要となりますが、ここで一旦無視しましょう。
ここまででHashMap利用時のパフォーマンス考慮の話をまとめましたが、本当に言いたいのはHashMapそのものではなく、どんな場合であっても、物事の本質を理解することが大事で、それによって、プログラムもアーキテクチャーも実際のニーズに合わせて最適化することが可能となります。
周@ソフトシンク