A minimal HashMap implementation in SML

hashmap.sml

signature HASH_MAP =
sig
type 'a hashVector
type ('a, 'b) hashMap
val makeEmpty : (('a -> int) * ('a * 'a -> bool) * int) -> ('a, 'b) hashMap
val lookup : ('a, 'b) hashMap -> 'a -> 'b option
val insert : ('a, 'b) hashMap -> 'a * 'b -> unit
val remove : ('a, 'b) hashMap -> 'a -> unit
val load : ('a, 'b) hashMap -> int
end

structure HashMap =
struct
type 'a hashVector = 'a list ref vector
type ('a, 'b) hashMap = { hash: 'a -> int, eq: 'a * 'a -> bool, size: int, vec: ('a * 'b) hashVector, load: int ref }
(* makeEmpty: ('a, 'b) hashMap * ('a -> bool) * int *)
fun makeEmpty (hash, eq, size) = 
    { hash=hash, eq=eq, size=size, vec=Vector.tabulate (size, (fn x => ref [])), load=ref 0 }
(* lookup_list: ('a * 'a -> bool) * ('a * 'b) list -> 'a -> 'b option *)
fun lookup_list (eq, kvList) key = 
    let fun eqToK (x, _) = eq (x, key)
    in Option.map (fn (_,v) => v) (List.find eqToK kvList)
    end
(* insert_list: ('a * 'a -> bool) * ('a * 'b) list ref -> ('a, 'b) -> () *)
fun insert_list (eq, kvList) (k, v) = 
    (k, v) :: (List.filter (fn (x, _) => (not (eq (x, k)))) kvList)
(* remove_list: ('a * 'a -> bool) * ('a * 'b) list ref -> 'a -> () *)
fun remove_list (eq, kvList) k =
    List.filter (fn (x, _) => (not (eq (x, k)))) kvList
(* lookup: ('a, 'b) hashMap -> 'a -> 'b option *)
fun lookup { hash, eq, size, vec, load } key  = 
    lookup_list (eq, !(Vector.sub (vec, (hash key)))) key
(* insert: ('a, 'b) hashMap -> 'a * 'b -> unit *)
fun insert { hash, eq, size, vec, load } (key, value) =
    let val kvListRef = Vector.sub (vec, (hash key))
	val ref kvList = kvListRef
    in (kvListRef := insert_list (eq, kvList) (key, value); 
	load := !load - (length kvList) + (length (!kvListRef)))
    end
(* remove: ('a, 'b) hashMap -> 'a -> unit *)
fun remove { hash, eq, size, vec, load } key = 
    let val kvListRef = Vector.sub (vec, (hash key))
	val ref kvList = kvListRef
    in (kvListRef := remove_list (eq, kvList) key;
	load := !load - (length kvList) + (length (!kvListRef)))
    end
(* load: ('a, 'b) hashMap -> int *)
fun load { hash, eq, size, vec, load } = !load
end

hashmap_test.sml

(* testing HashMap *)
use "hashmap.sml";

open HashMap;

(* djb2 hash algorithm from http://www.cse.yorku.ca/~oz/hash.html *)
fun djb2 size s =
    let val bytes = (map (Word.fromInt o Char.ord) (explode s))
	val sizeW = Word.fromInt size
    in Word.toInt (foldl (fn (b, hash) => 
			     (Word.xorb (Word.xorb (Word.<< (hash, 0wx5), hash), b)) mod sizeW)
			 0wx1505 (* 5381 *)
			 bytes)
    end

val ht_size = IntInf.toInt (IntInf.pow (2, 16))
val ht : (string, int) hashMap = makeEmpty (djb2 ht_size, op =, ht_size)
val test1 = load ht;
insert ht ("bar", 12000);
val test2 = load ht = 1;
insert ht ("buzz", 9000);
val test3 = load ht = 2;
insert ht ("bar", 15000);
val test4 = load ht = 2;
remove ht "bar";
val test5 = load ht = 1;
insert ht ("bar", 15000);
val test6 = lookup ht "bar" = SOME 15000;
val test7 = load ht = 2;
remove ht "foo";
val test8 = load ht = 2;