お気楽 Standard ML of New Jersey 入門

はじめに

今回は高速な探索アルゴリズムの一つである「ハッシュ法」を取り上げます。最初にハッシュ法を簡単に説明します。ハッシュ法を理解されている方は読み飛ばしてもらってかまいません。

●ハッシュ法とは？

ハッシュ法は、コンパイラやインタプリタなどで予約語や関数名、変数名などの管理に使われている方法です。また、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 を登録

    図 : ハッシュ法 (オープンアドレス法)

ハッシュ値が衝突した場合、異なるハッシュ関数を用いてハッシュ値を再計算し、データを格納する場所を決めます。これを空いている場所が見つかるまで繰り返します。この場合、データの最大数はハッシュ表の大きさに制限されます。

第 2 の方法はハッシュ表に複数のデータを格納することです。このとき、よく利用されるデータ構造が連結リストです。次の図を見てください。

   ハッシュ表
   ┌───┐   
   │  ／  │   
   ├───┤    ┌─┬─┐  ┌─┬─┐
   │  ・─┼─→│Ｅ│・┼→│Ａ│／│
   ├───┤    └─┴─┘  └─┴─┘
   │  ／  │   
   ├───┤   
   │  ／  │   
   ├───┤    ┌─┬─┐  ┌─┬─┐  ┌─┬─┐
   │  ・─┼─→│Ｆ│・┼→│Ｄ│・┼→│Ｂ│／│  
   ├───┤    └─┴─┘  └─┴─┘  └─┴─┘
   │  ／  │   
   ├───┤    ┌─┬─┐
   │  ・─┼─→│Ｃ│／│
   ├───┤    └─┴─┘
   │  ／  │   
   └───┘   

       ／ ： 終端

        図 : ハッシュ法 (チェイン法)

ハッシュ表からデータを探索する場合、まずハッシュ値を求め、そこに格納されている連結リストの中からデータを探索します。ただし、ハッシュ値の衝突が頻繁に発生すると連結リストが長くなるため、データの探索に時間がかかってしまいます。効率よく探索を行うためには、ハッシュ表の大きさとハッシュ関数の選択が重要になります。連結リストの代わりに二分探索木を使う方法もあります。

これら 2 つの方法の名前ですが、参考文献によって呼び方が異なっていて統一されていません。このドキュメントでは参考文献『Ｃプログラマのためのアルゴリズムとデータ構造』に従って、第 1 の方法を「オープンアドレス法 (open addressing)」、第 2 の方法を「チェイン法 (chaining)」と呼ぶことにします。

●プログラムの作成

今回はチェイン法でプログラムを作ってみましょう。ハッシュ法の性能は、ハッシュ関数によって大きく左右されます。このため、データに適したハッシュ関数を作るのが普通です。そこで、ハッシュ表の大きさ、ハッシュ関数、データの比較関数はストラクチャにまとめておき、ファンクタに渡すことにします。

最初に、ファンクタに渡すストラクチャ用のシグネチャ HASHITEM を定義します。次のリストを見てください。

リスト : シグネチャの定義

signature HASHITEM = sig
  type item
  val size : int
  val hash_func : item -> int
  val equal : item * item -> bool  
end

size がハッシュ表の大きさ、hash_func がハッシュ関数、equal がデータが等しいかチェックする述語です。これらの変数と関数を使ってファンクタを定義します。次のリストを見てください。

リスト : ファンクタの定義

functor makeHash(Item: HASHITEM) = struct
  (* データ型の定義 *)
  datatype 'a hash = Hash of 'a list array

  (* ハッシュ表の生成 *)
  fun create () = Hash(Array.array(Item.size, nil: Item.item list))  

  (* データの探索 *)
  fun search(k, Hash table) =
    let
      val n = Item.hash_func k
      val xs = Array.sub(table, n)
    in
      List.find (fn x => Item.equal(x, k)) xs
    end

  fun member(k, ht) = isSome (search(k, ht))

  (* データの挿入 *)
  fun insert(k, Hash table) =
    let
      val n = Item.hash_func k
      val xs = Array.sub(table, n)
    in
      if List.exists (fn x => Item.equal(x, k)) xs then ()
      else Array.update(table, n, k::xs)
    end

  (* データの削除 *)
  fun delete(k, Hash table) =
    let
      val n = Item.hash_func k
      val xs = Array.sub(table, n)
    in
      Array.update(table, n, List.filter (fn x => not(Item.equal(x, k))) xs)
    end
end

最初に datatype でハッシュ表のデータ型 'a hash を定義します。配列をそのまま使うのではなく、ハッシュ表を表すデータ型を定義した方がよいでしょう。関数 create でハッシュ表を生成します。大きさ は Item.size で、初期値は空リスト (nil) になります。

データの探索は関数 search で行います。ハッシュ関数 hash_func でハッシュ値 n を求め、ハッシュ表 table からリスト xs を取り出します。そして、関数 find で k と等しいデータを探します。データの比較には関数 equal を使います。関数 find は option 型を返しますが、関数 member はデータの有無を bool (true, false) で返します。

データの挿入は関数 insert で行います。ハッシュ値 n をリスト xs を求める処理は search と同じです。まず、関数 exists で同じデータがあるかチェックします。もし、同じデータがあれば何もせずにユニットを返します。そうでなければ、k をリスト xs の先頭に追加します。そして、ハッシュ表 table を関数 update で更新します。

データの削除は関数 delete で行います。ハッシュ値 n をリスト xs を求める処理は insert と同じです。あとは List.filter を使って data と等しい要素を削除し、その結果をハッシュ表 table にセットするだけです。

●ハッシュ関数の作成

次はファンクタに渡すストラクチャを定義しましょう。格納するデータは文字列とします。次のリストを見てください。

リスト : ストラクチャの定義

structure StringItem: HASHITEM = struct
  type item = string
  val size = 199
  fun hash_func x = (foldr (fn(a, b) => ord(a) + b) 0 (explode x)) mod size  
  fun equal(a, b) = a = b
end

structure StringHash = makeHash(StringItem)

ストラクチャ名は StringItem としました。ハッシュ表の大きさは適当でもいいのですが、参考文献『Ｃ言語による最新アルゴリズム事典』によると 『この値が素数だと安心である』 とのことなので、このプログラムでは 199 としました。

今回はハッシュ法の例題ということで、ハッシュ値の計算は簡単な方法を採用します。関数 hash_func は文字コードを全て加算し、その値を size で割った余りをハッシュ値としています。これで、0 から 198 までのハッシュ値を生成することができます。

SML/NJ には、文字を表す「文字型 (char)」というデータ型があります。c を文字とすると、文字型は #"c" で表します。SML/NJ には string を char list に変換する関数 explode と、char list を string に変換する関数 implode が用意されています。簡単な例を示します。

- explode "foo";
val it = [#"f",#"o",#"o"] : char list

- implode it;
val it = "foo" : string

char を int に変換する関数が ord で、int を char に変換する関数が chr です。簡単な例を示します。

- ord #"a";
val it = 97 : int

- chr 97;
val it = #"a" : char

関数 hash_func は引数の文字列 x を explode で分解し、foldr で文字コードを加算します。匿名関数の中では、ord を使って char を int に変換し、その値を引数 b に加算します。あとは、foldr の返り値と size の剰余を求めるだけです。

文字列は等値型データなので、関数 equal は等値演算子 = でデータを比較するだけです。これで、ストラクチャの定義は終わりです。最後に、ファンクタ makeHash に StringItem を渡してストラクチャ StringHash を生成します。

●実行例

それでは簡単な実行例を示します。

- val a = StringHash.create();
val a = Hash [|[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],...|]
  : StringItem.item StringHash.hash

- StringHash.insert("foo", a);
val it = () : unit

- StringHash.search("foo", a);
val it = SOME "foo" : StringItem.item option
- StringHash.member("foo", a);
val it = true : bool

- StringHash.search("bar", a);
val it = NONE : StringItem.item option
- StringHash.member("bar", a);
val it = false : bool

- StringHash.delete("foo", a);
val it = () : unit

- StringHash.search("foo", a);
val it = NONE : StringItem.item option

正常に動作していますね。

●連想配列 (Hash Table) の実装

最後にハッシュ法を使って「連想配列」を作ってみましょう。なお、SML/NJ の The Util Library には連想配列として利用できるストラクチャ HashTable が用意されているので、私たちが自作する必要はありませんが、SML/NJ のお勉強ということで、プログラムを作ることにします。

チェイン法の場合、連想リストを使うと簡単です。データ型の定義は次のようになります。

リスト : 連想配列

functor makeHashtbl(Item: HASHITEM) = struct
  (* データ型の定義 *)
  datatype ('a, 'b) hash = Hash of ('a * 'b) list array

  (* ハッシュ表の生成 *)
  fun create () = Hash(Array.array(Item.size, nil: ('a * 'b) list))  

  ・・・省略・・・

end

(* キーが文字列の連想配列 *)
structure StringHashtbl = makeHashtbl(StringItem)

ファンクタ名は makeHashtbl としました。HASHITEM の型 item をキーとして使います。データ型は ('a, 'b) hash で、型変数 'a がキーのデータ型、'b が値のデータ型を表します。なお、値のデータ型が定義されていないので、関数 create でハッシュ表を生成するとき、多相性の制約によりデータ型の指定が必要になります。たとえば、キーが文字列で値が整数の場合は次のように指定します。

- val a : (string, int) StringHashtbl.hash = StringHashtbl.create();
val a = Hash [|[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],...|]
  : (string,int) StringHashtbl.hash

関数 search はキーが見つかれば SOME 値 を返し、見つからなければ NONE を返します。member もキーが見つかれば true を、そうでなければ false を返します。関数 insert は連想リストの先頭に組 (キー, 値) を追加するだけです。関数 delete は List.filter で同じキーを持つ組を削除します。とくに難しいところはないので、詳細はプログラムリストをお読みくださいませ。

●実行例 (2)

簡単な実行例を示します。

- val a : (string, int) StringHashtbl.hash = StringHashtbl.create();
val a = Hash [|[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],...|]
  : (string,int) StringHashtbl.hash

- StringHashtbl.insert("foo", 100, a);
val it = () : unit
- StringHashtbl.search("foo", a);
val it = SOME 100 : int option
- StringHashtbl.search("bar", a);
val it = NONE : int option

- StringHashtbl.insert("foo", 200, a);
val it = () : unit
- StringHashtbl.search("foo", a);
val it = SOME 200 : int option

- StringHashtbl.delete("foo", a);
val it = () : unit
- StringHashtbl.search("foo", a);
val it = NONE : int option

正常に動作しているようです。興味のある方はいろいろ試してみてください。

●プログラムリスト

(*
 * hash.sml : ハッシュ法
 *
 *            Copyright 2005-2020 Makoto Hiroi
 *
 *)

(* シグネチャ *)
signature HASHITEM = sig
  type item
  val size : int
  val hash_func : item -> int
  val equal : item * item -> bool  
end

(* ファンクタ *)
functor makeHash(Item: HASHITEM) = struct
  (* データ型の定義 *)
  datatype 'a hash = Hash of 'a list array

  (* ハッシュ表の生成 *)
  fun create () = Hash(Array.array(Item.size, nil: Item.item list))  

  (* データの探索 *)
  fun search(k, Hash table) =
    let
      val n = Item.hash_func k
      val xs = Array.sub(table, n)
    in
      List.find (fn x => Item.equal(x, k)) xs
    end

  fun member(k, ht) = isSome (search(k, ht))

  (* データの挿入 *)
  fun insert(k, Hash table) =
    let
      val n = Item.hash_func k
      val xs = Array.sub(table, n)
    in
      if List.exists (fn x => Item.equal(x, k)) xs then ()
      else Array.update(table, n, k::xs)
    end

  (* データの削除 *)
  fun delete(k, Hash table) =
    let
      val n = Item.hash_func k
      val xs = Array.sub(table, n)
    in
      Array.update(table, n, List.filter (fn x => not(Item.equal(x, k))) xs)
    end
end

structure StringItem: HASHITEM = struct
  type item = string
  val size = 199
  fun hash_func x = (foldr (fn(a, b) => ord(a) + b) 0 (explode x)) mod size  
  fun equal(a, b) = a = b
end

structure StringHash = makeHash(StringItem)


(* 連想配列 *)
functor makeHashtbl(Item: HASHITEM) = struct
  (* データ型の定義 *)
  datatype ('a, 'b) hash = Hash of ('a * 'b) list array

  (* ハッシュ表の生成 *)
  fun create () = Hash(Array.array(Item.size, nil: ('a * 'b) list))  

  (* データの探索 *)
  fun search(k, Hash table) =
    let
      val n = Item.hash_func k
      val xs = Array.sub(table, n)
    in
      case List.find (fn(x, _) => Item.equal(x, k)) xs
        of NONE => NONE
         | SOME (_, v) => SOME v
    end

  fun member(k, ht) = isSome (search(k, ht))

  (* データの挿入 *)
  fun insert(k, v, Hash table) =
    let
      val n = Item.hash_func k
      val xs = Array.sub(table, n)
    in
      Array.update(table, n, (k, v)::xs)
    end

  (* データの削除 *)
  fun delete(k, Hash table) =
    let
      val n = Item.hash_func k
      val xs = Array.sub(table, n)
    in
      Array.update(table, n, List.filter (fn(x, _) => not(Item.equal(x, k))) xs)
    end
end

structure StringHashtbl = makeHashtbl(StringItem)