HAMT(Hash Array Mapped Trie) - sileのブログ『Ideal Hash Trees』*1という論文を(必要なところだけ、だいたい)読み終わったので、そのメモ等。 概要 AMT(Array Mapped Trie)という基盤的なデータ構造を使って、ideal(nearly ideal)なHash Treesを作ろう、というような話。 AMTの応用例として、以下のようなものが説明されている。 Hash Array Mapped Trie(HAMT) ハッシュマップ 各種操作がO(1) ハッシュテーブルの初期サイズを(あまり)気にする必要がない 要素が増えた場合のリサイズのコストが小さい*2 リサイズ不要な実装も可能だがその場合はO(log N)に。※ Nは要素数。今回の実装はこっち。 成功検索時、キーの比較は一回しか生じない ただし、キーのハッシュ値の計算処理は(異なるハッシュ関数で)複数回行われることがある。 Clojureの組み込みのハ
