JavaのHashMapの実装を眺める会①

HashMapってhashCodeで計算したハッシュからキーと値を引ける構造があって、ハッシュから値を引けるから早い、みたいな理解があって、あとはhashCodeがぶつかったらequalsの結果が等しいかチェックしてる、みたいな理解だったんだけどそもそも「ハッシュからキーを引ける構造」ってなんなん?となったのでHashMapのコードを見ている。そして今のところ全然わからん。

http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java

HashMap$putを見る

putするときにハッシュを作り直してるが何をしたい?

HashMap$hashのコメントを見る

http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java#l320 この辺りのコメントを見ているが全然わからん。

以下よくわからんまま訳したやつ。訳以外は🍙をつけている。


key.hashCode()を計算し、ハッシュの高位ビットを低位に持ってきた値との排他的倫理和を計算します。

🍙こんなん

hashCode():1001
h>>>16    :0010
hash      :1011

テーブルは2の冪でマスクされた値を使うので、カレントのマスクよりも上のビットだけが異なるハッシュの組み合わせは常に衝突するためです。

🍙https://ja.wikipedia.org/wiki/マスク_(情報工学)#2の冪の剰余

(よく知られた例は、小さなテーブル内の連続したFloatのキーのセットです。)

  • 🍙カレントのマスク?
  • 🍙例がわからん

そのため、高位ビットの影響を下位に展開する変換を行います。これに速度、有用性、ビット展開のトレードオフがあります。

  • 🍙ビット展開?散らばり具合の話でいい?

多くの一般的なハッシュの組み合わせは、すでに合理的に分散されています。(そのため拡散による利益をえません) そして、binsに置ける衝突の大きな集合をハンドルするために複数のツリーを利用するので、体系的な損失を減らすための最も効率的な方法のいくつかのシフトされたビットのXORを計算します。 加えて、テーブル境界のためインデックスの計算に使われない高位ビットの影響を組み込むことができます。

  • 🍙全然わからん

そうした方が効率が良いからそうしているらしいということくらいしかわからんけど次はそのままputを見てみる。