Thread-safe tally counter with bounded memory

Build a tally service that many threads call at once to count occurrences of keys, and that answers queries for counts. Memory is bounded, so it cannot keep every key forever. Make the updates thread-safe without one global lock becoming the bottleneck, and explain what you give up when memory runs out.