SML/NJ：ハッシュテーブルの使用方法は？

Question

私は本当にSMLでハッシュテーブルを作成したいのですが、SML/NJにはすでにこの構造があるようです。

問題は、どうすればそれを使用するのですか？私はSMLで構造を使用する方法を完全には理解していませんでしたが、私が読んだ本の非常に基本的な例のいくつかは、私が修正する方法さえ知らないエラーを与えてくれます。私は知りません。誰かがこれを説明できれば、それも素晴らしいでしょう！

私はそれがこのようなものだと思っています：

val ht : string * int HashTable.hash_table = HashTable.mkTable();

???

Answer 1

の署名 mkTable 価値は次のとおりです。

val mkTable : (('a -> word) * (('a * 'a) -> bool)) -> (int * exn)
      -> ('a,'b) hash_table
    (* Given a hashing function and an equality predicate, create a new table;
     * the int is a size hint and the exception is to be raised by find.
     *)

したがって、次のようなことをする必要があります。

val ht : (string, int) HashTable.hash_table =
    HashTable.mkTable (HashString.hashString, op=) (42, Fail "not found")

Answer 2

アイデアは、整数に文字列をマッピングするテーブルマッピングを作成することだと思います。次に、そのタイプを次のように書きたいと思います (string, int) hash_table （タイプ hash_table 2つのパラメーターを持つタイプで、MLでそのように書かれています）。

ただし、ハッシュ関数も必要です hash : string -> word および平等関数 eq : string * string -> bool 提供する文字列 mkTable. 。後者の場合、単に使用できます op=, 、前者のために使用できます HashString.hashString それぞれのモジュールから。

そう、

val ht : (string, int) HashTable.hash_table = HashTable.mkTable(HashString.hashString, op=)(17, Domain)

動作するはずです。

ただし、ハッシュテーブルは非常に使いすぎている傾向があり、多くの場合、それらが間違ったデータ構造であることに注意してください。これは、機能的なプログラミングで特に当てはまります。これは、ステートフルデータ構造であるためです。通常、ツリーベースのマップを使用して（そしてさらに効率的に）より良い（そして潜在的にさらに効率的） RedBlackMapFn SML/NJライブラリから。