2

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

问题是，我该如何使用它？我还没有完全理解如何在 SML 中使用结构，并且我阅读的书中的一些非常基本的示例给我带来了我什至不知道如何纠正的错误，所以使用 HashTable 结构可能是一件容易的事情，但是我不会知道的。如果有人可以解释这一点，那就太好了！

我在想它是这样的：

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

？？？

4

2 回答 2

6

该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")
于 2013-11-07T22:45:38.500 回答
4

我假设这个想法是创建一个将字符串映射到整数的表。然后你想把它的类型写成(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 库的地图）会更好（甚至可能更有效率） 。

于 2013-11-07T17:45:25.130 回答