Wait... a hash table has O(1)??? Wow, that''s incredible! I''ve got to do some reading on that one... I remember learning about lists and Binary Trees in Data Structures, but no one ever mentioned hash tables.

Hash tables aren''t really O(1), because O is for worst-case. Hash Tables are O(n), but act like constant-time access as long as you properly implement it. If you''re storing 50000 entries, but only have 2 buckets, you''re not going to get constant time access to each element. Generally, with a good hash function, you can get constant-time access if you have about 25% more buckets than you expect to have entries. Less than that, and you''ll generally start getting a few collisions, but not too many.

Also, each bucket could be represented as something other than a linked list if you expect to have many collisions. You could have each bucket be a hash table itself (using a different hashing function of course), or a binary tree, or any other data structure. In the normal case, where you only have a few collisions, a link list will do fine and make insertion fast.