Hay dos tipos de fijación de clave pública HTTP, HPKP estática y HPKP dinámica.
HPKP estático
Al menos para Google Chrome, el HPKP estático incluye una lista de sitios web y sus claves públicas realmente codificadas en un archivo json distribuido con todas las versiones de Chrome. Firefox lo mantiene en un archivo de encabezado con una gran estructura que contiene los sitios web y llaves clavadas. Esto es similar a la carga previa de HSTS, pero tiende a involucrar solo a sitios de perfil más alto, por lo que no puede enviar uno propio. Esta lista no es enorme, por lo que es fácil de consultar rápidamente. Si incluyera particularmente muchos sitios, no se escalaría.
Dynamic HPKP
Esto es similar a HSTS. Un servidor envía un encabezado HTTP que contiene la directiva pin junto con una huella digital y una huella digital de respaldo. Al igual que HSTS, también codifica la duración por la cual esto será válido. Después de obtener la huella digital, el navegador solo se conectará al sitio web si coincide, hasta que finalice la caducidad. Esto se almacena en la memoria o en el disco, y como máximo contiene solo el sitio web que ha visitado que utiliza HPKP dinámico. Asumiendo el compromiso de CA, HPKP proporciona efectivamente una garantía sólida de TOFU (Trust On First Use) sobre TLS.
La implementación real probablemente no sea relevante. Para HPKP estático, imagino que Firefox simplemente recorre la estructura para encontrar coincidencias, y Chrome usa su analizador interno de json para encontrar coincidencias. Para HPKP dinámico, es probable que sea algún tipo de lista, ya sea una lista vinculada o algo más rápido y ligero como algún tipo de árbol, no lo sé. De cualquier manera, no sería un cuello de botella significativo en comparación con el resto de las operaciones complejas que debe atravesar un navegador para realizar un protocolo de enlace TLS adecuado.
Subestima el rendimiento de un árbol hash o de radix bien optimizado. :)