hash table lookup

[zaheer ahmad]

hi,

iam looking at the following code which does lookup in the hash table
int HashTable<Shape, Key>::FindEntry(Key key) {
...
Object* element = KeyAt(entry);
if (!element->IsNull() && Shape::IsMatch(key, element)) return entry;
...
the key match seems to be unconditional. is it required in case there
are no collisions in the table or is it optimized in some way in this
case.

sorry if iam being naive.

Thanks,
Zaheer

[Søren Gjesse]

Hi,

The code you are citing is part of a loop where the possible colliding elements are checked for match. Before the loop the entry probe is calculated from the hash on the key, and then quadric probing is used to check all entries with the same hash. A null indicate that an element has been deleted, so more probes are required. Undefined indicate on element found.

Regards,

Søren

--
v8-users mailing list
v8-u...@googlegroups.com
http://groups.google.com/group/v8-users

[zaheer ahmad]

Thank you for the reply. I realize that we cant really avoid the key
comparison in the general case, but in cases where the lookup entry is
known to exist in the table and there are no collisions we may be able
to optimize. (something like runtime lookup of symbols which are
guaranteed to exist after compilation phase)

couple of related questions
- is there a provision in v8 api to generate perfect hash for static
tables at the cost of little memory (gperf)
- i think it may be helpful to reorder the requested entry to the head
of the collision chain (locality principle) and if the cost of swap is
cheap.

Thanks,
Zaheer

2010/6/22 Søren Gjesse <sgj...@chromium.org>: