## 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.