Re: Need quick lookup like Hashtable, but don't need to store value

This is a fundamental concept in Computer Science. Searching a sorted
list using binary search is O(log n)
The above log is base 2.

The complexity to get an entry from a hashtable that doesn't have
collisions is O(1).

In other words, I can't think of any reason to use a sorted list over a
hashtable - regardless of the language (C# or otherwise).

Novice

Carl Daniel [VC++ MVP] wrote:
Bruce Wood wrote:
illegal.prime@xxxxxxxxx wrote:
Hey all, I seem to recall stumbling across a class that is exactly
the same as Hashtable, except lacking the Value portion. I need
something that works just like the Hashtable, but that doesn't store
a value (in addition to the key).

Essentially, I will just be storing string keys and will want to do a
lookup in my container to see if they exist in it. Hashtable would
achieve exactly this, but it would also expect a secondary Value
argument when I add the string keys to it. Now obviously I can still
use a Hashtable and just use null for Value, but I would rather not
do that.

Nope. There is no such structure.

Just store the key in both the Key and Value portions. It won't take
up any more space.

Using an ArrayList and binary search is slower than a Hashtable for
lookups, and much, much slower for inserts. Hashtable should be your
preferred solution.

That depends a great deal on the number of items, how they're distributed,
and how they're compared. It's quite commonn for a sorted list to be more
efficient than a hashtable for <100 items, and string comparison is quite a
lot faster than hashing for typical mixtures of strings (because the
comparison loop will typically bail out after only a few characters, while
the hash always runs to completion). The only way to really know is to
measure both approaches in your application - there's simply no hard & fast
rule that's always right.

-cd

.