SML/NJ: How to use HashTable?

Question

I really want to create a HashTable in SML, it seems there already is a structure for this in SML/NJ.

The question is, how do I use it? I've not fully understood how to use structures in SML, and some of the very basic examples in the book I read gives me errors I don't even know how to correct, so using the HashTable structure might be an easy thing, but I wouldn't know. If someone could explain this, then that'd be wonderful too!

I'm thinking it's something like this:

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

???

Answer 1

The signature of the mkTable value is:

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.
     *)

Therefore, you would have to do something like:

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

Answer 2

I assume the idea is to create a table mapping strings to integers. Then you want to write its type as (string, int) hash_table (the type hash_table is a type with two parameters, which are written like that in ML).

But you also need a hash function hash : string -> word and an equality function eq : string * string -> bool over strings to provide to mkTable. For the latter, you can simply use op=, for the former you can use HashString.hashString from the respective module.

So,

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

should work.

I should note, however, that hash tables tend to be vastly overused, and more often than not they are the wrong data structure. This is especially true in functional programming, since they are a stateful data structure. Usually you are better off (and potentially even more efficient) using some tree-based map, e.g., the RedBlackMapFn from the SML/NJ library.