Commits

Kelvin Jin committed cacacdc

Fixed Hashtable.mem/find/remove, added rehashing to meet runtime complexity requirements.

Comments (0)

Files changed (1)

shared/hashtable.ml

 exception Not_found of string
 
-type ('a, 'b) t = (('a * 'b) list) array * ('a -> int) * int ref
+let bucket_max_size : int = 5
+let carrying_capacity : float = 0.75
+type ('a, 'b) t = (('a * 'b) list) array ref * ('a -> int) * int ref
 
 let create (capacity : int) (hash : 'a -> int) : ('a, 'b) t =
   let init_fun a : ('a * 'b) list = [] in
-  (Array.init capacity init_fun, hash, ref 0)
+  (ref (Array.init capacity init_fun), hash, ref 0)
+
+let iter (f : 'a -> 'b -> unit) (table : ('a, 'b) t) : unit =
+  let (hash_table_ref, hash_function, _) = table in
+  let hash_table = !hash_table_ref in
+  let size = Array.length hash_table in
+  for index = 0 to size - 1 do
+    let current_list = Array.get hash_table index in
+    let helper lst (k, v) = f k v in
+    List.fold_left helper () current_list
+  done
+
+let rehash table : unit =
+  let (hash_table_ref, hash_function, length) = table in
+  let new_capacity = (Array.length !hash_table_ref) * 2 in
+  let new_hash_table =
+    let init_fun a : ('a * 'b) list = [] in
+    Array.init new_capacity init_fun in
+  let add_to_new_table key value =
+    let index = hash_function key mod new_capacity in
+    let val_list = Array.get new_hash_table index in
+    Array.set new_hash_table index ((key, value)::val_list) in
+  iter add_to_new_table table; hash_table_ref := new_hash_table
 
 let add (table : ('a, 'b) t) (key : 'a) (value : 'b) : unit =
-  let (hash_table, hash_function, length) = table in
+  let (hash_table_ref, hash_function, length) = table in
+  let hash_table = !hash_table_ref in
   let capacity = Array.length hash_table in
   let index = hash_function key mod capacity in
   let val_list = Array.get hash_table index in
     if k = key then (length := !length - 1; lst)
     else (k, v)::lst in
   let processed_val_list = List.rev (List.fold_left filter [] val_list) in
+  let needs_rehash =
+    (List.length processed_val_list) + 1 >= bucket_max_size ||
+    (float_of_int (!length + 1)) /. (float_of_int capacity) >= carrying_capacity in
   length := !length + 1;
-  Array.set hash_table index ((key, value)::processed_val_list)
+  Array.set hash_table index ((key, value)::processed_val_list);
+  if needs_rehash then rehash table else ()
 
 let find (table : ('a, 'b) t) (key : 'a) : 'b =
-  let (hash_table, hash_function, _) = table in
+  let (hash_table_ref, hash_function, _) = table in
+  let hash_table = !hash_table_ref in
   let capacity = Array.length hash_table in
   let index = hash_function key mod capacity in
   let val_list = Array.get hash_table index in
-  match val_list with
-  | [] -> raise (Not_found "no binding for key")
-  | h::_ -> snd h
+  let rec find_in_list lst =
+    match lst with
+    | [] -> None
+    | (k, v)::t -> if k = key then Some (k, v) else find_in_list t in
+  match find_in_list val_list with
+  | None -> raise (Not_found "no binding for key")
+  | Some (k, v) -> v
 
 let mem (table : ('a, 'b) t) (key : 'a) : bool =
-  let (hash_table, hash_function, _) = table in
+  let (hash_table_ref, hash_function, _) = table in
+  let hash_table = !hash_table_ref in
   let capacity = Array.length hash_table in
   let index = hash_function key mod capacity in
   let val_list = Array.get hash_table index in
-  match val_list with
-  | [] -> false
-  | h::_ -> true
+  let rec find_in_list lst =
+    match lst with
+    | [] -> None
+    | (k, v)::t -> if k = key then Some (k, v) else find_in_list t in
+  match find_in_list val_list with
+  | None -> false
+  | Some (k, v) -> true
 
 let remove (table : ('a, 'b) t) (key : 'a) : unit =
-  let (hash_table, hash_function, length) = table in
+  let (hash_table_ref, hash_function, length) = table in
+  let hash_table = !hash_table_ref in
   let capacity = Array.length hash_table in
   let index = hash_function key mod capacity in
   let val_list = Array.get hash_table index in
-  match val_list with
-  | [] -> ()
-  | _::t -> length := !length - 1; Array.set hash_table index t
-
-let iter (f : 'a -> 'b -> unit) (table : ('a, 'b) t) : unit =
-  let (hash_table, hash_function, _) = table in
-  let size = Array.length hash_table in
-  for index = 0 to size - 1 do
-    let current_list = Array.get hash_table index in
-    let helper lst (k, v) = f k v in
-    List.fold_left helper () current_list
-  done
+  let filter lst (k, v) =
+    if k = key then (length := !length - 1; lst)
+    else (k, v)::lst in
+  let processed_val_list = List.rev (List.fold_left filter [] val_list) in
+  Array.set hash_table index processed_val_list
 
 let fold (f : 'a -> 'b -> 'c -> 'c) (table : ('a, 'b) t) (init : 'c) : 'c =
-    let (hash_table, hash_function, _) = table in
+  let (hash_table_ref, hash_function, _) = table in
+  let hash_table = !hash_table_ref in
   let size = Array.length hash_table in
   let x = ref init in
   let helper acc (k, v) = f k v acc in