Hashtblこのページは最後に更新されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。 last mod. 2009-09-10 (木) 16:54:23
module Hashtbl: sig end ハッシュテーブルとハッシュ関数です。 ハッシュテーブルはハッシュ化された連想テーブルです。内部置き換え式です。 Generic interfacetype ('a, 'b) t 型 'a から型 'b へのハッシュテーブルの型です。 val create : int -> ('a, 'b) t Hashtbl.create n は空のハッシュテーブルを新しく作って返します。初期サイズは n です。効率を考えると、n はハッシュテーブルに入れる要素の予想数オーダになっているとよいです。テーブルは必要に応じて大きくなりますから、n は初期の見当にすぎません。 val clear : ('a, 'b) t -> unit ハッシュテーブルを空にします。 val add : ('a, 'b) t -> 'a -> 'b -> unit Hashtbl.add tbl x y はテーブル tbl に x から y への束縛を追加します。 元からあった x の束縛は取り除かれず、隠れるだけです。つまり、あとで Hashtbl.remove tbl x を行うと、元からあった x の束縛が (あればですが) 再度有効になります (連想リストと同じ振る舞いです) 。 val copy : ('a, 'b) t -> ('a, 'b) t 与えられたハッシュテーブルのコピーを返します。 val find : ('a, 'b) t -> 'a -> 'b Hashtbl.find tbl x はテーブル tbl で現在 x が束縛しているものを返します。該当する束縛がない場合は例外 Not_found を発生します。 val find_all : ('a, 'b) t -> 'a -> 'b list Hashtbl.find_all tbl x はテーブル tbl で x が束縛しているすべてのデータをリストにして返します。 先頭に現在の束縛、それから元からあった束縛、というように、テーブルに追加された順の逆順で返します。 val mem : ('a, 'b) t -> 'a -> bool Hashtbl.mem tbl x はテーブル tbl に x の束縛があるかどうか検査します。 val remove : ('a, 'b) t -> 'a -> unit Hashtbl.remove tbl x はテーブル tbl から現在の x の束縛を取り除きます。 元からあった束縛があれば再度有効になります。 テーブル tbl に x の束縛がなかったら何もしません。 val replace : ('a, 'b) t -> 'a -> 'b -> unit Hashtbl.replace tbl x y はテーブル tbl で現在の x の束縛を x から y への束縛と置き換えます。テーブル tbl に x の束縛がなかったら、x から y への束縛を追加します。機能的には Hashtbl.remove tbl x したあと Hashtbl.add tbl x y するのと等価です。 val iter : ('a -> 'b -> unit) -> ('a, 'b) t -> unit Hashtbl.iter f tbl はテーブル tbl のすべての束縛を関数 f に適用します。f は第一引数にキーを、第二引数に連想値を取ります。どの束縛からどういう順に f を適用されるかは規定されていません。それぞれの束縛は 1 回ずつ関数 f に与えられます。 val fold : ('a -> 'b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c Hashtbl.fold f tbl init は (f kN dN ... (f k1 d1 init)...) を評価します。k1 ... kN はテーブル tbl にあるすべての束縛のキーで、d1 ... dN は連想値です。 どの束縛からどういう順に f を適用されるかは規定されていません。それぞれの束縛は 1 回ずつ関数 f に与えられます。 Functorial interfacemodule type HashedType = sig end functor Hashtbl.Make の入力 signature です。 module type S = sig end Hashtbl.Make の出力 signature です。 module Make: functor (H : HashedType) -> sig end ハッシュテーブル構造の実装を生成する functor です。 The polymorphic hash primitiveval hash : 'a -> int Hashtbl.hash x はどんあ型のどんな値でも正整数に関連づけます。x = y ならば hash x = hash y であることが保証されています。さらに、hash はたとえ循環構造を与えられても必ず停止します。 val hash_param : int -> int -> 'a -> int Hashtbl.hash_param n m x は x のハッシュ値を計算します。このハッシュ値は hash と同じ特性を持ちます。n と m というパラメータが 2 つ増えていて、ハッシングを細かくコントロールできます。ハッシングは x の構造を深さ優先、右から左へ縦断してスキャンします。意味のあるノードを n 回スキャンするか、意味のあるないに関わらずノードを m 回スキャンしたら停止します。意味のあるノードとは、整数、浮動小数点小数、文字列、文字、真偽値、定コンストラクタです。m と n を大きくすると、最終的に出力されるハッシュ値を計算する情報として、より多くのノードを取り入れることになり、衝突が発生する可能性は減ると思われます。しかしハッシングに時間がかかるようになります。m と n のパラメータは正確さと速度のトレードオフを決定します。 |