CODEWITHSUNDEEP
.netsearchhashtablelinear-search
CuriousCoder
CuriousCoder

Reputation: 1600

How does look up for a hash table work in .NET?

I tried to compare the performance of a hash table lookup and linear search. I created a hashtable containing 1000 items and found out the time taken to do a look up in the hash table to be 0.0002 (I used DateTime.Now to find out the system time before and after the look up and subtracted them). I had the same 1000 rows in an array and looked up the same value using linear search. And it turned out to be lesser than the time taken by hash table look up.

I thought hash tables are faster than linear search. How does it work?

Upvotes: 1

Views: 399

Answers (2)

toddmo
toddmo

Reputation: 22416

The answer can be found in this article:

An Extensive Examination of Data Structures Using C# 2.0,

in the section called "The System.Collections.Hashtable Class"

Here is the (extremely) short synopsis:

Adding to the collection (Add(object key, object value)):

  1. Receive key and value parameter
  2. Apply hash algorithm to the key parameter. This is a complicated formula that uses the Object.GetHashCode() method and yields a position in the index between 0 and hashsize (the number of slots in the hash table (the internal lookup structure used by System.Collections.HashTable).
  3. Insert a DictionaryEntry object at that position.

Accessing an item in the collection(object this[object key] { set; get; }):

  1. Receive the key parameter
  2. Compute the position in the hash table by using the hash algorighm on the key parameter.
  3. Return the value of the item stored at that position

Upvotes: 1

jason
jason

Reputation: 241661

First, your mechanism for timing is not good. If you want to test performance you should use a high-resolution timer like System.Diagnostics.Stopwatch.

Second, you need to find the average lookup time over many many lookups that are randomly and uniformly distributed over your lookup space, not just the lookup time for one particular item.

Upvotes: 3

Related Questions