の4章コレクションにおいて、java.util.Hashtableのハッシュコードから格納しているテーブルのインデックスを計算するアルゴリズムとしてテーブル長の剰余を使用しているとあります。そこで、java.util.Hashtableとjava.util.HashMapについてハッシュコードからテーブルインデックスを算出するロジックを実際のソースコードで調べてみました。
JDK1.6.0b81のソースでは、それぞれ以下のようになっていました。
- java.util.Hashtable
int index = (hash & 0x7FFFFFFF) % table.length
- java.util.HashMap
int i = indexFor(hash, table.length); : static int indexFor(int h, int length) { return h & (length - 1); }
HashMapの方はビット演算の&を使用しています。うーむと思い、lengthの設定を見てみたところ、かならず2のべき乗を取るようになっていました。
なるほど、こうやって剰余計算を非常に高速なビット論理積演算に置き換えているのですね。