ハッシュテーブルは有限写像の実装でよく使われます。 ATSLIB/libats には、linear chaining と linear probing を用いたハッシュテーブル実装があります。 永続化ハッシュテーブルだけでなく線形ハッシュテーブルのサポートもあります。 線形ハッシュテーブルはプログラマの手で安全に解放できます。 (線形ハッシュテーブルを用いた) 永続化ハッシュテーブルはガベージコレクション (GC) によって安全に回収されます。 この章では、永続化ハッシュテーブルの生成と操作方法を示します。
型 key_t のキーから型 itm_t の要素へマップする写像が必要だと考えます。 次のコードは本質的に、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]
key_t は string、 itm_t は int であると仮定します。 次のコードの行は初期容量が 1000 のハッシュテーブルを生成しています:
この場合の容量とは、生成されたハッシュテーブルに関連する配列のサイズであることに注意してください。 ハッシュテーブル実装の根底は linear chaining に基づいていて、このハッシュテーブルは 5000 (5*1000) 要素までリサイズなしに格納できます。 実際にリサイズが必要な場合も、自動的に行なわれます。 次の数行では、いくつかのキー/要素ペアを 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 *) //
この章で示したコード全体は オンライン から入手できます。 また、ハッシュテーブルを用いた symbol table の実装も オンライン から入手できます。