Most of the switch structures used in Perl scale linearly. They're all pretty much the same. The only exception to this is a hash that stores references to subroutines (example on page 282 of the Blue Camel).

As pg recently pointed out, hashes have an absolute worst case runtime of O(n), but that case is so unlikely that it can be safely ignored (and perl's specific implementation does tricks to help make sure it won't happen). In the common case, hashes run very close to O(1).

Note, though, that the constant value of hash searching is larger than a simple if tree, so if you have a small number of cases, the ifs might still be faster. If you're comparing integer, you could use a regular array instead of a hash, which will always give you O(1) efficiency with a much smaller constant.