commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Pranas Baliuka" <pranas.bali...@danet.lt>
Subject RE: [collections] Faster than HashMap?
Date Mon, 10 Mar 2003 15:31:52 GMT
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:baliuka@mwm.lt]
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" <Yoav.Shapira@mpi.com>
To: "Jakarta Commons Developers List" <commons-dev@jakarta.apache.org>
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:scolebourne@btopenworld.com]
>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: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org




---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message