Yes it trivial to generate hash table for known key type like string, but things are more complicated with "object". value returned by hashCode must be "good" to generate "good" map. The most trivial situation (hashCode1 == hashCode2) <==> (object1.equals(object2) )
----- Original Message ----- From: "Pranas Baliuka" <[EMAIL PROTECTED]> To: "Jakarta Commons Developers List" <[EMAIL PROTECTED]> Sent: Monday, March 10, 2003 4:31 PM Subject: RE: [collections] Faster than HashMap? > Juozas, > > You can gain valuable information about hash functions from project gperf( > http://www.gnu.org/software/gperf/gperf.html ) > > /Pranas > > -----Original Message----- > From: Juozas Baliuka [mailto:[EMAIL PROTECTED] > Sent: 2003 m. kovo 10 d. 16:30 > To: Jakarta Commons Developers List > Subject: Re: [collections] Faster than HashMap? > > > > Map performance depends on hash function implementation, one of ways to > optimize it is to find "the best" hash function at runtime (dependant on > known hash codes at runtime ) and rehash map using this function. > > int findIndex(int hashCode){ > //some hash function implementation generated at runtime > } > > "switch" is one of ways, it must be possible to find more ways. > > ----- Original Message ----- > From: "Shapira, Yoav" <[EMAIL PROTECTED]> > To: "Jakarta Commons Developers List" <[EMAIL PROTECTED]> > Sent: Monday, March 10, 2003 3:07 PM > Subject: RE: [collections] Faster than HashMap? > > > > Howdy, > I must be completely missing something here, but doesn't that require > your do not all the hashcodes of the items in the map at compile time? > > Yoav Shapira > Millennium ChemInformatics > > > >-----Original Message----- > >From: Stephen Colebourne [mailto:[EMAIL PROTECTED] > >Sent: Saturday, March 08, 2003 12:43 PM > >To: Jakarta Commons Developers List > >Subject: [collections] Faster than HashMap? > > > >I'd had an idea for a way to create a map thats faster to read than a > >HashMap... > > > >The idea was to bytecode generate the mapping from the hashcode to the > >index: > >public int lookupIndex(Object key) { > > switch (key.hashCode()) { > > case -1682: // hashcode > > return 2; // index of Map.Entry > > case 86929 // hashcode > > return 0; // index of Map.Entry > > case 1596969: // hashcode > > return 1; // index of Map.Entry > > } > > return -1; > >} > > > >Simple? No hashcode collisions. Should go faster.... > > > >Attached are the java files. My initial testing was with a size 3 map, > and > >that goes about 40% faster. Unfortunately, the bytecode map's > performance > >degenerates with size. Depending on exact data size 50 entries or more > may > >be slower, gradually getting slower. > > > >Of course now I realise that the switch statement in bytecode isn't > magical > >and is just doing a binary search, so was always going to suffer this > >problem. What an idiot I am. > > > >If anyone else wants to take a look and see if I've missed something, > or > >has > >another bright idea triggered by this then feel free to take a look at > the > >code. Otherwise, its not worth adding to [collections]. :-(((( > > > >Stephen > > > > > This e-mail, including any attachments, is a confidential business > communication, and may contain information that is confidential, proprietary > and/or privileged. This e-mail is intended only for the individual(s) to > whom it is addressed, and may not be saved, copied, printed, disclosed or > used by anyone else. If you are not the(an) intended recipient, please > immediately delete this e-mail from your computer system and notify the > sender. Thank you. > > > --------------------------------------------------------------------- > To unsubscribe, e-mail: [EMAIL PROTECTED] > For additional commands, e-mail: [EMAIL PROTECTED] > > > > > --------------------------------------------------------------------- > To unsubscribe, e-mail: [EMAIL PROTECTED] > For additional commands, e-mail: [EMAIL PROTECTED] > > > > --------------------------------------------------------------------- > To unsubscribe, e-mail: [EMAIL PROTECTED] > For additional commands, e-mail: [EMAIL PROTECTED] > > --------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
