Hash table internals

Kestrel Pay must answer whether a payment id was stored, for a million ids and 20,000 requests a second. Scanning a list costs about 100 seconds of work for each second of traffic. A hash function turns the key into a bucket, so a lookup reads one bucket. Collisions are handled by chaining or probing, and the table doubles when the load factor passes about three quarters, which keeps inserts amortised constant time.