Hashtables are commonly used to implement finite maps. In ATSLIB/libats, there are hashtable implementations based on linear chaining and linear probing. There is also support for linear hashtables as well as persistent hashtables. The linear ones can be safely freed by the programmer, and the persistent ones (which are directly based on linear ones) can only be safely reclaimed through garbage collection (GC). In this chapter, I show how persistent hashtables can be created and operated on.

Suppose that a map is needed for mapping keys of type key_t to items of type itm_t. The following code essentially sets up an interface for creating and operating on such a map based on a hashtable implementation in ATSLIB/libats:

local typedef key = key_t and itm = itm_t in (* in-of-local *) #include "libats/ML/HATS/myhashtblref.hats" end // end of [local]

Assume that key_t is string and itm_t is int. The following line of code creates a hashtable with its initial capacity set to be 1000:

Note that the capacity in this case is the size of the array associated with the created hashtable. The underlying hashtable implementation is based on linear chaining, and this hashtable can store up to 5000 (5*1000) items without need for resizing. When resizing is indeed needed, it is done automatically. The following few lines insert some key/item pairs into mymap:// val-~None_vt() = mymap.insert("a", 0) val-~Some_vt(0) = mymap.insert("a", 1) // val-~None_vt() = mymap.insert("b", 1) val-~Some_vt(1) = mymap.insert("b", 2) // val-~None_vt() = mymap.insert("c", 2) val-~Some_vt(2) = mymap.insert("c", 3) //

// val-true = mymap.remove("a") val-false = mymap.remove("a") // val-~Some_vt(2) = mymap.takeout("b") val-~Some_vt(3) = mymap.takeout("c") //

// val () = mymap.insert_any("a", 0) val () = mymap.insert_any("b", 1) val () = mymap.insert_any("c", 2) val kxs = mymap.listize1((*void*)) val ((*void*)) = fprintln! (stdout_ref, "kxs = ", kxs) val kxs = mymap.takeout_all((*void*)) val ((*void*)) = fprintln! (stdout_ref, "kxs = ", kxs) // val () = assertloc (mymap.size() = 0) //

// extern fun myhashtbl_foreach_cloref ( tbl: myhashtbl , fwork: (key, &(itm) >> _) -<cloref1> void ) : void // end-of-function //

// val () = myhashtbl_foreach_cloref ( mymap , lam (k, x) => fprintln! (stdout_ref, "k=", k, " and ", "x=", x) ) (* myhashtbl_foreach_cloref *) //

Please find the entirety of the code used in this chapter on-line. Also, there is a hashtable-based implementation of symbol table available on-line.