リストの探索では、一致するものが見つかるまで値を比較します。辞書の検索は別のデータ構造を使い、リストの先頭要素を削除すると残りの参照がずれます。こうした細部は、小さなヘルパーが頻繁に回るループの中にあるときに効いてきます。
ここではブラウザーで時間を計測する代わりに、操作の回数を数えます。回数は再現可能で、増え方を目に見える形にします。また、何を数えたのかを明確にする必要があります:比較、ずれた参照、入力の訪問、順序なしのペアのいずれかです。ハッシュテーブルの検索は通常の条件では平均で定数コストですが、これは前提を置いたモデルであり、あらゆるオブジェクトや衝突パターンについての保証ではありません。コンテナを変えても結果は保ってください。
見つからないクエリはすべての要素を走査しますが、一致した比較も数えてください。クエリごとに新しい比較カウンターを使ってください。最初に等しい値が見つかるまでリストをたどってください。要素数n、クエリ数qのとき、最悪の場合の比較回数はn×qに比例して増えます。