SML/NJ: Wie kann man Hashtable verwenden?

Question

Ich möchte wirklich einen Hashtable in SML erstellen, es scheint bereits eine Struktur dafür in SML/NJ zu geben.

Die Frage ist, wie ich es benutze? Ich habe nicht vollständig verstanden, wie man Strukturen in SML verwendet, und einige der grundlegenden Beispiele in dem Buch, das ich lese Ich würde es nicht wissen. Wenn jemand das erklären könnte, wäre das auch wunderbar!

Ich denke, es ist so etwas:

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

???

Answer 1

Die Signatur der mkTable Wert ist:

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

Deshalb müssten Sie so etwas tun:

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

Answer 2

Ich nehme an, die Idee ist, ein Tabellenzuordnungszeichenfolgen für Ganzzahlen zu erstellen. Dann möchten Sie seinen Typ als schreiben als (string, int) hash_table (der Typ hash_table ist ein Typ mit zwei Parametern, die wie in ML geschrieben sind).

Sie brauchen aber auch eine Hash -Funktion hash : string -> word und eine Gleichstellungsfunktion eq : string * string -> bool über Saiten zur Verfügung mkTable. Für letztere können Sie einfach verwenden op=, Für die ersteren können Sie verwenden HashString.hashString Aus dem jeweiligen Modul.

So,

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

sollte arbeiten.

Ich sollte jedoch beachten, dass Hash -Tabellen tendenziell stark überbeanspruchte und meistens die falsche Datenstruktur sind. Dies gilt insbesondere für die funktionale Programmierung, da sie eine staatliche Datenstruktur sind. Normalerweise sind Sie besser dran (und möglicherweise sogar noch effizienter) mit einer baumbasierten Karte, z. B. der RedBlackMapFn Aus der SML/NJ -Bibliothek.