SML/NJ：如何使用Hashtable？

Question

我真的很想在SML中创建一个标签，看来SML/NJ中已经有一个结构。

问题是，我该如何使用？我尚未完全了解如何在SML中使用结构，而我阅读的书中的一些非常基本的示例给了我什至不知道如何纠正的错误，因此使用Hashtable结构可能很容易，但是我不知道。如果有人可以解释这一点，那也很棒！

我认为这是这样的：

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 是具有两个参数的类型，它们像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库。