std::unordered_mapは、エントリーごとにノードを割り当て、検索ごとにポインターをたどります。IDで注文を1秒に何百万回も検索するシステムでは、代わりにフラットなオープンアドレス法のテーブルを使うことがよくあります。前もってサイズを決めた、スロットの1つの配列です。キーはハッシュによってホームスロットに対応付けられます。そのスロットに別のキーがあれば次のスロット、さらにその次と試し(線形探査)、キーか空のスロットが見つかるまで続けます。
削除には注意が必要です。スロットを空にすると、そのスロットより先に置かれたすべてのキーの探査チェーンが切れてしまうため、削除したスロットは削除済みマーカーになります。検索はそれを飛ばして進み、挿入ではそれを再利用できます。また、テーブルはいくつかのスロットを本当に空のまま保つ必要があります。そうしないと、ないキーの検索が止まらなくなるため、負荷率(ここでは70パーセント)を超える挿入は拒否します。
容量が2のべき乗なら、ホームスロットはhash & (capacity - 1)で、これは下位ビットしか見ません。そのため、ハッシュでは上位ビットを混ぜ込む必要があります。そうしないと、容量の倍数であるIDはすべて1つのスロットに集まります。テストでは、ヒープの割り当てと、probes()を通じて、検索が訪れるスロットの数を数えます。