Is JavaScript switch statement linear or constant time?

Question

I have the following JavaScript on my site so that when certain specific searches are performed, the answer is hardcoded to a specific page:

function redirect() {
    var input = document.getElementById('searchBox').value.toLowerCase();

    switch (input) {
      case 'rectangular':
        window.location.replace('http://www.Example.com/Rectangular/');
        break;
      case 'elephant':
        window.location.replace('http://www.Example.com/Elephants/');
        break;
      case 'coils':
        window.location.replace('http://www.Example.com/Parts/');
        break;
      default: // No keyword detected: submit the normal search form.
        return true;
        break;
    }
    return false; // Don't let the form submit
}

I'm wondering whether the search statement in JavaScript is linear on the number of case statements or constant time? If linear, is there a better way to write this code so it is constant time regardless of the number of special cases I code?

[This related question](http://stackoverflow.com/q/4442835/634824) may be useful, but doesn't specifically say whether JS is optimized with jump table lookups or not. That said, your code would be much cleaner and probably faster using a simple name:value pair mapping of input and url. — Matt Johnson-Pint, Dec 12 '16 at 20:58

Bergi · Answer 1 · 2016-12-12T22:28:49.913

4

The spec does not make any time complexity guarantees for the switch statement. It's semantics to do require a sequential evaluation of the case expressions however, so in the general case it behaves linearly.

Engines are free to optimise the evaluation if all of the cases are constant strings or numbers (and it's fairly simple), so you can expect constant time complexity.

If you want to enforce a better-than-linear behaviour, you need to use a Map as a lookup table:

var redirects = new Map([
    ['rectangular', 'http://www.Example.com/Rectangular/'],
    ['elephant', 'http://www.Example.com/Elephants/'],
    ['coils', 'http://www.Example.com/Parts/']
]);
function redirect() {
    var input = document.getElementById('searchBox').value.toLowerCase();
    if (redirects.has(input)) {
        window.location.replace(redirects.get(input));
        return false; // Don't let the form submit
    } else {
        return true;
    }
}

In a pre-ES6 environment, you can also use an object for the same purpose. All engines have implemented O(1) property lookup although they're not formally required to.

edited Dec 12 '16 at 22:28

answered Dec 12 '16 at 20:59

Bergi

630,263
148
957
1,375

Is there a way to lookup in the map only once, that is somehow use the exists test to also give you the value? Also, please elaborate on the pre-ES6 idea, if you are in ES6 can you still use map, not sure why you called out that rev? – WilliamKF Dec 12 '16 at 22:03
[`get`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/get) returns `undefined` if the key is not found, if you never use that as a value you can also distinguish what to do based on this. Regarding objects, maps were only introduced with ES6 so older browsers don't support them natively. – Bergi Dec 12 '16 at 22:30
What would be an example of using an object (in pre-ES6 env.) to do the same thing as a map? Also, for a map, is there shorthand to have multiple keys with the same value? – WilliamKF Dec 12 '16 at 22:47
See @MarkOrmstons answer for that, it's exactly what I meant. No, there's no shorthand, but a map is builtin data structure and can be modified/created programmatically to your liking (e.g. to avoid repeating the `http://www.Example.com/` prefix). – Bergi Dec 12 '16 at 22:55

score 2 · Accepted Answer · edited Dec 12 '16 at 22:56

2

Here's the equivalent of Bergi's answer in ES5. It'll be fast and also a lot easier to modify compared to what you're using now.

var _redirectlist = {
  'rectangular': 'http://www.Example.com/Rectangular/',
  'elephant': 'http://www.Example.com/Elephants/',
  'coils': 'http://www.Example.com/Parts/'
};

function redirect() {
  var input = document.getElementById('searchBox').value.toLowerCase();

  // Redirect if we have the input in our list
  if (_redirectlist.hasOwnProperty(input)) {
    window.location.replace(_redirectlist[input]);
    return false;
  }

  return true;
}

edited Dec 12 '16 at 22:56

Bergi

630,263
148
957
1,375

answered Dec 12 '16 at 22:34

Mark Ormston

1,836
9
13

I assume it is ok to use `var target = _redirectlist[input]` to avoid double lookup, right? What is syntax if I have multiple keys with the same value, do I have to repeat full key value, or can I give multiple keys for one value? – WilliamKF Dec 12 '16 at 22:50
@Bergi What's the advantage of using `hasOwnProperty()` versus using lookup and storing in a variable, or will lookup failing not provide a `False` value? – WilliamKF Dec 12 '16 at 23:06
There is no point in adding the hasOwnProperty at all here, except perhaps in uber debug mode in some browsers. I'm not sure why this was changed. – Mark Ormston Dec 12 '16 at 23:39
@WilliamKF Yes, you can can use a var if you want. The speed difference is really negligible in this case and most browsers automatically optimize that sort of use-case so even in tests, it may not turn up faster. If you have multiple values that mean the same thing, you can either have a second list to remap them, or add each possible entry to `_redirectlist` with the URL every time. – Mark Ormston Dec 12 '16 at 23:42
2

Ok, thinking about it, I think I know why Bergi added the hasOwnProperty... because of values in Object.prototype. When you're taking user input directly like that, yeah, you want to make certain they don't put in something weird. Like prototype which will generally pass the truesy test. – Mark Ormston Dec 12 '16 at 23:46

Is JavaScript switch statement linear or constant time?

2 Answers2

Linked