Scalaのmutable.HashMapとOpenHashMapの違い

はじめに

Scalaの標準ライブラリを漁っていたら、OpenHashMapなるものを見つけたのでScalaのソースコード読んでみた。

結論から言うとOpenHashMapってOpenAddressのHashMapなんだよーっていう話。

前提知識

Scalaの場合、実はimmutable.HashMapとmutable.HashMapの実装が異なっている。

immutable.HashMapはTrieTreeで実装されている一方で、mutable.HashMapは一般的なHashTableを使って実装されている。TrieTreeは詳しくないのでググれ。（お前モナーって言われそう）

OpenHashMap

https://github.com/scala/scala/blob/v2.10.2/src/library/scala/collection/mutable/OpenHashMap.scala

Searchの主アルゴリズムはOpenHashMap.scalaのdef findIndexを見れば理解できる。tableのindexを規則に従って回して、空いているのがあればそこに挿入しているのが分かる。Open Addressの一種とTwitterで教えてもらった。

HashMap

実体はHashTable.scalaで実装されている。

https://github.com/scala/scala/blob/v2.10.2/src/library/scala/collection/mutable/HashTable.scala

Searchの主なアルゴリズムはfindEntryにある。entryのnext呼び出してるし、LinkedListみたいなEntryと思われる（Entryの実装がどこにあるか最後まで分からなかった）
→下のコメントにもありますがHashEntryですね。原始的なLinkedListと考えて間違いないです。

おまけ

HashTableは大変優秀なアルゴリズムなんだけど、Hashが被ったらどうするよ、ってのは割と永遠の課題で、色々な手法が提案されてる。ってのがここ見ると分かりやすい。

http://www.interdb.jp/techinfo/algorithm/hash.html

つまりHashMapはChain型、OpenHashMapはOpen Address型の、典型的実装例ということだろうか。

だからと言って、パフォーマンスにどう影響があるのかはイマイチ分かってない。