検索の実装を検討すると、シンボルテーブルの実装に使用される構造の特性を含む興味深いテーブルが見つかりました。 さらに、最悪のケースと平均的なケースが考慮されます。
| 最悪の場合 | 平均的なケース |
| 挿入 | 検索する | 選択肢 | 挿入 | 検索でヒット | 逃した検索 |
| キーインデックス配列 | 1 | 1 | M | 1 | 1 | 1 |
| 配列された配列 | N | N | 1 | N / 2 | N / 2 | N / 2 |
| 順序付けられたリンクリスト | N | N | N | N / 2 | N / 2 | N / 2 |
| 順序なし配列 | 1 | N | NlnN | 1 | N / 2 | N |
| 順不同リンクリスト | 1 | N | NlnN | 1 | N / 2 | N |
| バイナリ検索 | N | lnN | 1 | N / 2 | lnN | lnN |
| 二分探索木 | N | N | N | lnN | lnN | lnN |
| 赤黒の木 | lnN | lnN | lnN | lnN | lnN | lnN |
| ランダム化されたツリー | N | N | N | lnN | lnN | lnN |
| ハッシング | 1 | N | NlnN | 1 | 1 | 1 |