sixlegs.com / blog / java / cglib-stringswitch-hash.html

Root Beer Logo Root Beer

Chris Nokleberg's Fizzy Weblog

June 2003
Su M Tu W Th F Sa
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 19 20 21
22 23 24 25 26 27
29 30
Previous  |  Next  |  More...
#  Switching on Strings, now using hashCode!

Got some good comments on the string switching algorithm from Bob Lee. They prompted me to write an alternate implementation that switches on hashCode instead of by character. The generated pseudocode looks like:

switch (arg.hashCode()) {
case 3112:
  if (arg.equals("at")) {
    /* a */
  }
case 97299:
  if (arg.equals("bar")) {
    /* b */
  }
case 97307:
  if (arg.equals("baz")) {
    /* c */
  }
}

Note: fall-through issues intentionally ignored in this example

For common use-cases the two implementations perform very similarly. In extreme cases they each start to break down in different ways, though, so I'm going to make both available.

For example, the bytecode for the switch here is shorter, but you need more string constants in your constant pool (one for each label). As the number of labels increases, the initial switch will get slower, since the sparse hash code values will force a lookupswitch (binary search). Of course, the same could happen with the original version, if the characters that make up your labels were evenly distributed over the entire range (0-65535), but I think that's uncommon. This version also slows down if the argument hashCode hasn't been previously computed. And so on...

[Powered By FreeMarker]  [Valid Atom 1.0]  [Weblog Commenting by HaloScan.com]