SML / NJ: comment utiliser le hashtable?

Question

Je veux vraiment créer un hashtable dans SML, il semble qu'il y ait déjà une structure pour cela dans SML / NJ.

La question est, comment puis-je l'utiliser? Je n'ai pas entièrement compris comment utiliser les structures dans SML, et certains des exemples très basiques du livre que j'ai lus me donnent des erreurs, je ne sais même pas comment corriger, donc l'utilisation de la structure de hachage pourrait être une chose facile, mais Je ne saurais pas. Si quelqu'un pouvait expliquer cela, ce serait aussi merveilleux!

Je pense que c'est quelque chose comme ça:

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

???

Answer 1

La signature du mkTable La valeur est:

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

Par conséquent, vous devrez faire quelque chose comme:

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

Answer 2

Je suppose que l'idée est de créer des chaînes de mappage de table aux entiers. Alors vous voulez écrire son type comme (string, int) hash_table (le type hash_table est un type avec deux paramètres, qui sont écrits comme celui dans ML).

Mais vous avez également besoin d'une fonction de hachage hash : string -> word et une fonction d'égalité eq : string * string -> bool sur des chaînes à fournir à mkTable. Pour ce dernier, vous pouvez simplement utiliser op=, pour le premier que vous pouvez utiliser HashString.hashString du module respectif.

Alors,

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

devrait marcher.

Je dois cependant noter que les tableaux de hachage ont tendance à être largement surutilisés, et le plus souvent, ils sont la mauvaise structure de données. Cela est particulièrement vrai dans la programmation fonctionnelle, car ils sont une structure de données avec état. Habituellement, vous êtes mieux (et potentiellement encore plus efficace) en utilisant une carte basée sur des arbres, par exemple, le RedBlackMapFn de la bibliothèque SML / NJ.