Tuesday, 25 May 2010

Mini hash table

Imagine you're stuck on a desert island with only a few keystrokes and you desperately need to create your own rudimentary hash table. What might you do?

Well, here's one possible solution: a function that takes a sequence of key-value pairs and builds a hash table, returning another function that searches the hash table for the given key in order to find its corresponding value:

> let hashtbl xs = let spine = [|for _ in xs -> ResizeArray()|] let f k = spine.[k.GetHashCode() % spine.Length] Seq.iter (fun (k, v) -> (f k).Add (k, v)) xs fun k -> Seq.pick (fun (k', v) -> if k=k' then Some v else None) (f k);; val hashtbl : seq<'a * 'b> -> ('a -> 'b) when 'a : equality

Here's how you might use it to look up some squares:

> let tbl = hashtbl [for x in 0..100 -> x, x * x];; val tbl : (int -> int) > tbl 4;; val it : int = 16 > tbl 12;; val it : int = 144

1 comment:

Art said...

Looking for insight into ResizeArray. Thanks.