この章ではリストから一歩進み,
ハッシュを実現できる木構造
関数プログラミングと
もちろん,
- 注1)
- Oはアルゴリズムの効率を表す表記です。効率が良い順に,
O(1), O(log N), O(N), O(N log N), O(N2)となります。 - 注2)
- 初期化のみで更新しなくてよいのであれば,
平均O(1)のハッシュが作れます。
木構造の特徴
木構造は永続データとして利用できます。図1を見てください。左の探索木に要素oを挿入すると,
木構造を使えば,
ハッシュのAPI
これから赤黒木を用いてハッシュを実装します。まず,
empty :: Hash k v
insert :: Ord k => (k,v) -> Hash k v -> Hash k v
fromList :: Ord k => [(k,v)] -> Hash k v
search :: Ord k => k -> Hash k v -> Maybe v
ハッシュの型はHash k vとします。キーの型がkで,
empty──空のハッシュ
emptyは空のハッシュを表します。emptyはO(1)です。
insert──要素を追加する
insertは,Ord k =>
というのは,
まだ実装していませんが,
> empty
Leaf
> insert (1,'a') empty
Node B Leaf (1,'a') Leaf
返ってくる値は赤黒木のリテラル表現ですが,
> insert (2,'b') (insert (1,'a') empty)
Node B Leaf (1,'a') (Node R Leaf (2,'b') Leaf)
fromList──要素をまとめて登録する
上記の例のようにinsertを何回も使うのは面倒なので,
> fromList [(1,'a'),(2,'b')]
Node B Leaf (1,'a') (Node R Leaf (2,'b') Leaf)
search──要素を検索する
ハッシュを検索するには関数searchを使います。searchはO(log N)です。
> let hash = fromList [(1,'a'),(2,'b')]
> search 1 hash
Just 'a'
> search 3 hash
Nothing
ハッシュにキーが格納されている場合は