stringHash.ml

let strs =
  [
    "Salty";
    "Cracker";
    "Emily";
    "Angela";
    "Richard";
    "John";
    "Betty";
    "Zebra";
    "Bobby";
    "Kenny";
    "Brenda";
    "Dart";
    "Cat";
    "Dog";
    "Bird";
    "Lion";
    "Tweety";
    "Tank";
    "Car";
    "Gun";
    "Apple";
    "Plum";
    "Run";
    "Peel";
    "See";
    "Sun";
    "Mouse";
    "Speaker";
    "Key";
    "Song";
    "Switch";
    "On";
    "Gun";
    "Apple";
    "Switch";
    "Lion";
    "Gun";
    "Gun";
  ]

let arr_size = 24

type 'a collisions = 'a list
type 'a hash_table = (('a * 'a collisions) option) array

let genhash str size =
  let hash = 5381 in
  (Seq.fold_left
    (
      fun a d ->
        ((Int.shift_left a 5) + a) + (Char.code d)
    )
    hash
    (String.to_seq(str))) mod size

let createEmptyHash size:'a hash_table =
  Array.init size (fun x -> None)

let display (ht:'a hash_table) fStr =
  Array.iter (
    fun v ->
      match v with
      | None -> print_endline "Nothing here!"
      | Some (s, coll) ->
        (
          Printf.printf "%s\n" (fStr s);
          List.iter (fun s -> Printf.printf "\t%s\n" s) coll
        )
  ) ht

let addString ht str size =
  let h_v = genhash str size in
  let elem = Array.get ht h_v in
  match elem with
  | None -> Array.set ht h_v (Some(str, []))
  | Some (s, coll) ->
    if not(String.equal s str)
    then
      if List.exists (fun s -> String.equal s str) coll
      then
        ()
      else
        Array.set ht h_v (Some(s, str::coll))

let findValue (ht:string hash_table) str =
  Array.exists
    (
      fun e ->
        match e with
        | None -> false
        | Some (s, coll) ->
          if (String.equal s str)
          then
            true
          else if (List.exists (fun s -> String.equal s str) coll)
          then
            true
          else
            false

    ) ht

let removeValue (ht:string hash_table) str =
  let exception Done in
  try
  Array.iteri
    (
      fun i e ->
        match e with
        | None -> ()
        | Some (s, coll) ->
          if String.equal s str
          then
            (
              if List.length coll = 0
              then
                (
                  Array.set ht i None;
                  raise Done
                )
              else
                (
                  Array.set ht i (Some(List.hd coll, List.tl coll));
                  raise Done
                )
            )
          else if List.exists (fun s -> String.equal s str) coll
          then
            (
              Array.set ht i
                (
                  Some(s, List.filter (fun s -> not(String.equal s str)) coll)
                );
              raise Done
            )
    ) ht
    with _ -> ()

let my_hash = createEmptyHash arr_size

let () =
  List.iter
    (fun s -> addString my_hash s arr_size)
    strs

let () =
  List.iter
    (
      fun s ->
       removeValue my_hash s
    )
    ["Tank"; "John"; "Bird"; "Lion"; "Switch"; "Apple"; "Gun"]

let () = display my_hash (fun t -> t)