Hashtable lookup - speed ?

[Guest]

I have build an application which uses Hashtables for storing information in
collections.

My question is simple - I wonder how big a (performance) difference it is,
to lookup a value in a hashtable with 500.000 items, and a hashtable with 500
items ?

Is there any difference or anything else I should be aware of ?


Regards,
Tony

 

[Stefan Simek]

Hi,

It mostly depends on the distribution of your hashcodes. In the ideal
case, the hashtable lookup should be always an O(1) operation regardless
of the item count. In the worst case, however, with all items having the
same hashcode, you would get an O(n) operation.

HTH,
Stefan

 

[Brian Gideon]

Tony,

Like Stefan said if the hashcodes are well distributed then the
hashtable will have an average case runtime complexity of O(1). That
means that the operations will run in the same amount of time
regardless of the size of the table. If you're using the primitive
types as the keys for the table then this won't be a problem. If you
have created your own class to be used as keys then pay special
attention to the implementation of the GetHashCode method.

Brian