Hashtbl

このページは最後に更新されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

Chapter 20 標準ライブラリ

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