1

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?

Dan Is Fiddling By Firelight
  • 5,981
  • 17
  • 77
  • 128
CuriousCoder
  • 1,582
  • 5
  • 28
  • 55
  • 1000 is really too small, the advantage of the hash table shows up when the numbers of items is larger. – Ta01 Aug 13 '11 at 00:27
  • @kd7: No, that is not the issue at all. The issue is that he only did one lookup, and maybe that item happened to be at the front of the array. – jason Aug 13 '11 at 00:31
  • The smallest increment you get out of DateTime.Now is 0.0156 sec on the vast majority of machines. If you kill 3 goats and sacrifice your eldest then you might get 0.0010. Given that you measured 0.0002 *and* got a counter-intuitive result, the bigger odds are that your test is just plain invalid. Easy assumption because you didn't give anyone a chance to validate it. – Hans Passant Aug 13 '11 at 00:59
  • possible duplicate of [How does a hash table work?](http://stackoverflow.com/questions/730620/how-does-a-hash-table-work) – Joe Aug 13 '11 at 01:50
  • @Joe, I don't think it's a duplicate because that question is theory; this question deals with an actual implementation - .Net `System.Collections.Hashtable` – toddmo Oct 15 '13 at 22:23

2 Answers2

3

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.

jason
  • 236,483
  • 35
  • 423
  • 525
1

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
toddmo
  • 20,682
  • 14
  • 97
  • 107