JavaのHashMap#putAllがバグって仕様よりもメモリを多く消費していた場合があったという話。

JDKのメーリングリストで投げられていましたが、面白かったので共有。

元ネタのメールはこちら。

HashMapとは

前提条件としてHashMapがどういう挙動をしているかがわからないと理解できないので、簡単にHashMapの説明をします。

HashMapはハッシュ表に基づいたMapの実装です。初期値として、初期容量と負荷係数を指定できます。

どんな感じでやっているかというと、初期容量4と負荷係数0.75が指定されていたとすると、内部的には最初は

[null, null, null, null]

という内部表が生成されます。

ここにハッシュコードが7になるAがあるとします。これをA(7)と表します。これは現在の容量が4で、7 mod 4は3になるので、以下のように挿入されます。

[null, null, null, A(7)]

次にB(0)があった場合は、現在の容量が4で、0 mod 4は0になるので、以下のように挿入されます。

[B(0), null, null, A(7)]

次にC(1)は以下のように挿入されます。

[B(0), C(1), null, A(7)]

次にD(2)があった場合はどうなるでしょうか？実はそのままは挿入されません。負荷係数0.75を指定しているため、4つのうち3つまでしか使用されず、それ以上の数の要素数になった場合は内部表はリサイズされます。今回はとりあえず2倍にしておきます。その時にハッシュコードの値ですでに入っている要素の位置は変更され、以下のようになります。

[B(0), C(1), D(2), null, null, null, A(7), null]

という感じになっており、アクセスするときはハッシュ値だけわかれば高速にアクセスできるようになってます。今回、仕様として重要なのは、内部表は実際の要素数よりも大きい数が使われており、仕様として内部表のサイズに負荷係数を掛けたものより多くの要素が入った場合に表の拡張が行われるようになっているということです。

HashMapのインスタンスには、その性能に影響を与える2つのパラメータである初期容量および負荷係数があります。容量はハッシュ表のバケット数であり、初期容量は単純にハッシュ表が作成された時点での容量です。負荷係数は、ハッシュ表がどの程度いっぱいになると、その容量が自動的に増加されるかの基準です。ハッシュ表エントリ数が負荷係数と現在の容量の積を超えると、ハッシュ表のハッシュがやり直され (つまり、内部データ構造が再構築され)、ハッシュ表のバケット数は約2倍になります。

何が起こっていたか

内部表を拡張するかどうかの数値の計算が以下のようになってました。

((float)s / loadFactor) + 1.0F

正しくは以下の通りでは？とのこと。

Math.ceil((float)s / loadFactor)

最初に張り付けたメールには確認するコードが載ってます。JavaのHashMapはJavaDocによると、引数を指定しない場合内部表の初期容量は16、負荷係数は0.75になるので、要素を12個入れた場合は内部表の容量が16でなければおかしいが、putAllを使用して入れた場合は32になるという指摘でした。

よく使われてるライブラリでもコーナーケースでバグが残ってるのは面白いですね。