Hashtable.ContainsKey - what does this mean.

  • Thread starter Thread starter Guest
  • Start date Start date
G

Guest

Hi

While looking in the help I came across this statement in the remarks
section of the hashtable.containskey help:

"This implementation is close to O(1) in most cases"

Can anyone help me understand what this means ?


thanks
Lemony
 
It means if the key exists in the hashtable then it returns true otherwise
false.

If this helps, I've pasted the underline code which was produced by
Reflector.

public virtual bool ContainsKey(object key)
{
uint num1;
uint num2;
Hashtable.bucket bucket1;
if (key == null)
{
throw new ArgumentNullException("key",
Environment.GetResourceString("ArgumentNull_Key"));
}
Hashtable.bucket[] bucketArray1 = this.buckets;
uint num3 = this.InitHash(key, bucketArray1.Length, out num1, out
num2);
int num4 = 0;
int num5 = (int) (num1 % bucketArray1.Length);
do
{
bucket1 = bucketArray1[num5];
if (bucket1.key == null)
{
return false;
}
if (((bucket1.hash_coll & 0x7fffffff) == num3) &&
this.KeyEquals(bucket1.key, key))
{
return true;
}
num5 = (int) ((num5 + num2) % ((ulong) bucketArray1.Length));
}
while ((bucket1.hash_coll < 0) && (++num4 < bucketArray1.Length));
return false;
 
not at all.
it means the query algorythm has a speed independant of the number of
element i the hashtable.

O(1) means the lokup time doesn't depends on the number of element
O(n) means it varies linearly with the number of element
O(n2) means it varies as the square value of the number of element
best sorting algorythm vaires in
O(n ln(n))
 
Lloyd,

I think we all knew what you meant, but O(n ln(n)) is better written as
O(n lg(n)). There is still a lot of debate about which notations to
use for logarithms, but it is generally assumed that ln means
log-base-e, log can either mean log-base-10 or log-base-e, and lg
usually means log-base-2.

Brian
 
Brian Gideon said:
I think we all knew what you meant, but O(n ln(n)) is better written as
O(n lg(n)). There is still a lot of debate about which notations to
use for logarithms, but it is generally assumed that ln means
log-base-e, log can either mean log-base-10 or log-base-e, and lg
usually means log-base-2.
Click to expand...

In that case surely it would be better written as O(n log(n)) as the
order of complexity doesn't depend on the base at all.

I'm certainly more familiar with reading either ln(n) or log(n).
 
Yes, actually you're probably right. When used in Big-Oh notation log
is almost always assumed to be base 2, which means that it actually
operates on all 3 bases depending on how the notation is used. But,
like you said, it doesn't matter that much anyway in complexity
analysis unless you're trying to estimate the number of operations a
particular algorithm performs.

Brian
 
Brian Gideon said:
Yes, actually you're probably right. When used in Big-Oh notation log
is almost always assumed to be base 2, which means that it actually
operates on all 3 bases depending on how the notation is used. But,
like you said, it doesn't matter that much anyway in complexity
analysis unless you're trying to estimate the number of operations a
particular algorithm performs.
Click to expand...

In which case Big-Oh notation isn't the right tool for the job.
Whatever base it is, it'll be constant - and O(n) = O(kn) for any
constant k, so it doesn't matter at all.
 
for your information
assuming log(n) is log10
and ln(n) is neper-ian(? not sure about the english name!) (AKA natural log)
the difference is simple
log(n) = ln(n) / ln(10)

ln(10) ~= 2.xxxx

Anyway we were saying the time is proportional to: ln(n)
so adding a constant (switching from ln to log) doesn't change this property
at all, does it?
furthermore ln(10) ~= 2 means we stay in the same order of magnitude.


Bottom line, from a 'mathematical' point of view (from a physisicist point
of view, dare I say, in fact :D :D) it doesn't matter at all!
But if you prefer the "log()" notation (if you are used to it), then I
accept that, so be it!
 
Jon said:
In which case Big-Oh notation isn't the right tool for the job.
Whatever base it is, it'll be constant - and O(n) = O(kn) for any
constant k, so it doesn't matter at all.
Click to expand...

Big-Oh is certainly not the tool for the job of determining the number
of operations an algorithm must perform. That's the job of the initial
equations that were used to get the Big-Oh in the first place. If the
initial equation contains a lg(n) or log(n) component then why would
you change that notation by saying the complexity is O(ln(n))?

I prefer using lg(n) in the initial equations because it is my belief
that there is less ambiguity in the base. I naturally carry over that
notation when writing the Big-Oh complexity because I see no compelling
reason to change it.

For example, consider the AVL tree. We want to know the runtime
complexity of a search and we know that it is a function of the height
h. For a AVL tree h <= 1.44*lg(n+1). The base is important here
because the tree is binary (it has at most 2 branches at each node).
You wouldn't want to use ln(n) because the tree doesn't have ~2.718
branches. So why would you suddenly change lg(n) to ln(n) when writing
the Big-Oh?

Brian
 
Brian Gideon said:
Big-Oh is certainly not the tool for the job of determining the number
of operations an algorithm must perform. That's the job of the initial
equations that were used to get the Big-Oh in the first place. If the
initial equation contains a lg(n) or log(n) component then why would
you change that notation by saying the complexity is O(ln(n))?
Click to expand...

Because (to my mind) ln and log are both more instantly recognisable as
being log than lg is. This could be due to a maths degree background
where log base 2 wasn't often useful - I don't think I've actually ever
seen lg before this thread. (ln and log both appear on most scientific
calculators, for instance; lg doesn't as far as I can remember - that
implies a certain amount of common readability.)

I'd pick log over ln - it's instantly readable and doesn't imply any
particular base.

What's your reason for preferring other people (who may have different
initial equations which genuinely involve ln(n)) to write O(lg(n)) to
O(ln(n))?
 
Jon said:
Because (to my mind) ln and log are both more instantly recognisable as
being log than lg is. This could be due to a maths degree background
where log base 2 wasn't often useful - I don't think I've actually ever
seen lg before this thread. (ln and log both appear on most scientific
calculators, for instance; lg doesn't as far as I can remember - that
implies a certain amount of common readability.)
Click to expand...

That's enough for me to concede. Afterall, if you aren't familiar with
it then maybe it's not as prevelant as I thought.
I'd pick log over ln - it's instantly readable and doesn't imply any
particular base.
Click to expand...

I'd pick log as well. However, I still think that log does imply a
particular base. On calculators it's 10 and the Math.Log function is
e.
What's your reason for preferring other people (who may have different
initial equations which genuinely involve ln(n)) to write O(lg(n)) to
O(ln(n))?
Click to expand...

I guess my original thinking was that if it genuinely involves ln(n)
then write O(ln(n)). But, now you have me second guessing that as
well. Perhaps log(n) should always be used.
 
Back
Top