Source

OCaml Map Reduce Project / shared / hashtable.ml

Full commit
exception Not_found of string

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
  (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_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
  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
  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);
  if needs_rehash then rehash table else ()

let find (table : ('a, 'b) t) (key : 'a) : 'b =
  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
  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_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
  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_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
  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_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
  for index = 0 to size - 1 do
    let current_list = List.rev (Array.get hash_table index) in
    x := List.fold_left helper !x current_list
  done; !x

let length (table : ('a, 'b) t) : int = let (_, _, length) = table in !length