Bernard Poulin wrote:
Funny, I was actually thinking of an implementation which would use a
Java-style String objects. In java, all string objects have an "int" hash
data member (computed the first time it is needed).
In that scenario, only a portion of the hash value is used to make the
hash
lookup. The complete hash stays around since it is part of the String
object
and so can still be used to quickly "distinguish" strings. Also when
"rehashing" you do not need to really compute new "hashes" - you just
need
to re-distribute them based on more bits of the complete hash.
That only works if the hash primary table has a length that is a power
of 2. If your original has maps from 1-5,000 and your increase the size
of the primary storage area to 15,000, you will need more than more
bits, you will need a completely different set of hash values.
Not sure what Java does with its hash. Do you have to declare the
maximum array size when you declare the array?
Ron
And yes, this
is still heavier than re-balancing a tree.
regards,
B.
Binary searches may involves a lot more string comparison. In a binary
> search comparing the "string hash" value is of no use to know if the
> value
> is "greater" or "lower" (to decide for the next search direction). In
> hashmaps, the lookup in the "chain" after the hash jump can, most
of the
> time, "skip" a string entry without even looking at the characters by
> comparing the 32bit integer hashes.
String hashes are only useful for looking up a specific value. It is
unlikely that the hashes are even stored since once you store the
key/value you no longer have any need for the hash since the position in
the main table is known and you can follow the links in the overflow
back to the main table(usually).
If you are hashed into the overflow, you have to examine each key since
the hashes are identical for everyone in the list (otherwise they would
not be in the list - they would be in another list of collided hashes).
_______________________________________________
Flashcoders@chattyfig.figleaf.com
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
_______________________________________________
Flashcoders@chattyfig.figleaf.com
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
