SML / NJ：如何使用HashTable？

Question

我真的很想在SML中创建一个HashTable，似乎在SML / NJ中已经有一个结构。

问题是，我该如何使用它？我还没有完全理解如何在SML中使用结构，并且在我读过的书中一些非常基本的示例给了我什至不知道如何更正的错误，因此使用HashTable结构可能很容易，但是我不知道 如果有人可以解释这一点，那也太好了！

我在想是这样的：

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

???

Answer 1

我认为这个想法是创建一个将字符串映射到整数的表。然后你想把它的类型写成(string, int) hash_table（该类型hash_table是有两个参数的类型，就像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 库的地图。

Answer 2

该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")