今回は高速な探索アルゴリズムの一つである「ハッシュ法」を取り上げます。OCaml には標準ライブラリにハッシュ法を実装したモジュール Hashtbl がありますが、今回は OCaml の勉強ということで、あえてハッシュ法のプログラムを作ってみることにします。なお、ハッシュ法は拙作のページ Algorithms with Python:「ハッシュ法」で詳しく説明しています。よろしければ参考にしてください。
ハッシュ法は、コンパイラやインタプリタなどで予約語や関数名、変数名などの管理に使われている方法です。また、Perl, Python, Ruby など連想配列 (辞書) をサポートしているスクリプト言語がありますが、その実装にはハッシュ法が使われています。
ハッシュ法は「ハッシュ表 (hash table)」と呼ばれるデータを格納する配列と、データを数値に変換する「ハッシュ関数 (hash function)」を使います。たとえば、ハッシュ表の大きさを N とすると、ハッシュ関数はデータを 0 から N - 1 までの整数値に変換します。この値を「ハッシュ値 (hash value)」と呼びます。ハッシュ値はハッシュ表の添字に対応し、この位置にデータを格納します。つまり、ハッシュ関数によってデータを格納する位置を決める方法がハッシュ法なのです。
ハッシュ法で不特定多数のデータを扱う場合、異なるデータでもハッシュ値が等しくなる可能性があります。これを「ハッシュ値の衝突 (collision)」といいます。つまり、データをハッシュ表に登録しようとしても、すでにデータが格納されていることがあるわけです。この場合、2 つの解決方法があります。
第 1 の方法は空いている場所を探して、そこにデータを格納する方法です。次の図を見てください。
ハッシュ表 ハッシュ表
┌───┐ ┌───┐
│ ／ │ │ ／ │
├───┤ ├───┤
│ Ａ │ │ Ａ ┼─┐ 衝突 (E)
├───┤ ├───┤ │
│ ／ │ │ Ｅ │←┘
├───┤ ├───┤
│ ／ │ │ ／ │
├───┤ ├───┤
│ Ｂ │ │ Ｂ ┼─┐ 衝突 (D, F)
├───┤ ├───┤ │
│ ／ │ │ Ｄ ┼←┤ 衝突 (F)
├───┤ ├───┤ │
│ Ｃ │ │ Ｃ ┼←┤ 衝突 (F)
├───┤ ├───┤ │
│ ／ │ │ Ｆ │←┘
└───┘ └───┘
／ ： 空き場所
(1) A, B, C を登録 (2) D, E, F を登録
図 1 : ハッシュ法 (オープンアドレス法)
ハッシュ値が衝突した場合、異なるハッシュ関数を用いてハッシュ値を再計算し、データを格納する場所を決めます。これを空いている場所が見つかるまで繰り返します。この場合、データの最大数はハッシュ表の大きさに制限されます。
第 2 の方法はハッシュ表に複数のデータを格納することです。このとき、よく利用されるデータ構造が連結リストです。次の図を見てください。
ハッシュ表
┌───┐
│ ／ │
├───┤ ┌─┬─┐ ┌─┬─┐
│ ・─┼─→│Ｅ│・┼→│Ａ│／│
├───┤ └─┴─┘ └─┴─┘
│ ／ │
├───┤
│ ／ │
├───┤ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│ ・─┼─→│Ｆ│・┼→│Ｄ│・┼→│Ｂ│／│
├───┤ └─┴─┘ └─┴─┘ └─┴─┘
│ ／ │
├───┤ ┌─┬─┐
│ ・─┼─→│Ｃ│／│
├───┤ └─┴─┘
│ ／ │
└───┘
／ ： 終端
図 2 : ハッシュ法 (チェイン法)
ハッシュ表からデータを探索する場合、まずハッシュ値を求め、そこに格納されている連結リストの中からデータを探索します。ただし、ハッシュ値の衝突が頻繁に発生すると連結リストが長くなるため、データの探索に時間がかかるようになります。したがって、効率よく探索を行うためには、ハッシュ表の大きさとハッシュ関数の選択が重要になります。なお、連結リストの代わりに二分探索木を使う方法もあります。
これら 2 つの方法の名前ですが、参考文献によって呼び方が異なっていて統一されていません。このドキュメントでは参考文献『Ｃプログラマのためのアルゴリズムとデータ構造』に従って、第 1 の方法を「オープンアドレス法 (open addressing)」、第 2 の方法を「チェイン法 (chaining)」と呼ぶことにします。
今回はチェイン法でプログラムを作ってみましょう。ハッシュ表にはキーとそれに対応する値を格納することにします。ハッシュ法の性能は、ハッシュ関数によって大きく左右されます。このため、データに適したハッシュ関数を作るのが普通です。そこで、ハッシュ表の大きさ、ハッシュ関数、データの比較関数はストラクチャにまとめておき、ファンクタに渡すことにします。
最初に、ファンクタに渡すストラクチャ用のシグネチャ ITEMTYPE を定義します。次のリストを見てください。
リスト 4 : シグネチャの定義
module type ITEMTYPE =
sig
type t
val hash_size : int
val hash_func : t -> int
val equal : t -> t -> bool
end
type t がキーとなるデータ型、hash_size がハッシュ表の大きさ、hash_func がハッシュ関数、equal がデータが等しいかチェックする述語です。これらの変数と関数を使ってファンクタを定義します。次のリストを見てください。
リスト 5 : ファンクタの定義
module MakeHash (Item: ITEMTYPE) :
sig
type t = Item.t
type 'a hash
val create : unit -> 'a hash
val insert : t -> 'a -> 'a hash -> unit
val search : t -> 'a hash -> 'a option
val delete : t -> 'a hash -> unit
val iter : (t -> 'a -> unit) -> 'a hash -> unit
end
= struct
(* 型の定義 *)
type t = Item.t
type 'a pair = {key : t; mutable value : 'a}
type 'a hash = Hash of 'a pair list array
(* リストから pair を探す *)
let rec find k = function
[] -> None
| ({key = x; value = _} as p) :: _ when Item.equal k x -> Some p
| _ :: xs -> find k xs
(* ハッシュ表の位置を求める *)
let position key = (Item.hash_func key) mod Item.hash_size
(* 生成 *)
let create () = Hash (Array.make Item.hash_size [])
(* 挿入 *)
let insert k v (Hash (table)) =
let n = position k in
match find k table.(n) with
None -> table.(n) <- {key = k; value = v} :: table.(n)
| Some p -> p.value <- v
(* 探索 *)
let search k (Hash (table)) =
let n = position k in
match find k table.(n) with
None -> None
| Some p -> Some p.value
(* 削除 *)
let delete k (Hash (table)) =
let n = position k in
match find k table.(n) with
None -> raise Not_found
| Some p -> table.(n) <- List.filter (fun x -> x <> p) table.(n)
(* 巡回 *)
let iter f (Hash (table)) =
for n = 0 to Item.hash_size - 1 do
List.iter (fun {key = k; value = v} -> f k v) table.(n)
done
end
最初に type でキーとなるデータ型 t を Item.t と宣言します。値は型変数 'a で表します。キーと値はレコード {key : t; mutable value : 'a} に格納し、それをデータ型 'a pair とします。すると、ハッシュ表のデータ型は 'a hash = Hash of 'a pair list array と定義することができます。
関数 find はキー k と等しい pair をリストから探します。キーの比較は Item.eaual を使います。見つけたレコードは option に格納して返します。関数 position はキー key からハッシュ表の位置を計算します。Item.hash_func で key のハッシュ値を求め、それと Item.hash_size の剰余を計算するだけです。この 2 つの関数は非公開とします。
関数 create はハッシュ表を生成します。Array.make で大きさ Item.hash_size の配列を生成するだけです。初期値は空リストになります。
データの挿入は関数 insert で行います。引数 k がキー、v が値、table がハッシュ表です。position でハッシュ表の位置 (添字) を求めます。そして、find で k と等しい pair を探します。見つからない場合はリストの先頭にレコードを追加します。見つかった場合は、レコードのフィールド value の値を v に書き換えます。
データの探索は関数 search で行います。find で k と等しい pair を探して、見つからない場合は None を返し、見つけた場合はフィールド value の値を option に格納して返します。
データの削除は関数 delete で行います。find で k と等しい pair を探します。見つからない場合は例外 Not_found を送出します。見つけた場合はその pair を削除します。この処理は List.filter を使うと簡単です。
関数 iter はハッシュ表に格納された全要素に対して関数 f を適用します。for ループでハッシュ表の要素 (リスト) を取り出し、List.iter でリストに格納されているレコードを取り出します。あとは関数 f にキー k と値 v を渡して呼び出すだけです。
次はファンクタに渡すストラクチャを定義しましょう。格納するデータは文字列とします。次のリストを見てください。
リスト 6 : ストラクチャの定義
module StringItem = struct
type t = string
let hash_size = 199
let hash_func key =
let rec string_hash n a =
if String.length key = n then a
else string_hash (n + 1) (a + int_of_char key.[n])
in
string_hash 0 0
let equal x y = x = y
end
module StringHash = MakeHash(StringItem)
ストラクチャ名は StringItem としました。ハッシュ表の大きさは適当でもいいのですが、参考文献『Ｃ言語による最新アルゴリズム事典』によると 『この値が素数だと安心である』 とのことなので、このプログラムでは 199 としました。
今回はハッシュ法の例題ということで、ハッシュ値の計算は簡単な方法を採用します。関数 hash_func は文字コードをすべて加算した値を返します。その値を hash_size で割った余りがハッシュ値になりま。これで、0 から 198 までのハッシュ値を生成することができます。
関数 equal は等値演算子 = でデータを比較するだけです。これで、ストラクチャの定義は終わりです。最後に、ファンクタ MakeHash に StringItem を渡してストラクチャ StringHash を生成します。実際に StringHash を生成すると次のように表示されます。
module StringHash :
sig
type t = StringItem.t
type 'a hash = 'a MakeHash(StringItem).hash
val create : unit -> 'a hash
val insert : t -> 'a -> 'a hash -> unit
val search : t -> 'a hash -> 'a option
val delete : t -> 'a hash -> unit
val iter : (t -> 'a -> unit) -> 'a hash -> unit
end
それでは簡単な実行例を示します。
# open StringHash;; # let a = create ();; val a : 'a StringHash.hash = <abstr> # insert "abc" 10 a;; - : unit = () # insert "def" 20 a;; - : unit = () # insert "ghi" 30 a;; - : unit = () # search "abc" a;; - : int option = Some 10 # search "ab" a;; - : int option = None # delete "abc" a;; - : unit = () # search "abc" a;; - : int option = None # iter (fun k v -> print_string (k ^ " "); print_int v; print_newline ()) a;; def 20 ghi 30 - : unit = ()
正常に動作していますね。
ハッシュ法はデータを高速に検索できる優れたアルゴリズムです。データを検索するだけならば、二分探索木よりもハッシュ法が優れています。ですが、二分探索木にはハッシュ法にはない長所があります。二分探索木はデータの大小関係で構成されているので、左の木をたどることで最小値を、右の木をたどることで最大値を簡単に求めることができます。ハッシュ法で最大値や最小値を求めるには、すべてのデータを調べなければいけません。また、二分探索木では通りがけ順でデータを出力すれば、ソートされた結果を得ることができます。データの大小関係を処理する場合は、ハッシュ法よりも二分探索木を選ぶといいでしょう。
最後に、OCaml のモジュール Hashtbl (ハッシュ表) の基本的な使い方を簡単に説明します。ハッシュ表の生成には関数 create を使います。
Hashtbl.create init_size
引数 init_size はハッシュ表の初期サイズを指定します。これは適当な値でもかまいません。足りなくなったら自動的に拡張されます。
キーの有無は関数 mem でチェックすることができます。値の取得は関数 find や find_opt で、削除は関数 remove で行うことができます。簡単な使用例を示します。
# let h0 = Hashtbl.create 199;;
val h0 : ('_weak1, '_weak2) Hashtbl.t = <abstr>
# List.iter (fun (k, v) -> Hashtbl.add h0 k v) [("foo", 10); ("bar", 20); ("baz", 30)];;
- : unit = ()
# Hashtbl.mem h0 "foo";;
- : bool = true
# Hashtbl.mem h0 "foo1";;
- : bool = false
# Hashtbl.find_opt h0 "foo";;
- : int option = Some 10
# Hashtbl.find_opt h0 "foo1";;
- : int option = None
# Hashtbl.remove h0 "foo";;
- : unit = ()
# Hashtbl.mem h0 "foo";;
- : bool = false
詳しい説明は OCaml のマニュアル Module Hashtbl をお読みくださいませ。
(*
* hash.ml : ハッシュ法
*
* Copyright (C) 2008 Makoto Hiroi
*)
(* シグネチャ *)
module type ITEMTYPE =
sig
type t
val hash_size : int
val hash_func : t -> int
val equal : t -> t -> bool
end
(* ファンクタ *)
module MakeHash (Item: ITEMTYPE) :
sig
type t = Item.t
type 'a hash
val create : unit -> 'a hash
val insert : t -> 'a -> 'a hash -> unit
val search : t -> 'a hash -> 'a option
val delete : t -> 'a hash -> unit
val iter : (t -> 'a -> unit) -> 'a hash -> unit
end
= struct
(* 型の定義 *)
type t = Item.t
type 'a pair = {key : t; mutable value : 'a}
type 'a hash = Hash of 'a pair list array
(* リストから pair を探す *)
let rec find k = function
[] -> None
| ({key = x; value = _} as p) :: _ when Item.equal k x -> Some p
| _ :: xs -> find k xs
(* ハッシュ表の位置を求める *)
let position key = (Item.hash_func key) mod Item.hash_size
(* 生成 *)
let create () = Hash (Array.make Item.hash_size [])
(* 挿入 *)
let insert k v (Hash (table)) =
let n = position k in
match find k table.(n) with
None -> table.(n) <- {key = k; value = v} :: table.(n)
| Some p -> p.value <- v
(* 探索 *)
let search k (Hash (table)) =
let n = position k in
match find k table.(n) with
None -> None
| Some p -> Some p.value
(* 削除 *)
let delete k (Hash (table)) =
let n = position k in
match find k table.(n) with
None -> raise Not_found
| Some p -> table.(n) <- List.filter (fun x -> x <> p) table.(n)
(* 巡回 *)
let iter f (Hash (table)) =
for n = 0 to Item.hash_size - 1 do
List.iter (fun {key = k; value = v} -> f k v) table.(n)
done
end