Ah yes, now that you mention it, I just checked the Java HashMap code and it is not limited to a power of two, here's a snippet:
index = (hash & 0x7FFFFFFF) % table.length; That way, they can still use the same set of 32bit hash values when growing. There is no "maximum" that can be "declared". The complete hash is always kept around. regards, B. 2006/5/17, Ron Wheeler <[EMAIL PROTECTED]>:
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). >> > _______________________________________________ > [email protected] > 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 > > > _______________________________________________ [email protected] 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
_______________________________________________ [email protected] 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
