commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Stephen Colebourne" <scolebou...@btopenworld.com>
Subject [collections] Faster than HashMap?
Date Sat, 08 Mar 2003 17:43:13 GMT
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


Mime
View raw message