Hashtable-based findKeyword function

1 files changed, 64 insertions, 0 deletions

diff --git a/hashtable.sml b/hashtable.sml
new file mode 100644
index 0000000..24e5bba
--- /dev/null
+++ b/hashtable.sml
@@ -0,0 +1,64 @@
+structure Hashtable :> HASHTABLE = struct
+    (* (Array, (cells occupied, total size)) *)
+  type 'a t = ((string * 'a) option) array * (int * int)
+
+  exception HashtableFull
+  exception Exists
+
+  fun create size = (Array.array (size, NONE), (0, size))
+
+  val fillLimit = 0.75
+
+  val ` = Word32.fromInt
+
+  fun hashFunc key =
+  let
+    open Word32
+  in
+    List.foldl (fn (x, acc) => acc * `31 + `(ord x)) (`0) $ explode key
+  end
+
+  fun insert (buf, (taken, total)) key value =
+    if Real.fromInt (taken + 1) / Real.fromInt total > fillLimit then
+      raise HashtableFull
+    else
+      let
+        open Array
+        val hash = hashFunc key
+
+        (* TODO: use bitwise manipulation instead of mod *)
+        val i = ref $ Word32.toInt $ Word32.mod (hash, `(length buf))
+        val flag = ref true
+      in
+        while !flag do (
+          case sub (buf, !i) of
+            NONE => (update (buf, !i, SOME (key, value)); flag := false)
+          | SOME (key', _) =>
+              if key' = key then
+                raise Exists
+              else
+                i := (!i + 1) mod (length buf)
+        )
+      end
+
+  fun lookup (buf, _) key =
+  let
+    open Array
+    val hash = hashFunc key
+
+    val i = ref $ Word32.toInt $ Word32.mod (hash, `(length buf))
+    val flag = ref true
+    val result = ref NONE
+  in
+    while !flag do (
+        case sub (buf, !i) of
+          SOME (key', value) =>
+            if key' = key then
+              (result := SOME value; flag := false)
+            else
+              i := (!i + 1) mod (length buf)
+        | NONE => flag := false
+    );
+    !result
+  end
+end