HashTable vs .... !?

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,

LVL 1
fischermxAsked:
Who is Participating?

Improve company productivity with a Business Account.Sign Up

x
 
tzxie2000Connect With a Mentor Commented:
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
 
armoghanCommented:
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
 
armoghanCommented:
You may try to use hashcode of string instead of string itself. as that is integer and can compare faster than String

0
Keep up with what's happening at Experts Exchange!

Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.

 
fischermxAuthor Commented:
Sounds interesting, but I have no idea what exactly are you talking about.
Could you show some code, please ?

Thank you.
0
 
tzxie2000Commented:
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
 
KeithWatsonCommented:
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
 
smeggheadCommented:
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
 
fischermxAuthor Commented:
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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.