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]
