std::unordered_map reserva un nodo por entrada y sigue un puntero por búsqueda. Los sistemas que buscan órdenes por id millones de veces por segundo suelen usar en su lugar una tabla plana de direccionamiento abierto: un array de huecos dimensionado de antemano. Una clave da por hash un hueco de origen; si ese hueco tiene otra clave, prueba el siguiente y luego el siguiente (sondeo lineal), hasta encontrar la clave o un hueco vacío.
Borrar requiere cuidado. Vaciar un hueco cortaría la cadena de sondeo de cada clave que se colocó más allá, así que un hueco borrado se convierte en una lápida: las búsquedas pasan por encima y las inserciones pueden reutilizarla. La tabla también tiene que mantener algunos huecos de verdad vacíos, o la búsqueda de una clave que no está nunca terminaría, así que las inserciones se rechazan por encima de un factor de carga, aquí el 70 por ciento.
Con una capacidad potencia de dos, el hueco de origen es hash & (capacity - 1), que solo mira los bits bajos, así que el hash tiene que mezclar en ellos los altos; si no, los ids que son múltiplos de la capacidad caen todos en un mismo hueco. Las pruebas cuentan las reservas en el heap y, con probes(), cuántos huecos visitan las búsquedas.
El sondeo lineal avanza desde el hueco de origen y vuelve al principio al llegar al final.