Solved

HashTable vs .... !?

Posted on 2004-09-24
8
296 Views
Last Modified: 2010-04-15
Hi,

I need to store a short list of strings, arround 10 to 20, that will be searched several hundreds of thousands times and retrieve an integer value correspoding to that string value, it will be most likely its ordinal position.

I first tried a secuential search on a TArrayList that result too slow.
Then, I tried HashTable but still being too much slow for what I am doing.
Which other methods would be faster ?

Thanks in advance,

0
Comment
Question by:fischermx
  • 2
  • 2
  • 2
  • +2
8 Comments
 
LVL 18

Expert Comment

by:armoghan
ID: 12149295
HashTable  is the fastest, if it is not constructed again and again..
HashTable  provides fastest access, the addition of an element takes more time but retrival takes much lesser time that traversing the whole array.

0
 
LVL 18

Expert Comment

by:armoghan
ID: 12149309
You may try to use hashcode of string instead of string itself. as that is integer and can compare faster than String

0
 
LVL 1

Author Comment

by:fischermx
ID: 12149313
Sounds interesting, but I have no idea what exactly are you talking about.
Could you show some code, please ?

Thank you.
0
 
LVL 5

Expert Comment

by:tzxie2000
ID: 12150350
I have test the code below:

private void button4_Click(object sender, System.EventArgs e)
{

  Hashtable myHT = new Hashtable();
  int i,j,max;
  string[] sa=new string[20];
  Random rand=new Random();

  for(i=0;i<20;i++)
  {
    max=rand.Next(0,20);
    string s="";
    for(j=0;j<20+max;j++)
    {
      char ch;
      ch =(char)rand.Next('a','z'+1);
      s=s+ch;
    }
    sa[i]=s;
    myHT.Add(s,rand.Next(0,1000));
  }
  DateTime dt=DateTime.Now;
  for(i=0;i<1000000;i++)
  {
    int index=rand.Next(0,20);
    int res=(int)myHT[sa[index]];
  }
  TimeSpan ts=DateTime.Now-dt;
  MessageBox.Show(ts.Milliseconds.ToString());
}

and it shows only 406 milliseconds.
so whether you use Hashtable in wrong way?
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 3

Expert Comment

by:KeithWatson
ID: 12151006
Do you know what these 10-20 strings will be at compile time, if so, you'd be better declaring an array and using constants to access them. This is as fast as it will get. Assuming you don't know this, then a hash table will be the fastest; however, you would want to ensure that there are enough "buckets" allocated in the hash table. At best, a hash table performs with o(1) efficiency, at worst, if all the elements hash to the same bucket, then it performs with o(n) efficiency; no better than linearly searching a list. So if you are using a hash table, initialise it with a starting size a good bit bigger than your contents, and with a prime number, which helps the hashing function achieve a more even spread across the buckets (don't ask me why!), so for example:

Hashtable hashTable = new Hashtable(37);


0
 
LVL 10

Expert Comment

by:smegghead
ID: 12156081
You could just contruct a string containing all your strings and integers, separated with delimiters.

For example

~Purple~3~Blue~5~Red~15~Orange~123~

Then, when you want to find the number corresponding to Red, simple search the string using IndexOf..

      string str="~Purple~3~Blue~5~Red~15~Orange~123~";
      string find="Red";
      int foundat=str.IndexOf("~"+find+"~")+find.Length+2;
      int foundend=str.IndexOf("~",foundat);
      int result=Convert.ToInt32(str.Substring(foundat,foundend-foundat));

If there are only 10 or so items, this will be very quick, but if the string gets much bigger, it won't be so efficient.

Smg.
0
 
LVL 1

Author Comment

by:fischermx
ID: 12156522
Thanks,

That was the first try in the very begining. It is like 50% slower than a HashTable approach.

I think my best bet to improve the hash table is to provide my own hash function, but  I found no samples about how to do that.

Regards,

0
 
LVL 5

Accepted Solution

by:
tzxie2000 earned 500 total points
ID: 12157587
primarycode below

private void button4_Click(object sender, System.EventArgs e)
{
  hashstring provider=new hashstring();<----------------------------------here implement a IHashCodeProvider

  Hashtable myHT = new Hashtable(provider,null);<-------------------------set the provider to hashtable
  int i,j,max;
  string[] sa=new string[20];
  Random rand=new Random();

  for(i=0;i<20;i++)
  {
    max=rand.Next(0,20);
    string s="";
    for(j=0;j<20+max;j++)
    {
      char ch;
      ch =(char)rand.Next('a','z'+1);
      s=s+ch;
    }
    sa[i]=s;
    myHT.Add(s,1);
  }
  DateTime dt=DateTime.Now;
  for(i=0;i<1000000;i++)
  {
    int index=rand.Next(0,20);
    int res=(int)myHT[sa[index]];
  }
  TimeSpan ts=DateTime.Now-dt;
  MessageBox.Show(ts.Milliseconds.ToString());
  // Displays the properties and values of the Hashtable.
}

//the implement part
public class hashstring :IHashCodeProvider  
  {
    int IHashCodeProvider.GetHashCode(object obj) <---write for gethashcode for your function,here I return the hashcode of string with the sum of all char

    {
      string s=obj.ToString();
      char []ca=s.ToCharArray();
      int res=0;
      int i;
      for(i=0;i<ca.Length;i++)
      {
        res+=ca[i];
      }
      return res;
    }
  }
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
reading a text file which contains double Quotes is truncading the record 4 41
Problem to error 4 43
Turn on intranet settings 1 36
C# parent child form 5 12
Extention Methods in C# 3.0 by Ivo Stoykov C# 3.0 offers extension methods. They allow extending existing classes without changing the class's source code or relying on inheritance. These are static methods invoked as instance method. This…
Introduction This article series is supposed to shed some light on the use of IDisposable and objects that inherit from it. In essence, a more apt title for this article would be: using (IDisposable) {}. I’m just not sure how many people would ge…
Here's a very brief overview of the methods PRTG Network Monitor (https://www.paessler.com/prtg) offers for monitoring bandwidth, to help you decide which methods you´d like to investigate in more detail.  The methods are covered in more detail in o…
This is a video that shows how the OnPage alerts system integrates into ConnectWise, how a trigger is set, how a page is sent via the trigger, and how the SENT, DELIVERED, READ & REPLIED receipts get entered into the internal tab of the ConnectWise …

943 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

4 Experts available now in Live!

Get 1:1 Help Now