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 =
    List.foldl (fn (x, acc) => acc * `31 + `(ord x)) (`0) $ explode key

  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