Hashtable is that fast

Question

Hi

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]. Is the hash function of the java string, I assume the rest of languages is similar or close to this implementation.

If we have hash-Table and a list of 50 elements. each element is 7 chars ABCDEF1, ABCDEF2, ABCDEF3..... ABCDEFn

If each bucket of hashtable contains 5 strings (I think this function will make it one string per bucket, but let us assume it is 5).

If we call col.Contains("ABCDEFn"); // will do 6 comparisons and discover the difference on the 7th.

The hash-table will take around 70 operations (multiplication and additions) to get the hashcode and to compare with 5 strings in bucket. and BANG it found.

For list it will take around 300 comparisons to find it.

for the case that there is only 10 elements, the list will take around 70 operations but the Hashtable will take around 50 operations. and note that hashtable operations are more time consuming (it is multiplications).

I conclude that HybirdDictionary in .Net probably is the best choice for that most cases that require Hashtable with unknown size, because it will let me use a list till the list becomes more than 10 elements. still need something like HashSet rather than a Dictionary of keys and values, I wonder why there is no HybirdSet!!

So what do u think?

Thanks

Answer 1

I think you raise a good point. Lists may be quicker than Hash tables for small numbers, and this is perfectly documented within the literature.

However, you can easily create your own data structure, which according to its size count() will utilize a List or a Hash.

Answer 2

I am new to asp.net. could i have berif intro about Hastable? Where to use that?. if you we use the Hastable will it be affected the performance?

Answer 3

Does this really matter? You usually care about performance impact with large collections of data. 20-30 additional operations if collection is small wont make any difference.