There are two kinds of HTTP Public Key Pinning, static HPKP and dynamic HPKP.
For Google Chrome at least, static HPKP involves a list of websites and their public keys actually hardcoded in a json file distributed with all Chrome builds. Firefox keeps it in a header file with a large struct containing the websites and pinned keys. This is similar to HSTS preloading, but tends to involve only higher profile sites, so you can't submit your own. This list is not huge, so it's easy to query rapidly. If it were to include particularly many sites, it would not scale.
This is similar to HSTS. A server sends an HTTP header containing the pin directive along with a fingerprint and a backup fingerprint. Like HSTS, it also encodes the duration for which this will be valid. After getting the fingerprint, the browser will only connect to the website if it matches, until the expiry is up. This is stored in memory or on disk, and at most contains only the website you've visited which use dynamic HPKP. Assuming CA compromise, HPKP effectively provides a strong TOFU (Trust On First Use) guarantee on top of TLS.
The actual implementation is probably not relevant. For static HPKP, I imagine Firefox simply loops over the struct to find matches, and Chrome uses its internal json parser to find matches. For dynamic HPKP, it's probably some kind of list, whether a linked list or something faster and lighter like some kind of tree, I don't know. Either way, it would not be a significant bottleneck compared to the rest of the complex operations a browser needs to go through to perform a proper TLS handshake.
You underestimate the performance of a well-optimized hash tree or radix tree. :)