Previous  Up  Next

Module Hashtbl


module Hashtbl: sig .. end
ハッシュテーブルとハッシュ関数

ハッシュテーブルはハッシュ関数を使った、破壊的変更のできる対応表です。


汎用インタフェース


type ('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 は y に対する x の束縛をテーブル tbl に追加します。 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 は x が tbl 中で束縛されているか検査します。
val remove : ('a, 'b) t -> 'a -> unit
Hashtbl.remove tbl x は tbl から x の現在の束縛を取り除き、以前の束縛が存在すればそれを復元します。 x が tbl 中で束縛されていなかった場合には何もしません。
val replace : ('a, 'b) t -> 'a -> 'b -> unit
Hashtbl.replace tbl x y は tbl 中の現在の x の束縛を置き換えます。 x が tbl 中で束縛されていなかった場合には x から y への束縛を tbl に追加します。 この関数は機能としては 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 に渡される束縛の順序は未定義です。 ただし、テーブルに同一のキーに対する値が複数ある場合には、追加したのと逆の順番に、すなわち、もっとも最近に追加した束縛が最初に 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 にちょうど一回だけ渡されます。 f に渡される束縛の順序は未定義です。 ただし、テーブルに同一のキーに対する値が複数ある場合には、追加したのと逆の順番に、すなわち、もっとも最近に追加した束縛が最初に f に渡されます。
val length : ('a, 'b) t -> int
Hashtbl.length tbl は tbl 中に存在する束縛の個数を返します。 複数の値に束縛されているキーは複数回数えられます。 つまり、 Hashtbl.length は Hashtbl.iter が第一引数の関数を呼び出す回数を返します。

関数型インタフェース


module type HashedType = sig .. end
Hashtbl.Make ファンクタに対する入力のシグネチャ。 
module type S = sig .. end
Hashtbl.Make ファンクタの出力のシグネチャ。 
module Make: 
functor (H : HashedType) -> S  with type key = H.t
ハッシュテーブルのストラクチャの実装を作成するファンクタ。

多相ハッシュプリミティブ


val hash : 'a -> int
Hashtbl.hash x は正の整数を任意の型の値に対応づけます。 x = y または Pervasives.compare x y = 0 のとき、 hash x = hash y であることが保証されています。 さらに、 hash は循環構造に対しても必ず停止します。
val hash_param : int -> int -> 'a -> int
Hashtbl.hash_param n m x は x について hash と同じ性質のハッシュ値を計算します。 追加の引数 n と m はハッシュ関数をより精確に制御します。 ハッシュ関数は x の構造を深さ優先で、右から左に走査し、 n 個の意味のあるノードに遭遇するか、意味の有無にかかわらず m 個のノードに遭遇すると停止します。 ここでいう意味のあるノードとは、整数、浮動小数点数、文字列、文字、真偽値、定数構成子です。 m と n により大きな値を指定することで、より多くのノードが最終的なハッシュ値の計算に関係することになり、それによってハッシュ値の衝突がより起こりにくくなります。 しかし、計算により時間がかかるようになります。 パラメータ m と n の値は精確さと速度のトレードオフになります。