検索操作の構造特性の比較

検索の実装を検討すると、シンボルテーブルの実装に使用される構造の特性を含む興味深いテーブルが見つかりました。 さらに、最悪のケースと平均的なケースが考慮されます。

	最悪の場合			平均的なケース
	挿入	検索する	選択肢	挿入	検索でヒット	逃した検索
キーインデックス配列	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