Skip to content

Instantly share code, notes, and snippets.

@mrfabbri
Created November 3, 2014 00:05
Show Gist options
  • Save mrfabbri/86b94ce9d2b06c641fd7 to your computer and use it in GitHub Desktop.
Save mrfabbri/86b94ce9d2b06c641fd7 to your computer and use it in GitHub Desktop.
A minimal HashMap implementation in 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
(* 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;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment