Robert,


RK> Peter, a Hash uses _hashing_ to keep lookup cost low.  This has complexity O(1).

Oh god, I feel so stupid.

Thanks for pointing that out.

RK> http://en.wikipedia.org/wiki/Hash_table#Performance_analysis