To clarify the context I was talking about, I mean online checking of a hashed user password against Troy Hunt's HIBP database of hashed passwords. The original

To clarify the context I was talking about, I mean online checking of a hashed user password against Troy Hunt's HIBP database of hashed passwords. The original context of this discussion was an API, not a local copy of the database. That being said I'm actually going to concede this argument, because on further investigation Troy Hunt provides the entire copy of his database freely for local lookups. Once you hash the user password to match the database hashes you can introduce the optimizations you mentioned, and in any case it shouldn't introduce intolerable latency to do that lookup locally.