std::unordered_map aloca um nó por entrada e segue um ponteiro a cada busca. Sistemas que buscam ordens por id milhões de vezes por segundo costumam usar, em vez disso, uma tabela plana de endereçamento aberto: um array de slots, dimensionado de antemão. Uma chave gera por hash um slot de origem; se esse slot tem outra chave, tente o próximo, depois o seguinte (sondagem linear), até encontrar a chave ou um slot vazio.
Apagar exige cuidado. Esvaziar um slot cortaria a cadeia de sondagem de toda chave que foi colocada depois dele, então um slot apagado vira uma lápide: as buscas passam por cima dela e as inserções podem reutilizá-la. A tabela também precisa manter alguns slots realmente vazios, ou a busca por uma chave ausente nunca terminaria, então as inserções são recusadas acima de um fator de carga, aqui de 70 por cento.
Com uma capacidade que seja potência de dois, o slot de origem é hash & (capacity - 1), que só olha os bits baixos, então o hash precisa misturar neles os bits altos; caso contrário, os ids que são múltiplos da capacidade caem todos em um único slot. Os testes contam as alocações no heap e, com probes(), quantos slots as buscas visitam.
A sondagem linear avança a partir do slot de origem e volta ao início ao chegar ao fim.