SML/NJ: ¿Cómo usar hashtable?

Question

Realmente quiero crear un hashtable en SML, parece que ya hay una estructura para esto en SML/NJ.

La pregunta es, ¿cómo lo uso? No he entendido completamente cómo usar estructuras en SML, y algunos de los ejemplos muy básicos en el libro que leí me dan errores que ni siquiera sé cómo corregir, por lo que usar la estructura de hashtable podría ser algo fácil, pero No lo sabría. Si alguien pudiera explicar esto, ¡eso también sería maravilloso!

Estoy pensando que es algo como esto:

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

???

Answer 1

La firma del mkTable el valor es:

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

Por lo tanto, tendrías que hacer algo como:

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

Answer 2

Supongo que la idea es crear una cadena de mapeo de mesa a enteros. Entonces quieres escribir su tipo como (string, int) hash_table (el tipo hash_table es un tipo con dos parámetros, que se escriben así en ML).

Pero también necesitas una función hash hash : string -> word y una función de igualdad eq : string * string -> bool sobre cuerdas para proporcionar a mkTable. Para este último, simplemente puedes usar op=, para el primero que puedes usar HashString.hashString del módulo respectivo.

Asi que,

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

Deberia trabajar.

Sin embargo, debo señalar que las tablas hash tienden a ser muy utilizadas en exceso, y la mayoría de las veces son la estructura de datos incorrecta. Esto es especialmente cierto en la programación funcional, ya que son una estructura de datos con estado. Por lo general, está mejor (y potencialmente aún más eficiente) utilizando algún mapa basado en árboles, por ejemplo, el RedBlackMapFn de la biblioteca SML/NJ.