This has some interesting implications and raises some questions such as "Why?" and "What the hell?".
Of interest is that efficiency is commonly cited as the reason switch statements in Java only take integer types and use constant cases. I imagine however that if implemented by a hash table, constant time performance could be given for string based switch statements.
I am speaking of the most simple and easily optimized switch statements: switches with n cases, cases from 0 to n-1.
So for n = 3 it looks like
switch(s) { case 0: something; break; case 1: something; break; case 2: something; break; }
I believe the Java bytecode, as verified by Clam in #xkcd, is in fact the standard lookup table type of implementation, which should run in constant time. However, it does not.
This undermines the value of switch statements as used to make programs efficient.
If very fast switch statements are needed a couple work arounds could be tested:
Method 1: if/else binary search. Theoretically gives at least O(log n) performance for n cases which is practically constant time. edit: tested, see results below. This method is faster than switches until about 330 cases, when the if/else binary search method suddenly takes much more time.
Method 2: Replacing a switch statement with n cases: Create one abstract class c with method f(). For each switch case s, derive a class "c[s]" from c, write function f() as what would have been in the switch case. Create an array of type c. At each index s of the array, put an object of type c[s] there. Where the switch statement was needed, do an array lookup into the array you made and filled in, and then call f() on the object at the index you were looking for in the switch. As convoluted as this method is, it may still be faster than switch statements, depending on how fast the derived methods can be called. Some testing suggested this method was in fact always faster than switches larger than a certain number of cases.
Finally, the machine I'm using.
* Windows XP, 32 bit.
* Code written in Processing 1.01. As I understand it, Processing uses the standard Windows JVM for Java 1.5 on my machine.
The results.
The code that generates the testing code, both of which run in Processing 1.01: http://www.processing.org.