C/C++のswitch-caseはO(1)

仕事のプログラムでswitch-caseを使ってるプログラムを見て「確かswitch-caseってif-elseと同じでラベルの数に対してO(n)だったよな。O(log n)のstlのmapにでも書き換えさせたろ。」と思ったので調べてみたところ最近はハッシュによる探索でO(1)との情報を得たので調査。
見つけた

検証方法:
switch-caseでN個のラベルを定義してSIZE_MAX回だけ回してその間のタイムを計測。
ただし、最適化を防ぐために余計な処理もあり。

結果としてはタイムにばらつきはあるものの条件をラベル数、2でも10000くらいにしても1.5 micro secondsさえも超えず。

switch-case文のO(1)は本当だと思われるので最早、静的にラベルが決まる際にはswitch-caseを使わなければならない。mapは使ってはならない。
さらに検証をしたところC言語も同様に1.5micro secを超えなかったのでC系は全部そうなっているものかと思われる。

参考
O(n)についてはこちら。
https://qiita.com/asksaito/items/59e0d48408f1eab081b5

O(1)と書かれているページの一例
http://blogs.wankuma.com/rti/archive/2007/01/31/60020.aspx
https://stackoverflow.com/questions/6860525/c-what-is-faster-lookup-in-hashmap-or-switch-statement?rq=1

ググっていくと"ジャンプテーブルルックアップ"というキーワードにたどり着いた、しかしこれを解読するには多少のアセンブラの知識が必要そうなのでとりあえずここまでにしておく。

追記
効率の良い組込みC言語プログラミング
という本には「出現率の高い値を先に比較した方がいい」と涙ぐましい最適化方法が書いてある。どう考えてもO(1)である時に気にするような事ではない。因みに本の初版が2009年だそうなのでハッシュ変換はそれ以降だと思われる。
リンク
http://amzn.asia/2N6VNa1