Previous  Up  Next

Module Hashtbl


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

ハッシュテーブルはハッシュ化された連想テーブルです。内部置き換え式です。



Generic interface



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 はテーブル 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 interface 


module 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 primitive 


val 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 のパラメータは正確さと速度のトレードオフを決定します。